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

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