Erlang:递归与列表

Question

我是Erlang的新手,我试图理解为什么递归比使用list更快(甚至可以得到错误"无法在堆中分配内存").

我创建了两个函数来查找值的素数(非常简单):

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到平方根加1的所有数字.这是20096056整数列表.

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

由于空间和性能原因,您的问题不适合在内存中创建整个搜索空间的解决方案.

总之,这里列表的使用非常不理想.

至于命名约定:当函数具有不同的arity(不同数量的参数)时,通常将其命名为相同.虽然Erlang并不认为它具有相同的功能,但只有具有相同名称和arity的函数才被认为是相同的.

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.