Muss viele Strings vergleichen. Geschwindigkeit...

[DelTurbo]

Hallo,
ich habe ein kleines Problem. Ich habe bis zu 2.000.000 Produkte in CSVDateien. Dort stehen Bestellnummern drin. Bestellnummern die mehrmals vorkommen muss ich zählen. Die Bestellnummern sind 10 Zeichen lang.

Da die Bestellnummern nur 10 Zeichen haben habe ich die in einer TStringlist. Das ist wesentlich schneller als THashedStringList habe ich festgestellt.

Nun zu meinem Problem. Je mehr Bestellnummern ich in der TStringlist habe um so langsamer wird das ganze. Ist ja auch logisch.

Ich Frage mit .IndexOf ob es die Bestellnummer schon gibt. Wenn nicht adde ich die. Hat vielleicht jemand eine andere Idee wie ich schneller abfragen könnte ob es die Nummer schon gibt?

Vielen dank im Voraus

[Neutral General]

Mit THashedStringList sollte ein IndexOf eigentlich schneller sein.
Falls du zufällig doch eine neuere Version als Delphi 2007 benutzt gäbe es da auch noch TDictionary<string, string> (bzw. <string, irgendwas>)

[Uwe Raabe]

Hast du bei der Stringlist nach dem Create

Delphi-Quellcode:

Sorted

auf true gesetzt? Wenn du dann noch

Delphi-Quellcode:

Duplicates

auf dupIgnore setzt, dann kannst du dir die Abfrage auf

Delphi-Quellcode:

IndexOf

auch sparen, da bei einem

Delphi-Quellcode:

Add

nur ein noch nicht vorhandener String zugefügt wird.

[himitsu]

Jupp, wenn StringList sortiert ist, dann nutzt IndexOf eine "optimierte" Suchfunktion,
wenn nicht, dann wird im Worst-Case jedes mal die komplette Liste durchgegangen (jeder einzelne String verglichen).

Mit eine Hashed-StringList muß nur nach dem Hash (Integer) gesucht werden, anstatt alle Strings als Byteweise zu vergleichen.

Das Dictinary ist erstmal sortiert und nutzt auch noch Hashs. (die Hashs sind natürlich sortiert)

[Bernhard Geyer]

Wir haben BTree-Implementierung im Einsatz die uns genau solche Suchen extrem beschleunigt.

[bra]

Zitat:

Zitat von Uwe Raabe (Beitrag 1376697)

Hast du bei der Stringlist nach dem Create

Delphi-Quellcode:

Sorted

auf true gesetzt? Wenn du dann noch

Delphi-Quellcode:

Duplicates

auf dupIgnore setzt, dann kannst du dir die Abfrage auf

Delphi-Quellcode:

IndexOf

auch sparen, da bei einem

Delphi-Quellcode:

Add

nur ein noch nicht vorhandener String zugefügt wird.

Er will ja gerade wissen, OB der Eintrag schon in der Liste war/ist.


Du könntest die TStringList sortieren und auf dupError setzen. Beim Add fängst du den Fehler ab und weißt, ob der Eintrag schon in der Liste war oder nicht.

[himitsu]

Add macht intern auch ein IndexOf (außer bei dupAccept und wenn nicht sortiert, wo er nicht zu prüfen/suchen braucht)

Das Tempo des IndexOf steckt also auch im Add drin.

[freimatz]

Aus meiner Sicht eindeutig: versuche es erst mal mit einem TDictionary<>. Ist wirklich "Delphi 2007 Architect" deine letzte Version? Bestell dir eine neuere oder such dir einen anderen Job.
BTree geht auch, ist aber nicht "out of the Box". Falls doch: auch ich habe auch eine Implementierung incl. hausinternen unit test.

[Daniel]

Zitat:

Zitat von freimatz (Beitrag 1376711)

Bestell dir eine neuere oder such dir einen anderen Job.

Also bitte? Was ist das denn für ein abartiger Kommentar? Man kann sich seine Werkzeuge eben nicht in jedem Projekt frei aussuchen. Du wirst das erkennen, sobald Du selbst ein wenig Lebens- und Praxiserfahrung gesammelt hast. Bis dahin wird man wohl nachsichtig mit Dir sein müssen. :roll:

[Uwe Raabe]

Zitat:

Zitat von bra (Beitrag 1376706)

Er will ja gerade wissen, OB der Eintrag schon in der Liste war/ist.

Na ja, er will das wissen, um zu entscheiden, ob er den Eintrag hinzufügen soll oder nicht. Mit

Delphi-Quellcode:

dupIgnore

erübrigt sich das eben. Das macht intern nämlich genau das.

Zitat:

Zitat von DelTurbo (Beitrag 1376694)

Ich Frage mit .IndexOf ob es die Bestellnummer schon gibt. Wenn nicht adde ich die.

[jobo]

Ich würde mich da nicht mit codieren quälen.

Die CSVs in einer DB einbinden (meinetwegen auch importieren) und dann bequem per SQL abfragen. Zählen, Suchen, Dubletten, Lang, Kurz, Vergleichen, whatever..
auch ein neues Gesamtergebnis kann man dann wieder rausgeben oder aber eine Liste mit neuen Einträgen

[DelTurbo]

Zitat:

Zitat von Uwe Raabe (Beitrag 1376697)

Hast du bei der Stringlist nach dem Create

Delphi-Quellcode:

Sorted

auf true gesetzt? Wenn du dann noch

Delphi-Quellcode:

Duplicates

auf dupIgnore setzt, dann kannst du dir die Abfrage auf

