文档结构  
翻译进度:已翻译     翻译赏金:0 元 (?)    ¥ 我要打赏

今天给大家一个Erlang Thursday福利。

上星期在达拉斯-沃斯堡的Erlang User group 演讲上,有一些Erlang新人参加我们的会议,有人提到了如下问题:

有没有聪明的方法来获得列表的长度,或者还是必须要遍历列表的所有元素来计算它的长度呢?

我可以百分之九九确定Erlang必须每次都要遍历列表来计算其长度,因为它用链接列表类的数据结构来构造它的列表,但是我不确定是否有一些聪明的实现方法是我没有意识到,这些方法能提高获取列表长度到速度。

第 1 段(可获 1.36 积分)

在写今天的Erlang Thursday的时候,我意识到,我应该用 timer:tc 函数,通过它来展示需要多长时间来获取不同列表的长度来证明 erlang:length/1 函数的执行情况。

为了纪念这个问题,也为了在下一次会议的时候能回忆其它,我在这里记录相关内容。我们要明白,timer:tc 函数返回的结果里第一个元素是被测量函数执行的微秒时间。

timer:tc(erlang, length, [lists:seq(1, 10)]).
{2,10}
timer:tc(erlang, length, [lists:seq(1, 1000)]).
{5,1000}
timer:tc(erlang, length, [lists:seq(1, 10000)]).
{41,10000}
timer:tc(erlang, length, [lists:seq(1, 100000)]).
{134,100000}
timer:tc(erlang, length, [lists:seq(1, 1000000)]).
{1918,1000000}
timer:tc(erlang, length, [lists:seq(1, 10000000)]).
{25139,10000000}
timer:tc(erlang, length, [lists:seq(1, 100000000)]).
{1368691,100000000}
第 2 段(可获 0.99 积分)

在链接列表有大概1000元素以后,我们可以看到计算其长度的时间线性增长,尽管不是真正对所有节点做遍历,但是在算法复杂度(大O)上看是相同复杂度级别。

第 3 段(可获 0.64 积分)

文章评论