| Autor |
Beitrag |
KidPaddle
      
Beiträge: 351
WinXP,Linux
D7 Prof, XE7
|
Verfasst: Do 13.10.05 13:50
Hallo,
in einer Liste werden Name und die dazugehoerigen Objekte gespeichert. Die Namen sind eindeutig, es existieren kein Duplikate. Bisher legen wir diese Daten in einer sortierten TStringlist ab. Nun hat sich ergeben, das das einfügen neuer Objekte in die Liste bei grosser Objektanzahl extrem langsam wird, d. h. die Einsortierung dauert sehr lange.
Wir haben nach alternativen gesucht und sind dabei auf mehrere Hash - Listen gestossen, die aber genau die gleiche Krankheit hatten. Kennt jemand eine Alternative. Gegoogelt habe ich schon, aber nichts brauchbares gefunden.
Gruß
Thomas
|
|
Martin1966
      
Beiträge: 1068
Win 2000, Win XP
Delphi 7, Delphi 2005
|
Verfasst: Do 13.10.05 13:54
Du könntest verkettete Listen benutzen. Das Einfügen sollte dabei recht zügig gehen.
Lg Martin
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Do 13.10.05 14:10
Wenn hintereinander viele Daten in die Liste eingefügt werden sollen, empfiehlt es sich, die Daten zunächst unsortiert anzuhängen, und nach dem Einfügen aller Daten die Liste zu sortieren.
Über welche Größenordnung reden wir überhaupt? 10.000? 100.000? 1.000.000?...
@Martin1966: Das mit den verketteten Listen ist nicht richtig, wenn die Daten sortiert vorliegen sollen.
_________________ We are, we were and will not be.
|
|
Martin1966
      
Beiträge: 1068
Win 2000, Win XP
Delphi 7, Delphi 2005
|
Verfasst: Do 13.10.05 14:12
Grrr... hab das sortieren überlesen. 
|
|
KidPaddle 
      
Beiträge: 351
WinXP,Linux
D7 Prof, XE7
|
Verfasst: Do 13.10.05 18:28
Die Anzahl an sich ist nicht viel, so zwischen 10.000 und 20.000. Das Problem ist, das suchen und einfügen sich abwechseln und nicht erst eingefügt und dann nur noch gesucht wird.
Gruß
Thomas
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Do 13.10.05 18:40
KidPaddle hat folgendes geschrieben: | | Wir haben nach alternativen gesucht und sind dabei auf mehrere Hash - Listen gestossen, die aber genau die gleiche Krankheit hatten. |
Von welcher Krankheit redest Du? Meine Hashliste, die ich Dir gerne zur Verfügung stelle, kennt keine Krankheiten, ausser die, das sie beim Vergrößern kurz mal ein paar ms braucht, das fällt aber insbesondere bei der Geschiwindkeit beim Einfügen und Suchen nicht ins Gewicht. Leider kann man die Einträge nicht sortiert ausgeben, so gesehen, eher ein Handicap als eine Krankheit. Unsortiert ist es kein Problem, aber sortiert eben. Solange es ums einfügen und finden geht, sind dynamische Hashlisten aber die erste Wahl.
Dann gäbe es da noch den guten alten B-Baum oder einfach eine Skiplist, die sich bei den 20.000 Einträgen auch noch recht ordendlich schlägt.
Was darfs sein?
_________________ Na denn, dann. Bis dann, denn.
|
|
KidPaddle 
      
Beiträge: 351
WinXP,Linux
D7 Prof, XE7
|
Verfasst: Do 13.10.05 19:22
Wir haben mehrere Implementierung von Hash - Listen ausprobiert. Die Borland eigene, die aus den Jedis und noch einige andere Units. Alle wurden mit der Zeit exponentiell langsamer. Das lag daran, das die Hash - Daten mit jedem einfügen eines neuen Wertes von allen Strings neu aufgebaut wurden.
Eine sortierte Ausgabe brauche ich nicht. Es geht nur darum zu erkennen, ob ein bestimmter Wert schonmal zuvor gefunden wurde, wenn das passende Objekt auszulesen, wenn nicht wird ein neues Objekt eingefügt. Die Sortierung war nur zum schnellen Suchen bekannter Werte gedacht.
Was kannst Du mir empfehlen?
Gruß
Thomas
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Do 13.10.05 20:27
Meine Stringdictionary (eine Hashliste), nur das daran nichts Exponentielles ist...
Ich verstehe auch nicht, wie man so etwas exponentiell hinbekommt, eine Hashliste ist und bleibt linear. Meine Implementierung vergrößert sich allerdings von alleine, sobald ein Füllgrad von 66% erreicht ist. Am Vergrößerungsfaktor (2), am Schwellenwert für die Vergrößerung an der ursprünglichen Größe (997 Elemente), und vor allen Dingen an der Hashfunktion (hier:CRC) kann man noch drehen.
Vergleich: Testen ob schon vorhanden und einfügen von
10.000 Strings : 70ms
100.000 Strings : 760 ms
1.000.000 Strings : 9820 ms
Im Vergleich dazu: TStringlist (Sorted = True, Duplicate = dupIgnore)
10.000 : 160 ms
100.000 : 13390 ms
1.000.000 Strings : nicht getestet, dauert zu lange
Vielleicht gibts ja jemanden, der hier noch was rausholen kann/will?
Einloggen, um Attachments anzusehen!
_________________ Na denn, dann. Bis dann, denn.
|
|
KidPaddle 
      
Beiträge: 351
WinXP,Linux
D7 Prof, XE7
|
Verfasst: Fr 14.10.05 07:35
Vielen Dank für deine Implementierung, werde diese ausprobieren.
Gruß
Thomas
|
|
|