erlang - Erlang 中的 Eratosthenes 筛

Question

我正在学习Erlang。作为练习，我学习了生成素数的埃拉托色尼筛法。这是我的代码：

-module(seed2).
-export([get/1]).

get(N) -> WorkList = lists:duplicate(N, empty),
          get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
                                              NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
                                              get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).


markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
                                                                 markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
                                                           markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = lists:nth(Iterator, WorkList),
                                        if
                                          I =:= empty -> Iterator;
                                          true -> findNextPrime(Iterator + 1, N, WorkList)
                                        end.

replace(N, L, New)-> {L1, [_H|L2]} = lists:split(N - 1, L),
                     lists:append(L1, [New|L2]).

这段代码实际上有效:)。问题是我觉得这不是最好的实现。

我的问题是实施“埃拉托色尼筛”的“erlangish”方式是什么

编辑：好的，安德烈亚斯解决方案非常好，但速度很慢。有什么想法可以改善吗？

score 13 · Accepted Answer

这是一个简单（但不是非常快）的筛子实现：

-module(primes).
-export([sieve/1]).
-include_lib("eunit/include/eunit.hrl").

sieve([]) ->
    [];
sieve([H|T]) ->          
    List = lists:filter(fun(N) -> N rem H /= 0 end, T),
    [H|sieve(List)];
sieve(N) ->
    sieve(lists:seq(2,N)).

score 9 · Accepted Answer

这是我的筛子实现，它使用列表推导并尝试尾递归。我在最后反转列表，以便对素数进行排序：

primes(Prime, Max, Primes,Integers) when Prime > Max ->
    lists:reverse([Prime|Primes]) ++ Integers;
primes(Prime, Max, Primes, Integers) ->
    [NewPrime|NewIntegers] = [ X || X <- Integers, X rem Prime =/= 0 ],
    primes(NewPrime, Max, [Prime|Primes], NewIntegers).

primes(N) ->
    primes(2, round(math:sqrt(N)), [], lists:seq(3,N,2)). % skip odds

在我的 2ghz mac 上计算高达 2 百万的素数大约需要 2.8 毫秒。

score 2 · Accepted Answer

2

我通过使用并发处理来解决这个问题。

来源

于 2008-09-28T20:14:22.570 回答

score 2 · Accepted Answer

我之前的帖子格式不正确。这是代码的重新发布。对不起，垃圾邮件...


-module(test).

%%-export([sum_primes/1]).
-compile(export_all).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Sum of all primes below Max. Will use sieve of Eratosthenes 
sum_primes(Max) ->
    LastCheck = round(math:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note are creating odd-only array
    %%Primes = sieve(noref,All, LastCheck),
    Primes = spawn_sieve(All, LastCheck),
    lists:sum(Primes) + 2. %adding back the number 2 to the list


%%sieve of Eratosthenes
sieve(Ref,All, LastCheck) ->
    sieve(Ref,[], All, LastCheck).

sieve(noref,Primes, All = [Cur|_], LastCheck) when Cur > LastCheck ->
    lists:reverse(Primes, All); %all known primes and all remaining from list (not sieved) are prime    
sieve({Pid,Ref},Primes, All=[Cur|_], LastCheck) when Cur > LastCheck ->
    Pid ! {Ref,lists:reverse(Primes, All)}; 
sieve(Ref,Primes, [Cur|All2], LastCheck) ->
    %%All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
    All3 = lists_filter(Cur,All2),
    sieve(Ref,[Cur|Primes], All3,  LastCheck).


lists_filter(Cur,All2) ->
    lists_filter(Cur,All2,[]).

lists_filter(V,[H|T],L) ->
    case H rem V of
    0 ->
        lists_filter(V,T,L);
    _ ->
        lists_filter(V,T,[H|L])
    end;
lists_filter(_,[],L) ->
    lists:reverse(L).


%% This is a sloppy implementation ;)
spawn_sieve(All,Last) ->
    %% split the job
    {L1,L2} = lists:split(round(length(All)/2),All),
    Filters = filters(All,Last),
    L3 = lists:append(Filters,L2),
    Pid = self(),
    Ref1=make_ref(),
    Ref2=make_ref(),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref1},L1,Last]),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref2},L3,Last]),
    Res1=receive
         {Ref1,R1} ->
         {1,R1};
         {Ref2,R1} ->
         {2,R1}
     end,
    Res2= receive
          {Ref1,R2} ->
          {1,R2};
          {Ref2,R2} ->
          {2,R2}
      end,
    apnd(Filters,Res1,Res2).


filters([H|T],Last) when H 
    [H|filters(T,Last)];
filters([H|_],_) ->
    [H];
filters(_,_) ->
    [].


