Recherche binaire dans Erlang dans lg (n) temps

Question

Je cherchais à travers le travail possible pour faire la recherche binaire dans Erlang et j'ai trouvé http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Mais je me demandais si la solution dans le blog s'exécute dans O (lg n). Maintenant, puisque la récurrence pour la recherche binaire est: T (n) = T (n/2) + c qui me donne un temps d'exécution de O (lg n).

Depuis un tableau C vous avez le pouvoir d'accéder à n'importe quel élément en O (1) temps. Mais dans erlang si l'accès au milieu de la liste prend le temps cn, alors la recherche binaire s'exécute en temps global linéaire aussi pauvre que la recherche linéaire.

Je suis tombé sur des listes: nth/2 BIF pour trouver le nième élément dans une liste mais je ne suis pas sûr de son temps d'exécution.

Un commentaire?

Answer 1

Il existe quelques structures de données qui permettent l'accès O (1) dans les tables, tuples et binaires d'Erlang: ETS.

Maintenant, aucun d'entre eux ne serait vraiment approprié pour une recherche binaire. La table ETS prend en charge la recherche depuis le début, et sinon, les données sont copiées dans votre processus lors du renvoi du résultat, ce qui ne sera probablement pas optimal pour votre cas d'utilisation.

Les tuples autorisent l'accès O (1) avec element/2, mais leur modification a un certain surcoût (c'est pourquoi le module de tableau utilise des arborescences de tuples).

Ensuite, vous avez binaires (<<1,2,3,4,5>>), qui permettent quelque chose de similaire à pointeur arithmétique, comme dans l'exemple suivant:

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

Cependant, prédire les performances lors de la construction binaire est un peu louche, et ce Le type d'arithmétique de pointeur est plus difficile à faire si vos valeurs ont des types différents et des tailles différentes lorsqu'elles sont représentées dans un binaire.

Votre meilleur pari serait probablement d'utiliser une liste de valeurs, de le trier, puis d'utiliser list_to_tuple/1 pour le contourner avec element/2.

Je recommanderais cependant fortement d'utiliser un arbre pour faire votre recherche; il serait probablement beaucoup plus simple d'utiliser le module gb_tree pour construire un arbre équilibré et obtenir toujours la recherche O (log N).

Answer 2

nth est O (n). Utilisez array module pour la structure de données à accès constant (tableau comme en C - presque).