Delphi-Quellcode:

IndexOf

auch sparen, da bei einem

Delphi-Quellcode:

Add

nur ein noch nicht vorhandener String zugefügt wird.

Ja, habe ich alles. Suchen muss ich aber, weil ich wissen muss ob die Nummer schon da ist. Ich muss mitzählen wie oft die in den CSVs vorkommt. Deswegen brauch ich das IndexOf.

Und ja, ich habe immer noch Delphi 2007.

Die Idee mit einlesen in eine DB kann ich mal umsetzen. Aber ich glaube nicht das es schneller wird.

[DelphendeElfen]

Aber dann könntest du doch auch einfach die Strings in die StringList adden und wenn ein Duplikat auftaucht bekommst du einen Fehler den du auswerten kannst. Oder verstehe ich da etwas falsch?

Zitat:

Note: For sorted lists, Add will raise an EListError exception if the string S already appears in the list and Duplicates is set to dupError. If Duplicates is set to dupIgnore, trying to add a duplicate string causes Add to return the index of the existing entry.

[DelTurbo]

Zitat:

Zitat von DelphendeElfen (Beitrag 1376720)

Aber dann könntest du doch auch einfach die Strings in die StringList adden und wenn ein Duplikat auftaucht bekommst du einen Fehler den du auswerten kannst. Oder verstehe ich da etwas falsch?

Das ist noch eine Idee. Die werde ich sofort mal versuchen. Wobei ich denke das "intern" das .Add ja auch nachsehen muss ob es die Nummer schon gibt.

Ich habe es gerade mal auf THashedStringList umgestellt. Das ist wesentlich langsamer.

[bra]

Zitat:

Zitat von Uwe Raabe (Beitrag 1376714)

Zitat:

Zitat von bra (Beitrag 1376706)

Er will ja gerade wissen, OB der Eintrag schon in der Liste war/ist.

Na ja, er will das wissen, um zu entscheiden, ob er den Eintrag hinzufügen soll oder nicht. Mit

Delphi-Quellcode:

dupIgnore

erübrigt sich das eben. Das macht intern nämlich genau das.

Nicht ganz ;)

Zitat:

Bestellnummern die mehrmals vorkommen muss ich zählen.

Darum mein Vorschlag mit dem dupError und den Fehler abfangen zum Zählen.

[DelTurbo]

Zitat:

Zitat von bra (Beitrag 1376724)

Darum mein Vorschlag mit dem dupError und den Fehler abfangen zum Zählen.

Ich habe es gerade eingbaut. Es ist leider langsamer als IndexOf.

[jobo]

Wie oben geschrieben, das Ganze in der Datenbank dürfte schnell und bequem sein. Selbst wenn man die Daten nicht importiert, sondern der DB nur die CSV "hinlegt" und bekannt gibt. Geht für firebird, postgres, oracle und sicher auch mssql.
Selbst mit sqlite wäre es ein 3 Zeiler, wenn man nicht extra eine dicke DB anwerfen will.
Dann noch notwendige Indizes spendieren und alles ist toll. sqlite hätte den Charme, dass man je CSV File eine eigene sqlite Datei nutzen könnte, mit anderen per dblink koppeln usw.
Man kann also munter mit den Daten jonglieren.

[himitsu]

Zitat:

Zitat von DelTurbo (Beitrag 1376721)

Wobei ich denke das "intern" das .Add ja auch nachsehen muss ob es die Nummer schon gibt.

siehe #7 zusammen mit #4

IndexOf in StringList sortiert > bei 1000 Einträgen bis zu 10 String-Vergleiche
IndexOf in StringList unsortiert > bei 1000 Einträgen alle 1000 String-Vergleiche, wenn nicht enthalten (durchschnittlich 500 wenn vorhanden)

"diese" THashedStringList ist gut beim Suchen, aber extrem schlecht beim Hinzufügen/Ändern.
Du änderst aber sehr oft und suchst verhältnismäßg selten.

[DelTurbo]

Hi,
ist vielleicht untergegangen. Sorted ist True. Hatte ich in #12 beantwortet. Aber mich schlecht ausgedrückt.

[DelTurbo]

Hi,
ich denke mal, das wenn man so eine Datenmenge hat, es nicht im Sekunden Bereich liegen kann. Damit muss man wohl leben. Trotz i7 mit 4,4Ghz im Turbomode.

Ich habe das nun so abgewandelt das ich einen 32Bit hash errechne und dann mit TIntegerlist arbeite. Das ist annehmbar schnell.

Link zu TIntegerlist

Vielen dank an alle die geholfen haben. :thumb:

[jaenicke]

Ich habe gerade einmal mit FireDAC eine Speichertabelle erstellt mit ebenfalls 2 Millionen Einträgen. Dort dauert die Filterung nur Millisekunden...

Es gibt ja sicher auch Fremdimplementierungen für solche Speichertabellen, die auch unter Delphi 2007 funktionieren.

[Uwe Raabe]

Zitat:

Zitat von jaenicke (Beitrag 1376748)

Es gibt ja sicher auch Fremdimplementierungen für solche Speichertabellen, die auch unter Delphi 2007 funktionieren.

Wieso fremd? Das müsste

Delphi-Quellcode:

TClientDataSet

doch auch schaffen.

[jaenicke]

Das ist aber um Größenordnungen langsamer, weshalb wir davon auch weg sind.

Die schnellste Lösung wäre allerdings wahrscheinlich ein eigener Datenbankserver, der entsprechende Cache Möglichkeiten und so weiter hat. Wenn das denn in Frage kommt.