Große Strings schnell auf Inhalt einer Zeichenkette prüfen?

[romber]

Hallo!

Gibt es eine ressourcenschönende schnelle Methode, sehr große Strings (wie in meinem Fall eine TStringList mit über 250.000 ziemlich langen Einträgen) auf Existenz einer bestimmten Zeichenkette zu prüfen? Mit pos geht das zwar auch, so richtig schnell ist das aber nicht.

Danke!

[SirThornberry]

also pos ist bereits in assembler programmiert und is somit wohl nur sehr schwer noch zu optimieren (wenn überhaupt möglich). Wie genau verwendest du es in Zusammenhang mit einer Stringlist? Suchst du in der Stringlist nach kompletten Einträgen? Wenn du suchst welcher Index in der Stringlist mit einer bestimmten zeischenkette los geht hilft es schon die Stringlist zu sortieren und dann den algorythmus darauf anzupassen, ansonsten wenn es darum geht einen teilstring an beliebiger Stelle zu finden dann bleibt nur übrig das du alle items der Stringliste durchgehst und das dauert nunmal lange..

[romber]

Danke für schnelle Antwort!

Ich habe Einträge, die aus Zahlen bestehen. Hier ein kleiner Abschnitt des Inhaltes:

...
33670903
33670905
33670899
33670911
33670915
33670904
33670919
33670920
33670912
33670916
33670921
33670918
...

Mann kann da erkennen, dass die Zahlen immer höher werden, aber nicht immer in der richtigen Reihenfolge sind. Ich möchte eigentlich nur sehr schnell prüfen, ob der eintrag bereits in der Liste ist, bevor ich diesen hinzufüge. Kann man da was optimieren?

[Ultimator]

Und wenn du mit IndexOf hergehst, und den zurückgegebenen Index auf -1 überprüfst?

[alzaimar]

Wenn Du statt einer Stringlist einfach einen String nimmst (und nicht einfach sl.Text verwenden, weil lahm), dann sollte Boyer-Moore deinen Anforderungen genügen. Wenn der String nur am Anfang einer Zeile stehen kann, wäre eventuell eine individueller Algorithmus schneller. Allerdings berücksichtigt Boyer-Moore auch diesen Sonderfall (man sucht dann einfach nach "#10#13FooBar").

Besorge Dir FastStrings.Pas von hier
http://www.droopyeyes.com/default.as...owProduct&ID=4

Alternativ empfehle ich mein TStringDictionary, eine dynamische Hashliste. Es fügt 100.000 Strings inkl. überprüfung in 600ms ein. TStringList ist 2-100x langsamer (je mehr Strings, desto schlimmer). Dafür verzichtest Du auf eine Sortierung. Wenn Dir das schnurz ist, verwende mein Wörterbuch.

[SirThornberry]

wenn es nur zahlen sind würde ich nicht die Stringlist nehmen sondern direkt TList und anstelle von Pointern deine Integer da rein hängen (casten). Dann das ganze noch sortieren und dann solltest du mit dem Quicksortalgorythmus recht schnell herausfinden ob der Eintrag schon vorhanden ist. Falls du bei der Stringlist bleibst so ist dort Sorted schon implementiert und auch IndexOf.
Wenn sorted auf True ist und "duplicates" auf "dubExcept" so bekommst du einen Fehler wenn du einen vorhandenen Eintrag adden willst (das ganze in Try-Except) und du solltest recht schnell fertig sein.

[alzaimar]

Auch da sind Hashlisten einfach schneller. Ein TIntegerDictionary ist im geposteten Sourcecode enthalten. Er ist gegenüber einer TList, Sortieren und Binarysearch auch um den schon erwähnten Faktor schneller.

Das 'Suchen' von Daten sollte und muss keine Zeit kosten. Natürlich immer relativ. Bei 100.000.000.000 Datensätzen darf das Suchen ruhig mal mal 100ms dauern, da doch einige Festplattenzugriffe nötig sind (bei einem B-Baum wären das ca. 3 Zugriffe a 8kb). Bei bis zu 10.000.000 Datensätzen, die ich ohne Probleme im Speicher halten kann, ist eine Hashliste optimal

[romber]

Ich wollte die vom Alzaimar entwickelte TIntegerDictionary probieren und habe ihn um einen Beispiel gebeten. Er hat mir die Beispielcode und die bereits erstellte EXE-Datei geshickt. Wenn man die Datei ausführt, wird in einem Memo-Feld angezeigt, wie lange den Suchprocess gedauert hat. Und das geht wirklich verdammt schnell. Ich habe jetzt aber ein anderes Problem: sobald ich die Code ins Delphi lade und ohne etwas zu ändern von dort ausführe, wird das Programm um fast deppelt langsammer! Woran liegt das?

[himitsu]

Führe dein Programm mal ohne Debugger aus ... also nicht direkt vom Delphi aus.
Der Debugger bremst ein wenig.

Ich hatte z.B. mal den Fall, daß ein reiner ASM-Code im Debugger mindestens 20-mal Langsamer ablief, als ohne.





Du könntest eventuell auch mal nach meinem SearchSameFiles (unter Open Source) suchen, dort werden zwar Dateien verglichen, aber man kann den Code auch leicht dahingehend verändern, daß da Strings verglichen werden.

Es wäre zumindestens ein "nettes" Beispiel für dich.

Dort wird mit 'ner Hashliste gearbeitet und bei gleichem Hash sicherheitshalber nochmals die Dateien(oder Strings) verglichen und da die Hashs nicht sortiert sind gibt es noch 'ne abgeänderte Pos-Funktion zum suchen eines Hashs.

PS: wunder dich aber nicht, wenn sich das Programm so nicht compilieren läßt ... dir fehlen da bestimmt noch ein paar Dateien eines anderen Projekts, aber wenn nötig kann ich dir ja die entsprechenden Funktionen/Proceduren noch zukommen lassen (und einige davon sind auch schon in der DP veröffentlicht)

[sniper_w]

Bei einer Sortierte Liste ist Binary Search seeeehr schnel....
Man braucht maximal 32 mal abzufragen in einer List von 2^32 Beiträgen um eine richtige Antwort zu bekommen. Da sollte es Geschwindigkeitsvorteile schon geben...

google.com