Erlang: рекурсия против списков

Question

Я новичок в Erlang, и я пытаюсь понять, почему рекурсия работает быстрее, чем использование списка (который может даже получить ошибку "не удается выделить память в куче").

Я создал две функции для поиска простых чисел для значения (довольно просто):

1. с использованием рекурсии:

   find_factor_rec(List, Max, _, NextValue)
       when NextValue > Max ->
           List;
   
   find_factor_rec(List, Max, Value, NextValue)->
       if (Value rem NextValue =:= 0) ->
           find_factor_rec([NextValue|List], Max, Value, NextValue + 1);
       true ->
           find_factor_rec(List, Max, Value, NextValue + 1)
       end
   .
   
   find_factors(Val)->
       find_factor_rec([], round(math:sqrt(Val)) + 1, Val, 2).
   

2. список

   find_factors1(Val) ->
       [X || X <- lists:seq(2, round(math:sqrt(Val)) + 1), Val rem X =:= 0].
   

пока я передаю небольшие значения - оба одновременно. Когда я передаю огромные значения, такие как 403851455234578, вторая функция становится все медленнее и медленнее и даже выдает ошибку.

Может кто-нибудь объяснить, почему первая функция лучше, чем список? Есть ли лучший способ переписать функцию? Существуют ли соглашения об именах для первого списка? (функция плюс их "дочерние рекурсивные функции")

Спасибо.

Answer 1

Первая функция быстрее, потому что вы вычисляете только верхнее число один раз. Во второй функции вы создаете все числа от 2 до квадратного корня плюс один. Это 20096056 целых чисел в списке.

lists:seq(2, round(math:sqrt(Val)) % Creates a list from 2 to 20096056

Ваша проблема не подходит для решения, которое создает все пространство поиска в памяти по причинам, связанным с пространством и производительностью.

В заключение, использование списков здесь очень неоптимально.

---

Что касается соглашений об именовании: когда функция имеет другую арность (другое количество аргументов), обычно ее называют одинаковой. Эрланг не видит ее как одну и ту же функцию, хотя, только функции с одинаковым именем и арностью считаются равными.

find_factors(Val)-> find_factor_rec([], round(math:sqrt(Val)) + 1, Val, 2).

find_factors(List, Max, _, NextValue) when NextValue > Max ->
    List;
find_factors(List, Max, Value, NextValue) ->
    if 
        (Value rem NextValue =:= 0) ->
            find_factors([NextValue|List], Max, Value, NextValue + 1);
        true ->
            find_factors(List, Max, Value, NextValue + 1)
    end.