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

[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

[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 von Namenloser:

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