Búsqueda binaria en Erlang en lg (n) tiempo

Question

Estaba buscando a través de posibles soluciones para hacer búsquedas binarias en Erlang y encontré http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Pero me preguntaba si la solución en el blog se ejecuta en O (lg n). Ahora, dado que la recurrencia para la búsqueda binaria es: T (n) = T (n/2) + c, lo que me da un tiempo de ejecución de O (lg n).

Dado que en una matriz C tiene el poder de acceder a cualquier elemento en el tiempo O (1). Pero en erlang si acceder al medio de la lista lleva cn tiempo, entonces la búsqueda binaria se ejecuta en tiempo general lineal tan pobre como la búsqueda lineal.

Encontré listas: nth/2 BIF para encontrar el enésimo artículo en una lista, pero no estoy seguro de su tiempo de ejecución.

¿Algún comentario?

Answer 1

Existen algunas estructuras de datos que permiten el acceso O (1) en Erlang: tablas, tuplas y binarios de ETS.

Ahora, ninguno de ellos sería realmente apropiado para una búsqueda binaria. La tabla ETS admite la búsqueda desde el inicio, y de lo contrario, los datos se copian en su proceso al devolver el resultado, que probablemente no sea óptimo para su caso de uso.

Las tuplas permiten O (1) acceder con element/2, pero modificarlas tiene una cierta sobrecarga (por lo que el módulo de matriz utiliza árboles de tuplas).

entonces usted tiene binarios (<<1,2,3,4,5>>), que permiten algo similar a puntero aritmética, como en el siguiente ejemplo:

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

Sin embargo, predecir el rendimiento cuando se construye el binario es un poco rara, y esto El tipo de aritmética del puntero es más difícil de hacer si sus valores tienen diferentes tipos y tamaños cuando están representados en un binario.

Lo mejor que puede hacer es utilizar una lista de valores, ordenarla y luego usar list_to_tuple/1 para navegar alrededor con element/2.

Sin embargo, le recomiendo usar un árbol para realizar su búsqueda; probablemente sería mucho más simple usar el módulo gb_tree para construir un árbol balanceado y obtener la búsqueda O (log N).

Answer 2

nth es O (n). Use array module para la estructura de datos de acceso constante (array como en C - casi).