Suche nach nächstem gleich-großen oder größeren Wert

[Zacherl]

Hallo zusammen,

ich benötige eine Datenstruktur, die es mir erlaubt möglichst performant nach numerischen Werten zu suchen. Hierbei suche ich allerdings nicht nur exakte Werte, sondern möchte als Fallback (bei nicht-Fund) den nächst-größeren Wert ermitteln.
Eine weitere Anforderung ist, dass ich ebenfalls möglichst performant Werte einfügen und löschen kann.

Ich denke mal, dass ich um balancierte Bäume wohl nicht herumkommen werde. Habt ihr irgendwelche speziellen Vorschläge?

Viele Grüße
Zacherl

[jobo]

Balancierte Bäume wären mein Tipp gewesen erstmal so. Hab da schon lang nichts mehr gemacht.
Heute würde ich sagen, kommt auf den konkreten Anwendungsfall an. Denn wenn ich z.B. weiß, ich krieg immer sortierte Werte rein, weiß ich, ich muss immer umbauen, schlecht.
Der Aufbau Algorithmus im Baum, kann auch (genauso gut?) bei der Suche in einer sortierten Liste angewendet werden.
Also lebt das Ding wie wild, ist es statisch, wie groß wird es, gibt's "downtime" für Reorganisation? Fragen über Fragen...

[haentschman]

Moin...

Ich würde ein TDictionary um deine "dann der nächste" erweitern. Durch die binäre Suche ist TDictionary sehr schnell.

[Blup]

Einen sortierte TList oder TObjectList sollte für Normalfälle schon reichen.
Man sollte halt nicht alle Elemente prüfen, sondern zuerst das mittlere Element.
Abhängig vom Ergebnis halbiert sich die Menge der relevanten Elemente.
Von dieser Hälfte wieder das mittlere Element usw.
Das Insert in eine sortierte Liste funktioniert nach dem selben Prinzip.

So findet man das Ergebnis aus 100000 Elementen z.B. mit 17 Vergleichen.

[Uwe Raabe]

Ich würde ein TArray<T> empfehlen und darauf das TArray.BinarySearch<T> loslassen. Die Doku sagt dazu:

Zitat:

Bei gefundenem Element enthält FoundIndex den nullbasierten Index von Item. Bei nicht gefundenem Element enthält FoundIndex den Index des ersten Eintrags, der größer als Item ist.

Bei XE7 würde man zum Einfügen einfach das Insert nehmen, aber das geht bei XE3 wohl noch nicht.

[Namenloser]

Balancierte Bäume sind was du suchst. Bei B+-Bäumen geht das Finden der nächsten Elemente sogar in O(1).

[jobo]

naja, das ist jetzt in einer sortierten Liste auch nicht so schwer oder?

[Uwe Raabe]

Zitat von haentschman:

Ich würde ein TDictionary um deine "dann der nächste" erweitern. Durch die binäre Suche ist TDictionary sehr schnell.

Ich weiß jetzt nicht, welche TDictionary-Implementation du da gerade vorliegen hast, aber die aus System.Generics.Collection verwendet keine binäre Suche sondern einen Hash-Algorithmus. Dabei wird aus dem Key ein Hash-Wert und aus diesem ein Index in das interne Array gebildet. Dann wird geprüft, ob der Hashwert an dem Index vorhanden ist und ob der Key wirklich passt. Dummerweise liegen die Daten im Array nicht sortiert vor, was eine Suche nach dem nächsthöheren Eintrag höchst ineffizient werden lässt. Man muss dazu nämlich das ganze Dictionary durchsuchen, wenn der Wert nicht vorhanden ist.

Es ist schon so, daß das TDictionary bei geeigneter Hash-Funktion sehr schnell bei der Suche nach einem Key ist, aber für die Suche nach dem nächst-größeren Key ist es denkbar ungeeignet.

[himitsu]

Zitat von Uwe Raabe:

Dummerweise liegen die Daten im Array nicht sortiert vor

Doch, aber halt nach den Hashs und nicht dem Inhalt sortiert.

Man braucht also eine inhaltlich sotierte Liste.
Wenn man Keine hat, dann bringt es nicht viel nur für eine Suche soeine Liste aufzubauen, bzw. wenn immer vor dem Suchen neu sortiert werden muß ... dann dann sollte alles durchlaufen und das suchen, das größer-gleich dem Suchwert ist und kleiner als alles Andere.

[stahli]

Ich habe eine binäre Suche für eine Objektliste genutzt.

Beim Einfügen wird geprüft, ob der Wert (das Objekt) schon existiert.
Sonst wird der Index des nächsten Wertes zurückgegeben.
An die Stelle wird dann der neue Wert eingefügt.

Die Suche ist auch sehr schnell.
Das lässt sich sicher noch etwas anpassen.

http://www.delphipraxis.net/1244470-post11.html

Gibt es dafür noch bessere Lösungen?