Performante sortierte LIste

[hanspeter]

Hallo,

ich baue im Moment so eine Art Ticketsystem.
Ein Ticket kommt zu einem willkürlichen Zeitpunkt an.
Es hat eine unterschiedliche zeitliche Länge und soll auf einer Zeitleiste ab einem bestimmten Datum eingeordnet werden.
In der zeitlichen Folge entstehen Belegungslücken.
Kommt ein neues Ticket an, dann wird ab dem gewünschten Termin eine Lücke gesucht, in welche das Tiket passt. Wird keine gefunden, dann wird es am Ende der Zeitleiste angehängt.

Für die Speicherung verwende ich ein generic-TList. Jedes Tiket wird durch eine Klasse dargestellt.
Ich suche jetzt das gewünschte Datum linear und dann vergleiche ich Anfangs-Endzeit aller folgenden Tikets um eine zeitliche Lücke zu finden.
Habe ich eine Lücke gefunden, dann füge ich die Classe an der Stelle ein.
Hier geht es um sehr große Mengen. ca 3000 Tikets in etwa 500 bis 1000 Vorgängen.
Ich hatte bemerkt das es performanter ist, das neue Tiket an die Liste anzuhängen und dann nach dem Datum zu sortieren.
Bei etwa 3000 Datensätzen kippt aber die Performance und das Einfügen wird schneller.
Das Sortieren in generischen Listen scheint weniger performant zu sein als im TList.
Ich habe dann versucht in einer Liste nicht die Tikets selbst, sondern die Lücken in der Belegung der Zeitachse zu speichern. Statt Anfangs-Endzeit zu vergleichen, suche ich jetzt in einer Liste eine passende Zeitlücke und modifiziere dann diese.
Das bringt zwar etwas Zeitgewinn aber nicht im erwarteten Umfang.
Es scheint als ob ein TList der Flaschenhals ist.
Ich denke im Moment über eine Hashliste oder eine verkettete Liste nach. Hat hier wer Erfahrung wie die Performance im Vergleich zu einem TList ist oder hat wer eine Idee wie man eine performantere Lösung dieses Problems erreichen kann?

Gruß Peter

[XHelp]

Im Grunde kannst du dir ja was von dem Dateisystem abgucken... Läuft aber verkettete Listen hinaus.
2 Listen: die eine verwaltet die Daten, die andere die Freiräume, wobei die Freiräume einen Zeiger auf den Platz in der Datenliste halten.
Wenn du das ganze auch noch mit Hashfunktion abhängig von der Zeit verknüpfst, dann weißt du ja an welcher Stelle du einsteigen musst, so dass der Vorgang dadurch beschleunigt wird.

[Sir Rufo]

Wenn du dir in einer weiteren Liste das Datum merkst, dann kannst Du direkt an das Datum springen und erst die Datensätze ab da durchsuchen.

Code:

ListByDate
- Datum
- TicketList

Sortieren würde ich dann auch nur noch diese Datumliste und die darin enthaltene TicketList.
Dadurch wird die jeweils zu verwaltende (sortierende) Menge erheblich kleiner

[hanspeter]

Mit einer getrennten Datumsliste habe ich es bereits probiert. Das brachte kaum einen Performance-Gewinn.
Ich bin gerade dabei eine doppelt verkettete Liste aufzubauen und diese über das Datum zu indizieren.
Die Tikets sind ohnehin bereits im Speicher.
Ich spare dann den Verwaltungsaufwand von TList.
Mal sehen wieviel das bringt.

Gruß Peter

[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