Daten auf Einzigartigkeit überprüfen...

[Nelphin]

Zitat:

Zitat von Uwe Raabe

Dann versuch doch mal folgenden Trick - sollte lineare Laufzeit bringen:

Delphi-Quellcode:

//funktionierende procedure von oben

Erstmal vielen Dank!!!!!
bei meinem 120000 -> 20000 beispiel schafft dein code es in 0,8 sekunden! SUPER!
bei einem 2,3 Mio -> 430000 beispiel hats 192 sekunden gedauert, das ist zwar lang aber in anbetracht des datenvolumens ersteinmal vertretbar. (Dauert ja schon fast 20 sekunden das ding zu laden)

deinen trick habe ich nicht verstanden aber er scheint zu funktionieren :) ich werds heut abend nach der arbeit nochmal zeile für zeile durchgehen, aber was

Delphi-Quellcode:

slopt.objects[i]

ist weiss ich nicht und was

Delphi-Quellcode:

idx := slopt.AddObject(sl[i], TObject(i));

macht weiss ich auch net.

aber erstmal vielen herzlichen dank!!! wochenende doch noch gerettet!

[Uwe Raabe]

Es war gestern schon zu spät für ausführliche Erläuterungen, aber nun:

Das Problem mit der sortierten Stringliste ist, daß bei jedem Add die Inizes umsortiert werden können. Daher kann man den von Add zurückgegebenen Index auch nur bis zum nächsten Add gebrauchen.

Statt nur einfach einen String zu der Liste hinzuzufügen, geben ich diesem noch einen Referenzwert, den Index in der Originalliste, mit. Zu diesem Zweck missbrauche ich das Objects-Property der Stringliste, das eigentlich ein TObject hält, aber durch Typecasting auch Integer verkraftet. Der Vorteil der Objects ist, daß sie beim Umsortieren mitgeführt werden.

Bei dupIgnore wird ein bereits vorhandener String bei einem Add nicht in die Liste aufgenommen, insbesondere wird bei AddObject auch das zugehörige Objects-Property nicht geändert. Der nachfolgende Abruf liefert also für den gleichen String auch immer den gleichen Referenzwert zurück. Diesen speichere ich im Index-Array.

Nachdem alle Strings zugefügt wurden, stehen im Index-Array nun allerdings die Werte des jeweiligen Objects-Property des zugehörigen Strings und nicht wie gewünscht der Index in der optimierten Liste. Um dieses Manko zu beheben baue ich einen temporären inversen Index auf, der mir für jeden Referenzwert den zugehörigen Index in slopt liefert. Das geht recht schnell, da hierzu lediglich die slopt durchlaufen werden muss.

Mit diesem temporären Index übersetze ich dann die Einträge des Index-Array in die korrekten Werte.

Übrigens: lineare Laufzeit ist das auch nicht, aber O(n*log n) sollte es schon sein.