apnd(Filters,{1,N1},{2,N2}) ->
    lists:append(N1,subtract(N2,Filters));
apnd(Filters,{2,N2},{1,N1}) ->
    lists:append(N1,subtract(N2,Filters)).



subtract([H|L],[H|T]) ->
    subtract(L,T);
subtract(L=[A|_],[B|_]) when A > B ->
    L;
subtract(L,[_|T]) ->
    subtract(L,T);
subtract(L,[]) ->
    L.

score 1 · Accepted Answer

我没有详细研究过这些，但我已经在下面测试了我的实现（我为 Project Euler 挑战编写的），它比上述两个实现快几个数量级。在我消除了一些自定义函数并转而寻找列表之前，它非常缓慢：可以执行相同操作的函数。吸取教训总是看看是否有一个你需要做的事情的库实现是很好的——它通常会更快！这可以在 2.8GHz iMac 上计算 3.6 秒内最多 200 万的素数总和...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Sum of all primes below Max. Will use sieve of Eratosthenes 
sum_primes(Max) ->
    LastCheck = round(math:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note are creating odd-only array
    Primes = sieve(All, Max, LastCheck),
    %io:format("Primes: ~p~n", [Primes]),
    lists:sum(Primes) + 2. %adding back the number 2 to the list

%sieve of Eratosthenes
sieve(All, Max, LastCheck) ->
    sieve([], All, Max, LastCheck).

sieve(Primes, All, Max, LastCheck) ->
    %swap the first element of All onto Primes 
    [Cur|All2] = All,
    Primes2 = [Cur|Primes],
    case Cur > LastCheck of 
        true ->
            lists:append(Primes2, All2); %all known primes and all remaining from list (not sieved) are prime
        false -> 
            All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
            sieve(Primes2, All3, Max, LastCheck)

    end.

score 1 · Accepted Answer

我有点喜欢这个主题，即素数，所以我开始稍微修改 BarryE 的代码，并通过创建自己的 lists_filter 函数使其速度提高了大约 70%，并且可以利用我的两个 CPU。我还可以轻松地在两个版本之间进行切换。测试运行显示：

61>计时器：tc（测试，sum_primes，[2000000]）。
{2458537,142913970581}

代码：


-模块（测试）。

%%-export([sum_primes/1])。
-编译（export_all）。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
%% 低于 Max 的所有素数的总和。将使用埃拉托色尼筛
sum_primes（最大值）->
    LastCheck = round(数学:sqrt(Max)),
    All = lists:seq(3, Max, 2), %note 正在创建奇数数组
    %%Primes = 筛子(noref,All, LastCheck),
    Primes = spawn_sieve(All, LastCheck),
    lists:sum(Primes) + 2. %将数字 2 添加到列表中


%%埃拉托色尼筛
筛子（参考，全部，最后检查）->
    筛子（参考，[]，所有，LastCheck）。

sieve(noref,Primes, All = [Cur|_], LastCheck) 当 Cur > LastCheck ->
    列表：反向（素数，全部）；%所有已知素数和列表中剩余的所有素数（未筛选）都是素数    
sieve({Pid,Ref},Primes, All=[Cur|_], LastCheck) 当 Cur > LastCheck ->
    皮德！{Ref,lists:reverse(Primes, All)};
筛子（参考，质数，[Cur|All2]，LastCheck）->
    %%All3 = lists:filter(fun(X) -> X rem Cur =/= 0 end, All2),
    All3 = lists_filter(Cur,All2),
    筛子（参考，[Cur|Primes]，All3，LastCheck）。


列表过滤器（Cur，All2）->
    列表过滤器（Cur，All2，[]）。

列表过滤器（V，[H|T]，L）->
    案例 H rem V 的
    0 ->
        列表过滤器（V，T，L）；
    _ ->
        列表过滤器（V，T，[H|L]）
    结尾;
列表过滤器（_，[]，L）->
    列表：反向（L）。



%% 这是一个草率的实现；）
spawn_sieve（全部，最后一个）->
    %% 拆分工作
    {L1,L2} = 列表：拆分（圆形（长度（全部）/2），全部），
    过滤器 = 过滤器（全部，最后一个），
    %%io:format("F:~p~n",[过滤器]),
    L3 = 列表：追加（过滤器，L2），
    %%io:format("L1:~w~n",[L1]),
    %% io:format("L2:~w~n",[L3]),
    %%lists_filter(Cur,All2,[])。
    PID =自我（），
    Ref1=make_ref(),
    Ref2=make_ref(),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref1},L1,Last]),
    erlang:spawn(?MODULE,sieve,[{Pid,Ref2},L3,Last]),
    Res1=接收
         {Ref1,R1} ->
         {1,R1};
         {Ref2,R1} ->
         {2,R1}
     结尾，
    Res2=接收
          {Ref1,R2} ->
          {1,R2};
          {Ref2,R2} ->
          {2,R2}
      结尾，
    apnd（过滤器，Res1，Res2）。


