++ 运算符是否比 | 更昂贵？ Erlang 中的运算符？

Question

我正在阅读 Learn You Some Erlang and I came upon this example in the Recursion 章。

tail_sublist(_, 0, SubList) -> SubList;
tail_sublist([], _, SubList) -> SubList;
tail_sublist([H|T], N, SubList) when N > 0 -> 
tail_sublist(T, N-1, [H|SubList]).

正如作者继续解释的那样，我们的代码中存在 致命缺陷。这是因为由此产生的子列表将被反转，我们将不得不重新反转它们以获得正确的输出。相反，我所做的是使用 ++ 运算符来避免稍后反转列表。

sublist_tail([],_,Acc) -> Acc;
sublist_tail(_,0,Acc) -> Acc;
sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,Acc++[H]).

我的问题是，++ 运算符是否比 | 运算符更昂贵？ 如果是， 我会与作者的解决方案（包括反转列表以获得正确输出）相比，解决方案（使用 ++ 运算符）仍然很慢？

Answer 1

您可能想在 Erlang efficiency guide 中阅读有关此问题的信息，因为那里说通过 | 构建列表然后反转结果比使用附加 [=12] 更有效=] 运算符。如果您想知道性能差异，请使用 timer:tc:

1> timer:tc(fun() -> lists:reverse(lists:foldl(fun(V, Acc) -> [V|Acc] end, [], lists:seq(1,1000))) end).
{1627,
 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
  23,24,25,26,27|...]}
2> timer:tc(fun() -> lists:foldl(fun(V, Acc) -> Acc++[V] end, [], lists:seq(1,1000)) end).
{6216,
 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
  23,24,25,26,27|...]}

这两种方法都创建了包含 1000 个整数的列表，但是这些基于 Erlang/OTP 17.5 的测量显示 prepending/reversing 版本比附加版本（当然是 YMMV）快大约 4 倍。

Answer 2

is the ++ operator more expensive than the | operator?

这取决于。如果你正确使用它，那么不会。 ++ 仅当您的左侧操作数很大时才危险。

每次在左侧列表（如：List1 ++ List2）上调用“++”运算符时，您正在创建一个新列表，即您的左侧列表的副本-手操作数（List1）。然后，每个复制操作都有一个运行时间，它取决于 List1 的长度（随着迭代不断增长）。

因此，如果您在前面加上您的值 'head first'，则不必在每个步骤中对整个列表执行复制操作。这也意味着，++ 在列表头部的累积也不会那么糟糕，因为在每次迭代中只复制一次 "H" 值：

sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,[H]++Acc).

但是，如果您已经先行积累（因此无论如何都必须稍后反转），您可以使用 cons-operator (|)

sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,[H|Acc]).

这是'proper'方式，因为（如果我错了请纠正我）++只是语法糖并且在内部实现反对者 (|).

++ 运算符是否比 | 更昂贵？ Erlang 中的运算符？

Is ++ operator more expensive than | operator in Erlang?

erlang