Autor Beitrag
KidPaddle
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 351

WinXP,Linux
D7 Prof, XE7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1068

Win 2000, Win XP
Delphi 7, Delphi 2005
BeitragVerfasst: Do 13.10.05 13:54 
Du könntest verkettete Listen benutzen. Das Einfügen sollte dabei recht zügig gehen.

Lg Martin
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1068

Win 2000, Win XP
Delphi 7, Delphi 2005
BeitragVerfasst: Do 13.10.05 14:12 
Grrr... hab das sortieren überlesen. :oops:
KidPaddle Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 351

WinXP,Linux
D7 Prof, XE7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 18:40 
user profile iconKidPaddle 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 351

WinXP,Linux
D7 Prof, XE7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 351

WinXP,Linux
D7 Prof, XE7
BeitragVerfasst: Fr 14.10.05 07:35 
Vielen Dank für deine Implementierung, werde diese ausprobieren.

Gruß
Thomas