Suche in TStrings optimieren
Hallo,
ich arbeite an einem Chatprogramm, in dem sich Benutzer von mehreren Rechnern aus anmelden können. Sie erscheinen also mehrfach in der Liste der Clients. Man kann Nachrichten zwar grundsätzlich an mehrere Clients schicken. Es ist aber gewünscht, dass ein und derselbe Benutzer die Nachricht auch dann mehrfach bekommt, wenn er nicht mehrfach ausgewählt wurde. Dazu folgendes Beispiel: Client-Liste ------------ Abraham // auf PC 1 Abraham // auf PC 2 Lisa Ziel: Wähle ich Abraham nur einmal aus, soll er dennoch auf beiden Rechnern die Nachricht empfangen. Mein Code dazu sieht bis jetzt so aus:
Delphi-Quellcode:
Mein Problem ist nun folgendes:
Procedure TForm1.Button1Click(Sender: TObject);
Var SendTo : Array Of Boolean; SendList : String; I : Integer; Current : String; J : Integer; Begin // Initialisierung SetLength(SendTo, Clients.Count); SendList:=''; // Der eigentlich Suchlauf For I:=0 To Pred(Clients.Count) Do If Clients.Selected[I] Then Begin SendTo[I]:=True; Current:=Clients.Items[I]; SendList:=SendList + Current + ', '; For J:=0 To Pred(Clients.Count) Do SendTo[J]:=(SendTo[J] Or (Clients.Items[J] = Current)); End; //Ausgabe der Ergebnisse For I:=0 To Pred(Clients.Count) Do If SendTo[I] Then ShowMessage(IntToStr(I) + ': ' + Clients.Items[I]); System.Delete(SendList, Pred(Length(SendList)), MaxInt); ShowMessage('Gesendet an:' + #13 + SendList); // Speicher aufräumen SetLength(SendTo, 0); End; Der Code funktioniert und bei unseren ca. 15 Teilnehmer ist das auch kein Problem. Wenn das aber größer wird, habe ich so meine Bedenken. Denn man kann absehen, dass für die Suche genau n * n Durchläufe nötig sind. Bei 3 Einträgen also 9. Wenn es aber 100 Einträge wären, dann wären das schon 10.000 Durchläufe usw.. Was noch wichtig sein dürfte: Die Einträge sind sortiert. Kann man das irgendwie optimieren? Ich erinnere mich noch dürftig an meine Schulzeit, wo wir nach Bubblesort dann Quicksort beigebracht bekamen. Ich bin aber nicht in der Lage zu durchdenken, ob ich daraus hierfür etwas ableiten könnte. Manchmal ist es ja so, dass schon einmal jemand dasselbe Problem hatte und ich da etwas abstauben könnte :lol: Gruß, Alex |
AW: Suche in TStrings optimieren
Zitat:
Da die Liste sortiert ist, brauchst du an dieser Stelle:
Delphi-Quellcode:
Nicht alle durchgehen, sondern nur ab dem aktuellen einmal hoch und einmal runter solange der Text gleich bleibt.
For J:=0 To Pred(Clients.Count) Do
SendTo[J]:=(SendTo[J] Or (Clients.Items[J] = Current));
Delphi-Quellcode:
// Der eigentlich Suchlauf
For I:=0 To Pred(Clients.Count) Do If Clients.Selected[I] Then Begin SendTo[I]:=True; Current:=Clients.Items[I]; SendList:=SendList + Current + ', '; J := I+1; while (Clients.Items[J] == Clients.Items[I]) begin SendTo[J]:=True; inc(J); end; J := I-1; while (Clients.Items[J] == Clients.Items[I]) begin SendTo[J]:=True; dec(J); end; End; |
AW: Suche in TStrings optimieren
Mir fällt dabei immer Hashing und auftretende Kollisionen ein... Du hast ja einen eindeutigen Namen "Abraham" und mehrere Clients dazu. Ausgehend davon, dass du immer erst nach dem Namen suchst, könntest du eine THashedStringList (uses IniFiles) nutzen und mit einem Eintrag eine TList verknüpfen. In der TList führst du dann alle Client-Objekte (z.B. IP-Adresse).
Die Liste sieht dann in etwa wie folgt aus:
Code:
Damit hättest du dann einen sehr flotten Zugriff auf die Liste und brauchst dann quasi nur noch diese Liste durchgehen. Du sparst dir x-Iterationen, um in einer sortierten(!) Liste zu suchen.
Verena -> TList(192.168.0.1)
Otto -> TList(192.168.0.2, 192.168.0.3) Abraham -> TList(192.168.0.4, 192.168.0.5, 192.168.0.6) |
AW: Suche in TStrings optimieren
Danke für die super Antworten!
@jfheins Die Sache mit dem Hoch- und Runtergehen hatte ich mir in der Zwischenzeit auch schon überlegt. So elegant wie Du habe ich es leider nicht, aber es klappt auch bei mir (erprobt mit trial and error). Wenn ich Deinen Code richtig lese (mit der Betonung auf wenn), dann hat er einen einzigen Haken: Er geht jedes Mal, wenn ein Fund auftritt, nach oben und nach unten. Wenn man Pech hat, der Benutzer hatte (1) alle Einträge ausgewählt und es gibt (2) jeden Eintrag nur einmal, was (3) zwar nicht gewollt ist, dann bedeutet das selbst im Idealfall immer noch n * 3 (n selbst, 1 oben, 1 unten) Schritte. Mir war auch aufgefallen, dass Du
Delphi-Quellcode:
immer mit
Clients.Items[I]
Delphi-Quellcode:
statt wie ich mit
Clients.Items[J]
Delphi-Quellcode:
vergleichst. Geht das so schneller?
Current
Ich selbst hatte aus diesem Grund bei meinen Überlegungen die For- durch eine While-Schleife ersetzt. Das ganze sieht bei mir jetzt so aus:
Delphi-Quellcode:
Den Vorschlag von s.h.a.r.k kann ich leider nicht umsetzen, weil ich keine weiteren Daten als die Nummer in der Liste habe. Diese kommt bereits sortiert vom Server. Ein umsortieren der Benutzer lasse ich nicht zu; ist mir einfach zu aufwendung.
I:=0;
While (I < Clients.Count) Do Begin If Clients.Selected[I] Then Begin SendTo[I]:=True; Current:=Clients.Items[I]; SendList:=SendList + Current + ', '; // vor gefundenem Eintrag suchen J:=Pred(I); While (J >= 0) Do If (Clients.Items[J] = Current) Then Begin SendTo[J]:=True; Dec(J); End Else Break; // nach gefundenem Eintrag suchen J:=Succ(I); While (J < Clients.Count) Do If (Clients.Items[J] = Current) Then Begin SendTo[J]:=True; Inc(J); End Else Break; // nach dem letzten gefundenen Eintrag weiter machen I:=J; End Else Inc(I); // <- besonders wichtig! Hatte ich erst vergessen und ewig den Fehler nicht gefunden. End; ABER: Das bringt mich auf die Idee, wie man es evtl. nochmals verbessern kann. Indem man nämlich die Liste 2 x durchgeht. Beim ersten mal sammelt man "nur" alle die, die markiert sind in einer 2. TStringList, die ebenfalls sortiert ist und keine doppelten Einträge zulässt. Beim 2. Durchlauf vergleicht man dann einfach mit IndexOf(), ob ein entsprechender Eintrag aus der Originalliste auch in der 2. Liste ist. Es könnte bloß daran scheitern, dass IndexOf() seinerseits die Liste zumindest teilweise durchgeht und damit der Vorteil wieder futsch ist, wenn viele ausgwählt sind. Soviel zur Theorie. Die Praxis werde ich morgen mal testen. Vermutlich müsste ich mal größere Listen generieren lassen, um es zu testen. Danke nochmal, Alex |
AW: Suche in TStrings optimieren
Zitat:
Und weniger komplex als linear geht's (in diesem Fall) nicht ;) Zitat:
Aber es war ja klar was gemeint war. Zitat:
Zitat:
Der obige mit den while-Schleifen benötigt im Worst-Case 3n Vergleiche (Wenn alle Einträge anders sind und alle ausgewählt) dieser hier hingegen n*ld(n) !! Von der Komplexität her also n vs. n*log(n), und das auch nur, wenn eine binäre Suche benutzt wird. Zugegeben, der Unterschied ist marginal und wird bei realistischen Datenmengen nicht auffallen. Aber mit signifikanten Performancegewinnen würde ich nicht rechnen ;) Das mit den while-Schleifen sollte erstmal hinreichend schnell sein. Falls später mal Performanceprobleme bei dem Code auftreten kannst du ihn dir ja wieder vornehmen ;) |
AW: Suche in TStrings optimieren
Danke für die Erklärung!
Vermutlich muss ich es aber doch so machen, wie zuletzt geplant, auch wenn der Ansatz schlechter ist: Es wäre ja denkbar, dass sich ein Benutzer an- oder abmeldet, während das Senden läuft. Da wäre es schön, wenn der neue Benutzer bei Identität die Nachricht gleich mit dem Anmelden mit bekäme. Schlimmer ist aber noch, dass wenn ein Benutzer sich abmeldet bei meiner Methode der nächste Benutzer (den es nichts angeht) die Nachricht bekommt oder eine Exception auftritt, weil ich plötzlich über das Ende der Liste renne. Ich weiß nicht, was schlimmer ist. Das macht den Ansatz der doppelten Liste doch wieder besser. Bei meinem Array of Boolean fehlt der Abgleich, ob die Liste noch mit dem Array übereinstimmt. Serverseitig wird eine Nachricht verworfen, wenn es den Benutzer nicht gibt. Bei der 2. TStringList könnte ich eben gerade beim 2. Durchlauf auf Identität prüfen. Zudem könnte man das evtl. optimieren, indem man abgearbeitete Benutzer aus der 2. Liste wirft und damit das Suchen schneller macht... Ich hätte nicht gedacht, dass das so komplex wird. Gruß, Alex |
AW: Suche in TStrings optimieren
Mooooment!
Dass sich die Liste ändern kann während der Algorithmus läuft war so nicht erwähnt. Und es wäre ein fetter Designfehler. Kann aber auch nur passieren wenn du einen extra Thread hast, der die Liste ändert. Und wenn du so einen Thread hast, leiden beide Algorithmen unter dem gleichen "Problem" dass sie sich nicht auf die Liste verlassen können. Die beste Lösung wäre wohl, wenn der Server (den du ja ohnehin zu haben scheinst) die Liste verwaltet und an die Clients nur die Liste der Benutzer verschickt (und zwar ohne Duplikate) Wenn dann eine Nachricht verschickt werden soll, werden als Empfänger die Benutzernamen angegeben. Der Server löst die Namen dann auf und schickt die Nachricht an alle Empfänger weiter. Der Server hat also eine Liste die jedem Benutzernamen eine Liste an IP's zuordnet (etwa so wie in Post #3) |
AW: Suche in TStrings optimieren
Zitat:
Zitat:
Zitat:
|
AW: Suche in TStrings optimieren
Zitat:
Das mit dem Designfehler ist so eine Sache. Die Software ist ca. 2 Jahre alt. Das Grundkonzept habe ich mir nicht selbst ausgedacht, sondern es stammt von hier. Es läuft problemlos über die genannte Zeit. Das einzige Problem, welches ich seither habe, ist die Frage, ob man Nachrichten an mehrere Clients schicken kann, wenn diese nicht ausgewählt wurden. Auch das klappt vom Prinzip. Der "Designfehler" mit der sich ändernden Liste ist mir während dieses Threads aufgefallen. Das ist m.E. schon eine Leistung, wenn man nicht Informatik studiert hat und einem Fehler auffallen, ohne dass das Programm bereits geschrieben ist, läuft und diese zum Problem werden... Das serverseitige Verschicken ohne Dublikate kommt nicht in Betracht. Zum einen möchte ich alle Benutzer explizit sehen. Sie unterscheiden sich z.B. danach, ob ein Benutzer längere Zeit hindurch den Rechner nicht benutzt hat. Admins können andere tolle Sachen machen als "normale" Benutzer ... Zum anderen soll das mit dem Senden an Dublikate eine zusätzliche Funktion und nicht der Standard werden. alzaimar hat im Grunde recht - die Ausgangsfrage (ohne das lästige Problem sich ändernder Listen) wurde gelöst. Ich denke mir mal eine neue Methode aus, die Suche sicher laufen zu lassen und werde das dann nur der Vollständigkeit halber später hier mal posten. Um die 2. Liste werde ich dabei wohl nicht herumkommen. Danke an alle Mitdenkenden für die Unterstützung Alex |
AW: Suche in TStrings optimieren
Zitat:
Zitat:
Ich habe mir gerade das Tutorial mal angeguckt. Da steht nichts von Thread bis auf das Ende, da steht, dass alles über den Hauptthread abgewickelt wird. Wenn sich dein Programm an dem Tutorial orientiert, dann können also keine anderen Threads in der Liste herumpfuschen. (wenn du nicht weist, was Threads sind, hast du wahrscheinlich keine Threads programmiert) Und solange es keine anderen Threads gibt, kannst du auch sicher sein dass die Liste nicht geändert wird. Weil wenn irgendein Ereignis geschieht, dass veranlassen würde das sich die Liste ändert muss dieses Ereignis warten bis das Programm Zeit findet, es zu bearbeiten. Und somit kann das Ändern der Liste erst nach dem Senden der Nachricht erfolgen. Mein Fazit ist also: Während der Code läuft kann sich die Liste nicht ändern ;) @alzaimar: Ich meinte die Anzahl der Vergleiche - Komplexität war vll. das falsche Wort. Das O() habe ich ja schon weggelassen. Dass die Komplexität lienar ist hatte ich ja weiter oben schon gesagt. Danke ;) |
Alle Zeitangaben in WEZ +1. Es ist jetzt 01:16 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz