Zitat:
Wie kann ich erfahren wie schnell jeder einzelne Lösung ist? Sind das "gewaltige" unterschiede? Oder minimale?
Je nach Datenmenge sind es gewaltige Unterschiede, vom schlechtesten zum besten sortiert
1.) TStringList
2.) IndexOf() ohne binärer Suche
3.) Pos()
4.) BoyerMoorePos()
5.) IndexOf() aber mit binärer Suche, statt wie oben einfach linear
6.) Trees wie mein DAWG
7.) Hash-Vergleich
Noch ein par Bemerkungen:
7.) Hash-Vergleich meint KEINE Hash-StringListe oder so ein Quatsch. Man sucht eine geeignetes Prüfsummenverfahren das für alle zu suchenden String in der Liste eine eindeutige Zahl liefert, zb. eine 32Bit Zahl. Diese Zahlen erzeugt man einmalig und kann dann so sehr sehr effizient vergleichen
Delphi-Quellcode:
case Pruefsumme(Bezeichnung) of
$12345678: ;
$AB450CDE: ;
$DFFFFF12: ;
// usw. usf.
end;
Dh. in dieser Methode wird nur ein String real bearbeitet, nämlich der Suchstring Bezeichnung wir byteweise durch Prüfsumme umgewandelt. Danach gibnt es KEINE weiteren realen Stringvergleiche mehr.
Eine Hash-Liste empfehle ich niemals, da diese immer nur auf bestimmte Probleme bezogen ihren Aufwand lohnen.
Trees benötigen fast immer mehr Speicher sind aber abgesehen von obiger Prüpfsummen-Methode die schnellste Lösung.
Pos() ist schnell implementiert aber schlecht zu warten und nicht sonderlich schnell. Aber weitaus sachneller als
eine TStringList jedesmal zu erzeugen, dann mit dem langsammen CommaText oä. die Liste zuzuweisen, dann vielleicht noch sortieren und dann erst darin suchen, und dann die Liste wieder freigeben. Uff, schon beim Schreiben dieses Satzes wird mir schlecht.
Die Beste Lösung bei nur wenigen Strings in der Liste dürfte die 2. von Mabuse sein -> IndexOf() habe ich si mal genannt. Hier erzeugt der Compiler schonmal eine schöne hardcoded Datenstruktur aller Strings im Codesegement. Also keinerlei Allokationen oder Deallokationen dieser "Liste" mehr notwendig. Sortiert man diese Strings noch von Hand und benutzt in IndexOf() eine binäre Suche so ergibt sich ein ziemlich effizientes Verfahren das auch bei zb. 1024 Strings nur 11 Vergleiche benötigt.
Aber es würden eben noch 11 * 2 Stringzugriff für diese Vergleiche notwendig sein, bei der TStringList wären dies ca. 512 pro Suche. Bei den Hash-Prüfsummen würde man denoch nur 1 String umwandeln in einen 32Bit Wert und diesen dann vergleichen in der CASE OF Abfrage, würde ja bei den anderen Verfahren ebenfalls notwendig sein.
Das Problem bei der Hash-Prüfsummen-Methode ist es das man erstmal eine geeignete Funktion finden muß die bei allen Strings eine wirklich eindeutige Prüfsumme erzeugt. Wenn man davon ausgehen kann das der Wert in Bezeichnung nur aus Werten bestehen kann die in der zu suchenden Liste vorkommen dann ist das noch effizient möglich, sonst aber nicht.
Wie gesagt: am elegantesten ist die const Array[] Methode, rein schon vom sauberen Eindruck den der Source macht und von der sich ergebenden Performance ist sie ein supere Kompromiss. Um längen besser als diese elende TStringList Rechnereien. (hab den Eindruck das es ausreichend ist einem Delphicoder die TStringList zu erklären, mehr benötigt er nicht
)
Gruß Hagen