Хвостовая рекурсия против не хвостовой рекурсии.Первый медленнее? - PullRequest
Новая
       29

Хвостовая рекурсия против не хвостовой рекурсии.Первый медленнее?

2 голосов
/ 16 июня 2019

Я изучаю основы функционального программирования и 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

Я ожидал, что версия хвостовой рекурсиивыступают лучше, чем два других, но, к моему удивлению, они менее производительны.Эти результаты являются полной противоположностью того, что я ожидал.

Почему?

Ответы [ 2 ]

5 голосов
/ 17 июня 2019

Проблема в функции, которую вы выбираете. Факториал - это функция, которая очень быстро растет. Эрланг реализовал целочисленную арифметику, поэтому она не будет переполнена. Вы эффективно измеряете, насколько хорошо лежит большая целочисленная реализация. 1000000! это огромное количество. Это 8,26 × 10 ^ 5565708, что похоже на длину 5,6 МБ, записанную в виде десятичного числа. Между вашими 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 shoudl превосходит 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 для 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, и он работает довольно быстро. В любом случае, рекурсивная функция тела значительно медленнее 110 мс против 85 мс. Вы можете заметить, что первый запуск 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
0 голосов
/ 22 июня 2019

В документации Erlang указано, что 

It is generally not possible to predict whether the tail-recursive 
or the body-recursive version will be faster. Therefore, use the version that
makes your code cleaner (hint: it is usually the body-recursive version).

http://erlang.org/doc/efficiency_guide/myths.html

...