Erlang：递归与列表

发布于 2024-12-05 13:45:43 字数 831 浏览 1 评论 0原文

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

我创建了两个函数来查找某个值的素数（非常简单）：

使用递归：

find_factor_rec(列表、最大值、_、NextValue)
    当下一个值>最大->
        列表;

find_factor_rec(List, Max, Value, NextValue)->
    if (值 rem NextValue =:= 0) ->
        find_factor_rec([NextValue|列表], 最大值, 值, NextValue + 1);
    正确->
        find_factor_rec(列表、最大值、值、NextValue + 1)
    结尾
。

find_factors(Val)->;
    find_factor_rec([], round(数学:sqrt(Val)) + 1, Val, 2)。

列表

find_factors1(Val) ->;
    [X|| X <- 列表：seq(2, round(数学:sqrt(Val)) + 1), Val rem X =:= 0]。

- 两者同时发生。当我传递像 403851455234578 这样的巨大值时，第二个函数变得越来越慢，甚至抛出错误。

有人可以解释一下为什么第一个功能比列表更好吗？有更好的方法重写函数吗？第一次上市有什么命名约定吗？（函数加上它们的“子递归函数”）

谢谢。

原文

I'm newbie in Erlang and i'm trying to understand why recursion working faster than using list (that can even got an error "can't allocate memory in heap").

I created two functions to find primes for a value (pretty straight forward):

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

while i'm passing small values - both are at the same time. When i'm passing huge values like 403851455234578 the second function became slower and slower and even throws error.

Could someone please explain why first function better than list?
Are there better way to rewrite function?
Are there any name convention for the first listing? (function plus their "child-recursive-functions")

Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

心凉怎暖 2024-12-12 13:45:43

第一个函数更快，因为您只计算顶部数字一次。在第二个函数中，您创建从 2 到平方根加一的所有数字。这是列表中的 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.

The first function is faster because you only calculate the top number once. In the second function, you create all the numbers from 2 to the square root plus one. That's 20096056 integers in a list.

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

Your problem doesn't suit itself to a solution that creates the whole search space in memory, because of space and performance reasons.

To conclude, the use of lists here is very sub-optimal.

As for naming conventions: when the function has a different arity (a different number of arguments) one usually names it the same. Erlang does not see it as the same function though, only functions with the same name and arity are considered equal.

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.

回复收藏 0 原文

~没有更多了~