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

[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?

[haentschman]

Zitat:

Es ist schon so, daß das TDictionary bei geeigneter Hash-Funktion sehr schnell bei der Suche nach einem Key ist

...das meinte ich so. Binär war der Verschreiber...

Zitat:

aber für die Suche nach dem nächst-größeren Key ist es denkbar ungeeignet.

...richtig, aber möglich.

Zitat:

Ich würde ein TArray<T> empfehlen und darauf das TArray.BinarySearch<T> loslassen.

...ist natürlich besser. Wie soll man das finden wenn man nicht weis das es sowas gibt.

[Uwe Raabe]

Zitat von haentschman:

Zitat:

Ich würde ein TArray<T> empfehlen und darauf das TArray.BinarySearch<T> loslassen.

...ist natürlich besser. Wie soll man das finden wenn man nicht weis das es sowas gibt.

Liest du denn nicht bei jedem neuen Delphi die mitgelieferten Sourcen?

[mkinzler]

Zitat:

Zitat:
aber für die Suche nach dem nächst-größeren Key ist es denkbar ungeeignet.
...richtig, aber möglich.

Das käme dann aber eine Suche in einer/einem nicht sortierter/m Liste/Array gleich, dann würde ich gleich eine/einen solche/n nehmen.

[Zacherl]

Vielen Dank schonmal für eure zahlreichen Antworten. Ich konkretisiere mal ein wenig:

Ich benötige diese spezielle Art der Suche für einen Symbol Resolver (das Ding, was in einem Disassembler numerische Adressen in SymbolName + Offset umwandelt). Hat man beispielsweise ein bekanntes Symbol an Adresse 0x1000 und der Resolver bekommt jetzt Adresse 0x1010 übergeben, dann wäre die Ausgabe SymbolName+0x10. Üblicherweise wird man wohl versuchen die meisten Symbole schon vor dem ersten Resolvevorgang "einzutragen", aber es kann durchaus passieren, dass nachträglich noch eine ganze Reihe von Adressen hinzugefügt werden muss.

Ich werde dann mal wohl mal ein wenig mit binärer Suche und B+ Bäumen rumspielen

Viele Grüße
Zacherl

[Dejan Vu]

Zitat von 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.

Nein. Hash modulo Listengröße = Index. Gleicher Index => Kollision => Verschiedene Strategien.

B+ Bäume sind hierfür imho falsch, denn sie basieren auf festen Speicherblöcken (z.B. Dateiblöcken) und sind nichts anderes als binäre Arrays, die als N-ärer Baum untereinander hängen. Für die In-Memory Suche ist das imho overkill.

Binäre Listen sind knackig und kurz in der Implementierung, dafür O(n) beim Einfügen (Listeninhalt muss verschoben werden). Das geht aber sehr schnell.

Binäre Bäume (RB oder AVL) komplexer in der Umsetzung, aber dafür für diesen Fall optimal.

Eine SkipList wäre noch eine Alternative.

Es gibt fertige Lösungen, auch hier im Forum, z.B. hier :
http://www.delphipraxis.net/55493-ve...eispielen.html

[Mavarik]

Die eigentliche Frage lautet wie viel zeit hast Du fürs Sortieren übrig..

Kommen die Werte einzeln rein...
- Mit Intervall-Schachtelung die Position suchen
- Mit einem Move Platz machen und einfügen

Kommen viele Werte auf einmal rein
- QSort drüber fertig
- Suchen wieder mit Intervall-Schachtelung...

Wahrscheinlich kann man in einer eigenen Implementierung einige Taktzyklen sparen, aber i.d.R. "reichen"
auch die Bordmittel.

Mavarik

[Dejan Vu]

Zitat von Mavarik:

Wahrscheinlich kann man in einer eigenen Implementierung einige Taktzyklen sparen, aber i.d.R. "reichen" auch die Bordmittel.

Das stimmt. Ich vertrete die Ansicht, das für die Lösung eines Problems immer die beste Möglichkeit gewählt werden soll. Was das 'beste' ist, muss man dann abwägen. Teil der Abwägung ist natürlich 'Kosten/Nutzen', da hast Du vollkommen recht. Allerdings: Einen RB-Baum in seinem Portfolio zu haben, schadet nichts. Dann hat man immer etwas Sauschnelles zur Hand, wenn man vor einem ähnlichen Problem steht (Daten müssen sortiert vorliegen, nächstgrößeren Wert ermitteln o.ä.).