在lg(n)时间内在Erlang中进行二进制搜索

Question

我正在搜索在Erlang中进行二进制搜索的可能工作,我找到了http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/但我想知道博客中的解决方案是否运行O(lg n).现在,因为二进制搜索的重现是:T(n)= T(n/2)+ c,它给出了O(lg n)的执行时间.

因为在C数组中,您可以在O(1)时间内访问任何元素.但是在erlang中,如果访问列表中间需要cn时间,则二进制搜索在线性整体时间内运行与线性搜索一样差.

我遇到了列表:第n/2个BIF用于查找列表中的第n个项目,但我不确定它的执行时间.

任何意见 ？

Answer 1

有一些数据结构允许在Erlang中进行O(1)访问:ETS表,元组和二进制文件.

现在,它们都不适合二进制搜索.ETS表支持从头开始搜索,否则,在返回结果时会将数据复制到您的进程,这可能不是您的用例的最佳选择.

元组允许O(1)访问element/2,但修改它们有一定的开销(这就是阵列模块使用元组树的原因).

然后你有二进制(<<1,2,3,4,5>>),它允许类似于指针算术的东西,如下例所示:

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

但是,在构建二进制文件时预测性能有点粗略,如果您的值在二进制文件中表示时具有不同的类型和不同的大小,则这种指针算法更难实现.

您最好的选择可能是使用值列表,对其进行排序,然后使用list_to_tuple/1它来导航element/2.

但我强烈建议您使用树来搜索; 使用该gb_tree模块构建平衡树并仍然可以获得O(log N)搜索可能要简单得多.