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...8-)

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

[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

Delphi-Quellcode:

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:

Zitat von haentschman (Beitrag 1277256)

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:

Zitat von Uwe Raabe (Beitrag 1277283)

Dummerweise liegen die Daten im Array nicht sortiert vor

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

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... :zwinker:

Zitat:

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

...richtig, aber möglich. :P

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. :oops:

[Uwe Raabe]

Zitat:

Zitat von haentschman (Beitrag 1277319)

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. :oops:

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

[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

[Namenloser]

Brauchst du denn dafür wirklich performante Einfüge- und Löschoperationen? Es müsste doch reichen, die Liste nur einmalig zu Beginn zu initalisieren. Da könntest du wirklich einfach ein sortiertes Array nehmen, wäre deutlich einfacher als balancierte Bäume und vom Zeitaufwand her identisch (n Einfügeoperationen im Baum = O(n log n), n-elementiges Array sortieren ebenfalls = O(n log n)). Das Array wäre nicht nur einfacher zu implementieren sondern in der Praxis wahrscheinlich sogar schneller, weil der Overhead geringer ist.

[Zacherl]

Zitat:

Zitat von Namenloser (Beitrag 1277352)

Brauchst du denn dafür wirklich performante Einfüge- und Löschoperationen?

Einfügeoperationen leider schon. Je nach Anwendungsfall (z.b. IDA oder sowas) soll der User ja auch die Möglichkeit haben zur Laufzeit Symbole selbst zu definieren. Bei einem Runtime Debugger auf der anderen Seite, können jederzeit dynamisch DLLs geladen werden, deren Exports man dann zur Symbolliste hinzufügen muss.

[Namenloser]

Es wird dann aber wahrscheinlich gleich immer ein Haufen Symbole auf einen Schlag eingefügt (und dazwischen längere Zeit nichts), oder? Wenn das Array nur einmal pro geladener DLL neu sortiert werden muss, wäre das ja wahrscheinlich auch noch verschmerzbar.

[Dejan Vu]

Zitat:

Zitat von himitsu (Beitrag 1277290)

Zitat:

Zitat von Uwe Raabe (Beitrag 1277283)

Dummerweise liegen die Daten im Array nicht sortiert vor

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

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:

Zitat von Mavarik (Beitrag 1277363)

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.ä.).

[Mavarik]

Zitat:

Zitat von Dejan Vu (Beitrag 1277364)

Einen RB-Baum in seinem Portfolio zu haben, schadet nichts.

Kommt darauf an, ob man "den" selber entwickelt oder sich den Code zusammen Gegoogelt hat.

[Dejan Vu]

Echt? Wieso? Du verwendest doch auch fast ausschließlich Code, der nicht von Dir ist (VCL, WinAPI etc.)

[Mavarik]

Zitat:

Zitat von Dejan Vu (Beitrag 1277366)

Echt? Wieso? Du verwendest doch auch fast ausschließlich Code, der nicht von Dir ist (VCL, WinAPI etc.)

Ich habe im meinem Portfolio aber auch nicht stehen:"VCL der super Komponanten Wrapper für Windows... Powered by Mavarik..."

[Dejan Vu]

Zitat:

Zitat von Mavarik (Beitrag 1277595)

Ich habe im meinem Portfolio aber auch nicht stehen:"VCL der super Komponanten Wrapper für Windows... Powered by Mavarik..."

Und wer hat in seinem Portfolio zu stehen "TAVLTree die Superklasse ... powered by Whoever"? :lol: