Performante sortierte LIste

[Sir Rufo]

Wie schnell muss die denn sein?

Im Anhang ein kleines Beispiel-Projekt mit so einer Ticket-Liste

btn1 füllt die Liste mit 5000 Einträgen und löscht dann wieder 2000 (Termine werden per Random angefordert)
btn2 trägt dann einen einzelnes Ticket ein (Dauer ca. 140 Ticks -> ca. 0.000040s)

Noch schneller?

[hanspeter]

Zitat von Sir Rufo:

Wie schnell muss die denn sein?

Im Anhang ein kleines Beispiel-Projekt mit so einer Ticket-Liste

btn1 füllt die Liste mit 5000 Einträgen und löscht dann wieder 2000 (Termine werden per Random angefordert)
btn2 trägt dann einen einzelnes Ticket ein (Dauer ca. 140 Ticks -> ca. 0.000040s)

Noch schneller?

Vielen Dank erst mal für das Beispiel.
Ich hatte gestern schon mal geantwortet.
Irgendwie werden aber Beiträge verschluckt.
Ich habe bei mir die Terminsuche auf eine binäre Suche umgestellt und damit auch eine erhebliche Leistungssteigerung erreicht.
Über ein TDictionary hatte ich auch schon nachgedacht. Hier ist dann allerdings die Behandlung von mehreren Tickets an einem
Tag etwas schwieriger. Da könnte man dann mit einer verketteten Liste arbeiten.
Also nochmal vielen Dank für die Mühe als Denkanstoss.

Peter

[Sir Rufo]

Was mir aber noch nicht die Frage beantwortet, was jetzt "schnell" und was "langsam" ist
Wenn es einen noch scheeleren Ansatz gibt, wäre es ja lohnenswert diesen hier anzusprechen, bzw. es würde ja schon reichen die Performance von deinem Code zu haben. Dann haben wir alle was davon

[hanspeter]

Zitat von Sir Rufo:

Was mir aber noch nicht die Frage beantwortet, was jetzt "schnell" und was "langsam" ist
Wenn es einen noch scheeleren Ansatz gibt, wäre es ja lohnenswert diesen hier anzusprechen, bzw. es würde ja schon reichen die Performance von deinem Code zu haben. Dann haben wir alle was davon

Ich habe eine zufällige Datumsliste von 10.000 Einträgen erzeugt.
Das gleiche Datum kann mehrfach auftreten.
Diese werden einzeln in einer Liste aufsteigend eingefügt.
Das TDictionary brachte keinen größeren Zeitgewinn, da Daten am gleichen Tag in einer Liste verkettet werden müssen.
Ich habe das nicht voll ausprogrammiert lag etwas über 180 ms.
Das verwenden eines TList , lineares Suchen des Eintrittspunktes und Einfügen benötigte 195 ms.
Das Verwalten als doppelt verkettete Liste benötigte 225 ms.

Überraschend war das Ergebnis des dritten Versuches.
Der Insertpunkt in einem TList wurde sequentiell gesucht, der Eintrittspunkt aber mit 4 Vergleichen eingeschränkt.

Delphi-Quellcode:

m1 := List.count shr 2;
m2 := m1 + m1;
m3 := m2 + m1;

Hier benötigte ich noch 72 ms.

Das ganze mit 100.000 Einträgen.

26:175 sec linear
8:960 sec mit Vergleich.

Ich bestimme die Anzahl der binären Schritte jetzt dynamisch, sodass 10 bis 20 sequentielle Suchschritte übrigbleiben.
Mit 100.000 Einträgen benötige ich dann etwa 3 sec.
Eine rein binäre Suche wäre wohl die schnellste Lösung. Ist jedoch schwierig, da Einträge mehrfach vorhanden sein können oder ganz fehlen.

Peter