Erlang：递归 vs 列表

Question

Erlang：递归 vs 列表

4

我是Erlang的新手，我试图理解为什么递归比使用列表更快（甚至可能会出现“无法在堆中分配内存”的错误）。

我创建了两个函数来查找给定值的质数（非常直观）：

using recursion:

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

list

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

当我传递小值时，两个函数同时执行。但是当我传递像403851455234578这样的巨大值时，第二个函数变得越来越慢，甚至会抛出错误。

请问有人能解释为什么第一个函数比列表更好吗？有没有更好的重写函数的方法？第一个列表是否有任何命名约定（函数加上它们的“子递归函数”）？

谢谢。

- ravnur

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Lindberg · Accepted Answer

第一个函数更快，因为您只需要计算一次顶部数字。在第二个函数中，您需要创建从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.