Параллельное сито в Erlang

У меня есть код, который использует метод решета Эратосфена для генерации простых чисел до заданного предела N.

Метод:

  1. Разделить список нечетных чисел на сегменты
  2. Каждый сегмент передается процессу
  3. Сегменты просеиваются одновременно с набором 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

Я хотел бы знать, что вызывает ошибку, если я разделил список на более чем два сегмента.


person CB95    schedule 02.03.2018    source источник


Ответы (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(First,Last,2).

Это должно быть просто исправить. Просто добавьте 1 к First, если оно четное, сразу после того, как вы вычислили его внутри leaf_spawn. (редактировать: лучше сделать это здесь, при входе в leaf, чтобы его требование было ясно видно и выполнялось им самим).

Кроме того, иногда ваше самое большое простое число в Lp также включается в качестве первого простого числа в самый младший блок (например, для N=121, N=545).

person Will Ness    schedule 03.03.2018