Wyszukiwanie binarne w Erlangu w czasie lg (n)

Question

Przeszukałem możliwe prace do wykonania dla wyszukiwania binarnego w Erlangu i znalazłem http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Ale zastanawiałem się, czy rozwiązanie na blogu działa w O (lg n). Teraz, ponieważ rekurencja dla wyszukiwania binarnego to: T (n) = T (n/2) + c, co daje mi czas wykonania O (lg n).

Ponieważ w macierzy C masz możliwość dostępu do dowolnego elementu w czasie O (1). Ale w erlangu, jeśli dostęp do środka listy zajmuje cn czas, to wyszukiwanie binarne działa w liniowym czasie ogólnym tak słabym, jak wyszukiwanie liniowe.

Natknąłem się na listy: n/2 BIF dla znalezienia n-tego elementu na liście, ale nie jestem pewien co do czasu jego wykonania.

Masz jakieś uwagi?

Answer 1

Istnieje kilka struktur danych, które umożliwiają dostęp O (1) w tabelach Erlang: ETS, krotkach i plikach binarnych.

Teraz żadna z nich nie byłaby odpowiednia do wyszukiwania binarnego. Tabela ETS obsługuje wyszukiwanie od początku, w przeciwnym razie dane są kopiowane do procesu po zwróceniu wyniku, co prawdopodobnie nie będzie optymalne w przypadku użycia.

Krotki umożliwiają dostęp O (1) z element/2, ale modyfikowanie ich ma pewien narzut (dlatego moduł tablicy używa drzew krotek).

Wtedy masz binarne (<<1,2,3,4,5>>), które pozwalają na coś podobnego do arytmetyki wskaźników, jak w poniższym przykładzie:

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

Jednak przewidywania wydajności przy budowie binarny jest nieco nieprzyjemne, a to rodzaj arytmetyki wskaźnika jest trudniejszy do zrobienia, jeśli twoje wartości mają różne typy i różne rozmiary, gdy są reprezentowane w pliku binarnym.

Najlepszym rozwiązaniem byłoby użycie listy wartości, posortowanie jej, a następnie użycie list_to_tuple/1 do nawigacji po niej przy pomocy element/2.

Zdecydowanie zaleca się jednak użycie drzewa do wyszukiwania; byłoby znacznie łatwiej użyć modułu gb_tree do zbudowania zrównoważonego drzewa i nadal uzyskiwać wyszukiwanie O (log N).

Answer 2

nth to O (n). Użyj array module dla struktury danych o stałym dostępie (tablica jak w C - prawie).