Suche in TStrings optimieren

[Schwedenbitter]

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:

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;

Mein Problem ist nun folgendes:
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

Gruß, Alex

[jfheins]

Zitat:

Kann man das irgendwie optimieren?

Ja.

Da die Liste sortiert ist, brauchst du an dieser Stelle:

Delphi-Quellcode:

      For J:=0 To Pred(Clients.Count) Do
        SendTo[J]:=(SendTo[J] Or (Clients.Items[J] = Current));

Nicht alle durchgehen, sondern nur ab dem aktuellen einmal hoch und einmal runter solange der Text gleich bleibt.

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;

[s.h.a.r.k]

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:

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)

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.

[Schwedenbitter]

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 Clients.Items[I] immer mit Clients.Items[J] statt wie ich mit Current vergleichst. Geht das so schneller?
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:

  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;

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.
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

[jfheins]

Zitat von Schwedenbitter:

@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.

Sollte nicht allzu schlimm sein. Immerhin ist die Komplexität nur noch linear. (Also O(n) - wenn dir das was sagt) Und die paar tausend Durchläufe schafft die CPU schon in ausreichend kurzer Zeit
Und weniger komplex als linear geht's (in diesem Fall) nicht

Zitat:

Mir war auch aufgefallen, dass Du Clients.Items[I] immer mit Clients.Items[J] statt wie ich mit Current vergleichst. Geht das so schneller?

Vermutlich ist es einen Hauch langsamer. (Insbesondere wenn Items[] einen Getter hat)
Aber es war ja klar was gemeint war.

Zitat:

Ich selbst hatte aus diesem Grund bei meinen Überlegungen die For- durch eine While-Schleife ersetzt. Das ganze sieht bei mir jetzt so aus:

Gute Idee.

Zitat:

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.

Die Theorie ist noch nicht am Ende - denn sie besagt dass dieser Ansatz schlechter ist als der obige!
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

[Schwedenbitter]

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

[jfheins]

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)

[alzaimar]

Zitat von Schwedenbitter:

Kann man das irgendwie optimieren?

Die Frage ist doch schon beantwortet:

Zitat von s.h.a.r.k:

Mir fällt dabei immer Hashing und auftretende Kollisionen ein... Du hast ja einen eindeutigen Namen "Abraham" und mehrere Clients dazu. ...

Das ist der schnellste Ansatz mit einer Komplexität von O(1). Besser gehts nicht.

Zitat von jfheins:

...hat eine Worst-Case-Komplexität von 3n (Wenn alle Einträge anders sind und alle ausgewählt)...

Äh. Nö. Komplexität ist O(n), egal ob worst-case oder nicht. Die Konstante fällt bei der Komplexitätsbetrachtung weg.

[Schwedenbitter]

Zitat von jfheins:

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.

Asche auf mein Haupt
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

[jfheins]

Zitat von Schwedenbitter:

Asche auf mein Haupt

Nun mal nicht so vorschnell ... die schöne Asche

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...

Es ist ja noch nicht geklärt ob es diesen "Designfehler" überhaut gibt. Ichhabe ja gesagt: "es wäre ein fetter Designfehler".
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