Erlang 中的并发筛选

Question

我有一个代码使用埃拉托色尼筛法生成不超过给定限制 N 的素数。

方法：

将奇数列表拆分成段
每个段都传递给一个进程
片段与集合 Lp 同时筛选

代码如下：

%---------------------------------------------------------------------------------   
primes(N) ->
    simple_sieve(lists:seq(3,N,2),[],N).

    simple_sieve(Lin,Lp,N) -> [H|_] = Lin,
        case H*H < N of
               true -> simple_sieve([X || X <- Lin, X rem H =/= 0], [H|Lp], N);
               false -> lists:reverse(Lp) ++ Lin
        end.

%---------------------------------------------------------------------------------
primes_parr(N, Num_blocks) -> 
    Pid_stem = self(),
    SQ = round(math:sqrt(N)),
    Lp = primes(SQ), io:fwrite("List of primes: ~w~n", [Lp]),
    Block_size = round(N/Num_blocks),
    ok = leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks),  
    stem_loop(Lp, 0, Num_blocks).

stem_loop(Lp, Primes, 0) ->
    1 + length(Lp) + Primes;
stem_loop(Lp, Primes, Num_blocks) ->
    receive
    {leaf_done, _, Leaf_nums} ->
        stem_loop(Lp, Primes+Leaf_nums, Num_blocks-1)
    end.

leaf_spawn(_, _, _, _, 0) -> ok;
leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks) ->
    case (Num_blocks==1) of
    true -> case (SQ rem 2 == 0) of
            true -> Start = SQ+1;
            false -> Start = SQ
        end;
    false -> Start = 1
    end,
    First = (Num_blocks-1)*Block_size + Start, 
    Last = Num_blocks*Block_size,
    io:fwrite("Start: ~w | Finish: ~w ~n", [First,Last]),   
    spawn(fun() -> leaf(Pid_stem, Num_blocks, First, Last, [], Lp) end), 
    leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks-1).

leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, []) -> 
    L = ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)), 
    io:fwrite("The sublist is: ~w~n", [L]),
    Pid_stem ! {leaf_done, Leaf_id, length(ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)))};
leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, [H|T]) ->
    case (H*H =< Last)  of
    true -> 
        case H*H >= First of
        true ->
            leaf(Pid_stem, Leaf_id, First, Last, lists:seq(H*H, Last, 2*H) ++ Leaf_nums, T);
        false ->
            K = round((First - H*H)/(2*H)),
            leaf(Pid_stem, Leaf_id, First, Last, lists:seq(H*H + 2*K*H, Last, 2*H) ++ Leaf_nums, T)
        end;
    false -> 
        leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, [])
    end.

如果我调用函数 primes_parr(100,2)，代码工作正常。给我输出：

List of primes(Lp): [3,5,7]
Start: 51 | Finish: 100 
Start: 11 | Finish: 50 
The sublist is: [53,59,61,67,71,73,79,83,89,97]
The sublist is: [11,13,17,19,23,29,31,37,41,43,47]
25    %no. of primes

但是如果我调用primes_parr(100,3)，输出就无效了。输出为：

List of primes(Lp): [3,5,7]
Start: 67 | Finish: 99 
Start: 34 | Finish: 66 
Start: 11 | Finish: 33 
The sublist is: [67,71,73,79,83,89,97]
The sublist is: [34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66]
The sublist is: [11,13,17,19,23,29,31]
35   %no. of primes

如果我将列表分成两个以上的部分，我想知道是什么导致了错误。

Answer 1

根据您的无效输出判断

The sublist is: [67,71,73,79,83,89,97]
The sublist is: [34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66] %% HERE
The sublist is: [11,13,17,19,23,29,31]

某处您的代码假定要筛选的范围的 起始数 是奇数 .

的确如此，

leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, []) -> 
    L = ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)), 
    io:fwrite("The sublist is: ~w~n", [L]),
    Pid_stem ! {leaf_done, Leaf_id, length(L)};      %% reuse the L !!

假设First是奇数，当它计算lists:seq(<b>First</b>,Last,<b>2</b>)。

这应该很容易修复。如果 First 是偶数，只需在 leaf_spawn 中计算后立即将 1 添加到 First。（编辑： 最好在进入 leaf 时在此处执行此操作，因此它的要求可以清楚地看到并由它自己执行）。

此外，有时您在 Lp 中的最大素数也包含在最低块中作为第一个素数（例如 N=121、N=545）。

Erlang 中的并发筛选

Concurrent Sieve in Erlang

parallel-processing

concurrency

erlang

sieve

sieve-of-eratosthenes