Erlang Thursday Bonus! Performace of erlang:length/1 on a list

发表于   |   分类于 ，

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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}

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

原文链接： https://www.proctor-it.com/erlang-thursday-bonus-performace-of-erlang-length-1-on-a-list/