@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