尾递归与非尾递归。前者慢吗？

Question

我正在学习函数式编程和 Erlang 的基础知识，并且我已经实现了阶乘函数的三个版本：将递归与守卫结合使用、将递归与模式匹配结合使用以及使用尾递归。

我正在尝试比较每个阶乘实现的性能 (Erlang/OTP 22 [erts-10.4.1]):

%% Simple factorial code:
fac(N) when N == 0 -> 1;
fac(N) when N > 0 -> N * fac(N - 1).

%% Using pattern matching:
fac_pattern_matching(0) -> 1;
fac_pattern_matching(N) when N > 0 -> N * fac_pattern_matching(N - 1).

%% Using tail recursion (and pattern matching):
tail_fac(N) -> tail_fac(N, 1).

tail_fac(0, Acc) -> Acc;
tail_fac(N, Acc) when N > 0 -> tail_fac(N - 1, N * Acc).

计时器助手：

-define(PRECISION, microsecond).

execution_time(M, F, A, D) ->
  StartTime = erlang:system_time(?PRECISION),
  Result = apply(M, F, A),
  EndTime = erlang:system_time(?PRECISION),
  io:format("Execution took ~p ~ps~n", [EndTime - StartTime, ?PRECISION]),
  if
    D =:= true -> io:format("Result is ~p~n", [Result]);
    true -> ok
  end
.

执行结果：

递归版本：

3> mytimer:execution_time(factorial, fac, [1000000], false).
Execution took 1253949667 microseconds
ok

具有模式匹配版本的递归：

4> mytimer:execution_time(factorial, fac_pattern_matching, [1000000], false).
Execution took 1288239853 microseconds
ok

尾递归版本：

5> mytimer:execution_time(factorial, tail_fac, [1000000], false).
Execution took 1405612434 microseconds
ok

我原以为尾递归版本的性能会比其他两个好，但令我惊讶的是它的性能较差。这些结果与我的预期完全相反。

为什么？

Answer 1

问题出在您选择的功能上。阶乘是一个增长非常快的函数。 Erlang 已经实现了大整数运算，所以它不会溢出。您正在有效地衡量底层大整数实现的好坏。 100万！是一个巨大的数字。它是 8.26×10^5565708 就像 5.6MB 长写成一个十进制数。您的 fac/1 和 tail_fac/1 在大整数实现开始时达到大数字的速度以及数字增长的速度之间存在差异。在您的 fac/1 实现中，您实际上是在计算 1*2*3*4*...*N。在您的 tail_fac/1 实现中，您正在计算 N*(N-1)*(N-2)*(N-3)*...*1。你看到那里的问题了吗？您可以用不同的方式编写尾调用实现：

tail_fac2(N) when is_integer(N), N > 0 ->
    tail_fac2(N, 0, 1).

tail_fac2(X, X, Acc) -> Acc;
tail_fac2(N, X, Acc) ->
    Y = X + 1,
    tail_fac2(N, Y, Y*Acc).

它会更好用。我不像你那样有耐心，所以我会测量一些小一点的数字，但新的 fact:tail_fac2/1 应该每次都优于 fact:fac/1：

1> element(1, timer:tc(fun()-> fact:fac(100000) end)).
7743768
2> element(1, timer:tc(fun()-> fact:fac(100000) end)).
7629604
3> element(1, timer:tc(fun()-> fact:fac(100000) end)).
7651739
4> element(1, timer:tc(fun()-> fact:tail_fac(100000) end)).
7229662
5> element(1, timer:tc(fun()-> fact:tail_fac(100000) end)).
7104056
6> element(1, timer:tc(fun()-> fact:tail_fac2(100000) end)).
6491195
7> element(1, timer:tc(fun()-> fact:tail_fac2(100000) end)).
6506565
8> element(1, timer:tc(fun()-> fact:tail_fac2(100000) end)).
6519624

如您所见，fact:tail_fac2/1 for N = 100000 需要 6.5 秒，fact:tail_fac/1 需要 7.2 秒，fact:fac/1 需要 7.6 秒。更快的增长不会推翻尾调用的好处，所以尾调用版本比主体递归版本更快，可以清楚地看到 fact:tail_fac2/1 中累加器的较慢增长显示了它的影响。

如果您为尾调用优化测试选择不同的函数，您可以更清楚地看到尾调用优化的影响。例如总和：

sum(0) -> 0;
sum(N) when N > 0 -> N + sum(N-1).

tail_sum(N) when is_integer(N), N >= 0 ->
    tail_sum(N, 0).

tail_sum(0, Acc) -> Acc;
tail_sum(N, Acc) -> tail_sum(N-1, N+Acc).

速度是：

1> element(1, timer:tc(fun()-> fact:sum(10000000) end)).
970749
2> element(1, timer:tc(fun()-> fact:sum(10000000) end)).
126288
3> element(1, timer:tc(fun()-> fact:sum(10000000) end)).
113115
4> element(1, timer:tc(fun()-> fact:sum(10000000) end)).
104371
5> element(1, timer:tc(fun()-> fact:sum(10000000) end)).
125857
6> element(1, timer:tc(fun()-> fact:tail_sum(10000000) end)).
92282
7> element(1, timer:tc(fun()-> fact:tail_sum(10000000) end)).
92634
8> element(1, timer:tc(fun()-> fact:tail_sum(10000000) end)).
68047
9> element(1, timer:tc(fun()-> fact:tail_sum(10000000) end)).
87748
10> element(1, timer:tc(fun()-> fact:tail_sum(10000000) end)).
94233

如您所见，我们可以轻松地使用 N=10000000，而且速度非常快。无论如何，主体递归函数明显慢 110ms vs 85ms。您可以注意到 fact:sum/1 的第一个运行比其余运行花费的时间长 9 倍。这是因为主体递归函数消耗堆栈。当你使用尾递归对应物时，你不会看到这样的效果。（尝试一下。）如果您运行在单独的过程中进行每个测量，您会看到差异。

1> F = fun(G, N) -> spawn(fun() -> {T, _} = timer:tc(fun()-> fact:G(N) end), io:format("~p took ~bus and ~p heap~n", [G, T, element(2, erlang:process_info(self(), heap_size))]) end) end.
#Fun<erl_eval.13.91303403>
2> F(tail_sum, 10000000).
<0.88.0>
tail_sum took 70065us and 987 heap
3> F(tail_sum, 10000000).
<0.90.0>
tail_sum took 65346us and 987 heap
4> F(tail_sum, 10000000).
<0.92.0>
tail_sum took 65628us and 987 heap
5> F(tail_sum, 10000000).
<0.94.0>
tail_sum took 69384us and 987 heap
6> F(tail_sum, 10000000).
<0.96.0>
tail_sum took 68606us and 987 heap
7> F(sum, 10000000).
<0.98.0>
sum took 954783us and 22177879 heap
8> F(sum, 10000000).
<0.100.0>
sum took 931335us and 22177879 heap
9> F(sum, 10000000).
<0.102.0>
sum took 934536us and 22177879 heap
10> F(sum, 10000000).
<0.104.0>
sum took 945380us and 22177879 heap
11> F(sum, 10000000).
<0.106.0>
sum took 921855us and 22177879 heap

尾递归与非尾递归。前者慢吗？

Tail recursion vs non tail recursion. Is the former slower?

erlang

tail-recursion