Erlang：为什么使用递归+反向而不是映射对列表的操作是最快的？

Question

我很好奇对列表进行操作的最快方法是什么。

我创建了一个小模块来帮助我解决这个问题：

-module(tests).

-compile(export_all).

createRandomList(Nb) ->
    [random:uniform(10) || _ <- lists:seq(1, Nb)].

fastest() ->
    List = createRandomList(10000),
    StartFlatten = tools:getTimeStampMilli(),
    flatten(List),
    StopFlatten = tools:getTimeStampMilli(),
    debug:print("Flatten~n"),
    debug:print("Start at: ~p~nStop at: ~p~nTime elapsed: ~p~n", [StartFlatten, StopFlatten, (StopFlatten-StartFlatten)]),
    debug:print("#############~n~n"),
    StartReverse = tools:getTimeStampMilli(),
    reverse(List),
    StopReverse = tools:getTimeStampMilli(),
    debug:print("Reverse~n"),
    debug:print("Start at: ~p~nStop at: ~p~nTime elapsed: ~p~n", [StartReverse, StopReverse, (StopReverse-StartReverse)]),
    debug:print("#############~n~n"),
    StartMap = tools:getTimeStampMilli(),
    map(List),
    StopMap = tools:getTimeStampMilli(),
    debug:print("Map~n"),
    debug:print("Start at: ~p~nStop at: ~p~nTime elapsed: ~p~n", [StartMap, StopMap, (StopMap-StartMap)]),
    debug:print("#############~n~n").

op(A) ->
    A+2.

flatten(List) ->
    flatten(List, []).
flatten([], Accu) ->
    Accu;
flatten([Obj|Tail], Accu) ->
    flatten(Tail, lists:flatten([Accu, op(Obj)])).

reverse(List) ->
    reverse(List, []).
reverse([], Accu) ->
    lists:reverse(Accu);
reverse([Obj|Tail], Accu) ->
    reverse(Tail, [op(Obj)|Accu]).

map(List) ->
    lists:map(fun op/1, List).

结果如下：

----debug: Flatten
Start at: 1424535074364
Stop at: 1424535274083
Time elapsed: 1.99719 s
----debug: #############

----debug: Reverse
Start at: 1424535274208
Stop at: 1424535274551
Time elapsed: 0.00343 s
----debug: #############

----debug: Map
Start at: 1424535274631
Stop at: 1424535275095
Time elapsed: 0.00464 s
----debug: #############

我实际上可以理解为什么使用 flatten 方法比其他方法长 waaaay...但我认为为列表操作而创建的函数会比我自己的反向递归函数更快...

有人解释一下吗？

或者我的模块中可能有一个丑陋的错误！！

编辑1：如果我在更大的列表上一次又一次地调用测试，我会得到以下结果：

3> tests:fastest().
----debug: Reverse
Start at: 1424536230201935
Stop at: 1424536230262924
Time elapsed: 60989
----debug: #############

----debug: Map
Start at: 1424536230263066
Stop at: 1424536230326419
Time elapsed: 63353
----debug: #############

ok
4> tests:fastest().
----debug: Reverse
Start at: 1424536231860951
Stop at: 1424536231917979
Time elapsed: 57028
----debug: #############

----debug: Map
Start at: 1424536231918116
Stop at: 1424536231975828
Time elapsed: 57712
----debug: #############

ok
5> tests:fastest().
----debug: Reverse
Start at: 1424536233253424
Stop at: 1424536233309301
Time elapsed: 55877
----debug: #############

----debug: Map
Start at: 1424536233309430
Stop at: 1424536233375391
Time elapsed: 65961
----debug: #############

ok
6> tests:fastest().
----debug: Reverse
Start at: 1424536235622322
Stop at: 1424536235675287
Time elapsed: 52965
----debug: #############

----debug: Map
Start at: 1424536235675424
Stop at: 1424536235739555
Time elapsed: 64131
----debug: #############

很奇怪，不是吗？

编辑 2：

好的成功使用 timer:tc 结果如下：

1> tests:fastest().
ReverseTime: 58455
MapTime: 47507
ok
2> tests:fastest().
ReverseTime: 29887
MapTime: 61311
ok
3> tests:fastest().
ReverseTime: 61563
MapTime: 68040
ok
4> tests:fastest().
ReverseTime: 55874
MapTime: 57388
ok
5> tests:fastest().
ReverseTime: 56712
MapTime: 61326
ok

和以前差不多...

Answer 1

正如 Pascal 在对您的问题的评论中观察到的那样，Erlang 标准库中 lists:map/2 的实现按照它们在原始列表中出现的确切顺序从头到尾构造了一个新列表。您的 "reverse" 函数以相反的顺序构造它，或尾对头。

从头到尾排序的副作用之一是虚拟机必须return将每次调用映射函数的结果传递给函数那叫它。也就是说，每次调用该函数都会在调用堆栈中添加另一个return地址，最后一次调用必须访问一次已完成以产生最终的 return 值。您可以在调用本身的语法中看到这一点：

map(F, [H|T]) ->
    %% At this point, the result of map(F, T) is unknown,
    %% so we must evaluate it to determine what the tail
    %% of this expression should be.
    [F(H)|map(F, T)];
map(F, []) ->
    [].

另一方面，可以针对尾递归优化尾对头排序，这意味着原始堆栈被重用对于所有后续调用。这有效地优化了我们在以相反方式构建列表时必须访问的所有那些 return 地址。事实上，如果您要删除对 lists:reverse/1 的调用，您会发现尾对头排序比头对尾排序表现得更加一致。

reverse(F, [H|T], Acc) ->
    %% Here, we know what Acc is, so the only thing
    %% we have to evaluate is F(H). 
    %% And since we're calling ourselves recursively and
    %% do nothing with the return value of the function, 
    %% we're eligible for tail-call optimization.
    reverse(F, T, [F(H)|Acc]);
reverse(F, [], Acc) ->
    %% Now we launch into another function that's eligible
    %% for tail-call optimization (though its implementation
    %% uses another form of stack sharing, known as a "while
    %% loop"
    lists:reverse(Acc).

最后，lists:reverse/1 是一个 C 语言优化的 BIF，它的执行速度比任何等效的纯 Erlang 函数都快得多（通过绕过 BEAM 解释器和一些智能分配技巧实现）。不过，即使不考虑这一点，逆向也是不需要访问各种 return 点的另一种尾递归操作，由于 Erlang 制作了 浅拷贝 [=29]，因此效率更高=] 原始列表中的术语（基本上使用 pointer/reference 到术语而不是术语本身的新副本）。

Erlang：为什么使用递归+反向而不是映射对列表的操作是最快的？

Erlang : Why operation on Lists are fastest with recursivity + reverse instead of map?

erlang