Ich habe eine Liste von Werten (1-dimensional) und ich würde gerne die beste Datenstruktur / Algorithmus zum Finden der nächsten zu einem Abfragewert, den ich habe, kennen. Die meisten Lösungen (alle?), Die ich für Fragen hier gefunden habe, sind für 2 oder mehr Dimensionen. Kann mir jemand den Ansatz für meinen Fall vorschlagen?
Mein Instinkt sagt mir, dass ich die Daten sortieren und die binäre Suche irgendwie verwenden soll. Übrigens, es gibt keine Begrenzung für die Konstruktion oder die Einfügezeit für irgendeinen benötigten Baum, also kann wahrscheinlich jemand einen besseren Baum als nur eine sortierte Liste vorschlagen.
Wenn Sie etwas schneller als O (log (n)) benötigen, das Sie leicht mit einem sortierten Array oder einem binären Suchbaum erhalten, können Sie ein van Emde Boas Baum . vEB-Bäume geben Ihnen O (log (log (n))), um nach dem nächsten Element auf beiden Seiten zu suchen.
Wenn die Einfügezeit irrelevant ist, ist die binäre Suche in einem sortierten Array der einfachste Weg, die Abfragezeit O (log N) zu erreichen. Jedes Mal, wenn ein Gegenstand hinzugefügt wird, sortiere alles. Führen Sie für jede Abfrage eine binäre Suche aus. Wenn eine Übereinstimmung gefunden wird, geben Sie sie zurück. Andernfalls sollte die binäre Suche den Index des Elements zurückgeben, an dem er eingefügt werden sollte. Verwenden Sie diesen Index, um die zwei benachbarten Elemente zu überprüfen und festzustellen, welche davon näher am Abfragepunkt liegt.
Ich nehme an, dass es Lösungen mit O (1) Zeit gibt. Ich werde versuchen, an einen zu denken, der nicht zu viel Speicherverbrauch mit sich bringt ...
Sortieren Sie die Liste und verwenden Sie die binäre Suche, um das gesuchte Element zu finden, und vergleichen Sie dann Ihre linken und rechten Nachbarn. Sie können ein Array verwenden, das O (1) Zugriff hat.
Etwas wie:
%Vor%Das ist O (n log n), das sich amortisiert, wenn Sie viele Look-Ups durchführen wollen.
EDIT: Dafür müssten Sie die Sortierung dieser Methode verschieben
Verwenden von OCaml Set :
Übrigens, Sie können mein n-nächster Nachbar-Sample von OCaml for Scientists und The F # .NET Journal Artikel Traversierende Netzwerke: n-te nächste Nachbarn .
Tags und Links algorithm data-structures