过滤器([H|T],Last) 当 H
    [H|过滤器(T,Last)];
过滤器（[H|_]，_）->
    [H];
过滤器（_，_）->
    []。


apnd(过滤器,{1,N1},{2,N2}) ->
    列表：追加（N1，减（N2，过滤器））；
apnd(过滤器,{2,N2},{1,N1}) ->
    列表：追加（N1，减去（N2，过滤器））。



减([H|L],[H|T]) ->
    减（L，T）；
减(L=[A|_],[B|_]) 当 A > B ->
    大号;
减去（L，[_|T]）->
    减（L，T）；
减法（L，[]）->
    L.

score 1 · Accepted Answer

你可以给你的老板看这个：http ://www.sics.se/~joe/apachevsyaws.html 。其他一些（经典？）erlang参数是：

- 不间断操作，可以动态加载新代码。

- 易于调试，不再需要分析核心转储。

- 易于使用多核/CPU

- 易于使用集群可能吗？

-谁想处理指针和东西？这不是21世纪吗？;)

一些缺陷： - 写东西可能看起来简单快捷，但性能可能很差。如果我想快速做一些事情，我通常最终会编写相同功能的 2-4 个不同版本。通常，您需要对可能与使用的问题略有不同的问题采取鹰眼态度。

在列表中查找 > 大约 1000 个元素的内容很慢，请尝试使用 ets 表。
字符串“abc”占用的空间比 3 个字节多得多。所以尝试使用二进制文件，（这很痛苦）。

总而言之，我认为在用 erlang 编写东西时，性能问题始终是需要牢记的。Erlang 的家伙需要解决这个问题，我认为他们会的。

score 1 · Accepted Answer

在这里查看 4 种不同的实现，用于在 Erlang 中查找素数（其中两个是“真正的”筛子）和性能测量结果：

http://caylespandon.blogspot.com/2009/01/in-euler-problem-10-we-are-asked-to.html

score 1 · Accepted Answer

足够简单，完全实现算法，并且不使用库函数（仅模式匹配和列表理解）。确实不是很强大。我只是试图让它尽可能简单。

-module(primes).
-export([primes/1, primes/2]).

primes(X) -> sieve(range(2, X)).
primes(X, Y) -> remove(primes(X), primes(Y)).

range(X, X) -> [X];
range(X, Y) -> [X | range(X + 1, Y)].

sieve([X]) -> [X];
sieve([H | T]) -> [H | sieve(remove([H * X || X <-[H | T]], T))].

remove(_, []) -> [];
remove([H | X], [H | Y]) -> remove(X, Y);
remove(X, [H | Y]) -> [H | remove(X, Y)].

score 0 · Accepted Answer

这是我的 Eratophenes 实施 C&C 的筛子：

    -module(sieve).
    -export([find/2,mark/2,primes/1]).

    primes(N) -> [2|lists:reverse(primes(lists:seq(2,N),2,[]))].

    primes(_,0,[_|T]) -> T;
    primes(L,P,Primes) -> NewList = mark(L,P),
        NewP = find(NewList,P),
        primes(NewList,NewP,[NewP|Primes]).

    find([],_) -> 0;
    find([H|_],P) when H > P -> H;
    find([_|T],P) -> find(T,P). 


    mark(L,P) -> lists:reverse(mark(L,P,2,[])).

    mark([],_,_,NewList) -> NewList;
    mark([_|T],P,Counter,NewList) when Counter rem P =:= 0 -> mark(T,P,Counter+1,[P|NewList]);
    mark([H|T],P,Counter,NewList) -> mark(T,P,Counter+1,[H|NewList]).

score 0 · Accepted Answer

这是我的样本

S = lists:seq(2,100),
lists:foldl(fun(A,X) -> X--[A] end,S,[Y||X<-S,Y<-S,X<math:sqrt(Y)+1,Y rem X==0]).

:-)

score -1 · Accepted Answer

到目前为止，我最快的代码（比 Andrea 的更快）是使用数组：

-module(seed4).
-export([get/1]).

get(N) -> WorkList = array:new([{size, N}, {default, empty}]),
          get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
                                              NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
                                              get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).


markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
                                                                 markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
                                                           markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = array:get(Iterator - 1, WorkList),
                                        if
                                          I =:= empty -> Iterator;
                                          true -> findNextPrime(Iterator + 1, N, WorkList)
                                        end.

replace(N, L, New) -> array:set(N - 1, New, L).

erlang - Erlang 中的 Eratosthenes 筛

12 回答 12

Related

Reference