Binäre Suche in Erlang in lg (n) Zeit

Question

Ich suchte durch die möglichen Arbeitsumgebungen für binäre Suche in Erlang und ich fand http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Aber ich fragte mich, ob die Lösung in Blog in O (LG) läuft. Jetzt, da die Wiederholung für die binäre Suche ist: T (n) = T (n/2) + c was mir eine Ausführungszeit von O (lg n) gibt.

Da Sie in einem C-Array die Möglichkeit haben, auf jedes Element in O (1) -Zeit zuzugreifen. Aber in Erlang, wenn der Zugriff auf die Mitte der Liste dauert cn Zeit, dann läuft die binäre Suche in linearen Gesamtzeit so schlecht wie lineare Suche.

Ich stieß auf Listen: nth/2 BIF für die Suche nach dem n-ten Element in einer Liste, aber ich bin mir nicht sicher über die Ausführungszeit.

Irgendwelche Kommentare?

Answer 1

Es gibt ein paar Datenstrukturen, die O (1) Zugriff in Erlang erlauben: ETS-Tabellen, Tupel und Binärdateien.

Nun wäre keiner von ihnen wirklich für eine binäre Suche geeignet. Die ETS-Tabelle unterstützt die Suche von Anfang an, und ansonsten werden Daten in Ihren Prozess kopiert, wenn das Ergebnis zurückgegeben wird, was für Ihren Anwendungsfall wahrscheinlich nicht optimal ist.

Tupel erlauben O (1) -Zugriff mit element/2, aber ihre Änderung hat einen gewissen Overhead (weshalb das Array-Modul Tupel-Bäume verwendet).

Dann haben Sie Binärdateien (<<1,2,3,4,5>>), die ähnlich etwas erlaubt Arithmetik Zeiger, wie in folgendem Beispiel:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>. 
<<"abcdefgh">> 
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted. 
<<"abcdefgh">> 
3> X. 
<<"d">> 

jedoch die Leistung der Vorhersage beim Bau der binären ein wenig lückenhaft ist, und dies Art der Zeigerarithmetik ist schwieriger zu tun, wenn Ihre Werte unterschiedliche Typen und unterschiedliche Größen haben, wenn sie in einer Binärdatei dargestellt werden.

Ihre beste Wette wäre wahrscheinlich, eine Liste von Werten zu verwenden, sie zu sortieren und dann list_to_tuple/1 zu verwenden, um mit element/2 umher zu navigieren.

Ich würde jedoch dringend empfehlen, einen Baum zu verwenden, um Ihre Suche durchzuführen; Es wäre wahrscheinlich viel einfacher, das Modul gb_tree zu verwenden, um einen ausgeglichenen Baum zu erstellen und dennoch O (log N) -Suche zu erhalten.

Answer 2

nth ist O (n). Verwenden Sie array module für konstante Datenstruktur (Array wie in C - fast).