list - Erlang:递归与列表

Question

我是 Erlang 的新手，我试图理解为什么递归比使用 list 工作得更快(甚至可能出现“无法在堆中分配内存”的错误)。

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

使用递归:

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).

列表

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

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

总而言之，这里使用列表是非常次优的。

至于命名约定:当函数具有不同的元数(不同数量的参数)时，通常将其命名为相同的。 Erlang 并不认为它是同一个函数，只有具有相同名称和元数的函数才被认为是相等的。

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.