Решето Эратосфена в [закрытом] Erlang

Многие объяснения уже присутствуют, чтобы объяснить, как это происходит и как это исправить, но вы также должны следовать рекомендациям, чтобы избежать NullPointerException вообще.

См. также: A хороший список лучших практик

Я бы добавил, очень важно, хорошо использовать модификатор final. Использование "окончательной" модификатор, когда это применимо в Java

Сводка:

  1. Используйте модификатор final для обеспечения хорошей инициализации.
  2. Избегайте возврата null в методы, например, при возврате пустых коллекций.
  3. Использовать аннотации @NotNull и @Nullable
  4. Быстрое завершение работы и использование утверждений, чтобы избежать распространения нулевых объектов через все приложение, когда они не должен быть пустым.
  5. Сначала используйте значения с известным объектом: if("knownObject".equals(unknownObject)
  6. Предпочитают valueOf() поверх toString ().
  7. Используйте null safe StringUtils StringUtils.isEmpty(null).

17
задан Emre Yazici 6 July 2011 в 21:05
поделиться

10 ответов

Вот является простое (но не ужасно быстро) реализацией решета:

-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)).
13
ответ дан 30 November 2019 в 12:37
поделиться

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

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

Берет приблизительно 2,8 мс для вычисления начал до 2 миллиметров на мой Mac на 2 ГГц

9
ответ дан 30 November 2019 в 12:37
поделиться

Я приблизился к проблеме при помощи параллельной обработки.

Источник

2
ответ дан 30 November 2019 в 12:37
поделиться

Мое предыдущее сообщение не стало отформатированным правильно. Вот пересообщение кода. Извините за спам...


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

2
ответ дан 30 November 2019 в 12:37
поделиться

Я не изучил их подробно, но я протестировал свою реализацию ниже (что я записал для Euler проблемы Проекта), и это - порядки величины быстрее, чем вышеупомянутые две реализации. Это было мучительно медленно, пока я не устранил некоторые пользовательские функции и вместо этого искал списки: функции, которые сделали бы то же. Хорошо извлечь урок, чтобы всегда видеть, существует ли реализация библиотеки чего-то, что необходимо сделать - это обычно будет быстрее! Это вычисляет сумму начал до 2 миллионов за 3,6 секунды на iMac на 2.8 ГГц...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.
1
ответ дан 30 November 2019 в 12:37
поделиться

Мне отчасти нравятся этот предмет, начала то есть, таким образом, я начал изменять код BarryE немного и меня manged для создания его приблизительно на 70% быстрее путем создания моей собственной функции lists_filter и позволил использовать оба из своих центральных процессоров. Я также облегчил подкачивать между к двум версиям. Тестовый прогон показывает:

61> timer:tc(test,sum_primes,[2000000]).
{2458537,142913970581}

Код:



-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),
    %%io:format("F:~p~n",[Filters]),
    L3 = lists:append(Filters,L2),
    %%io:format("L1:~w~n",[L1]),
    %%    io:format("L2:~w~n",[L3]),
    %%lists_filter(Cur,All2,[]).
    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.
1
ответ дан 30 November 2019 в 12:37
поделиться

Вы могли показать Вашему боссу это: http://www.sics.se/~joe/apachevsyaws.html . И некоторый другой (классик?) erlang аргументы:

- безостановочная операция, новый код может быть загружен на лету.

- легкий отладить, больше дампов ядра для анализа.

- легкий использовать многоядерные / центральные процессоры

- легкий использовать кластеры, возможно?

- кто хочет иметь дело с указателями и материалом? Разве это не 21-й век?;)

Некоторый pifalls: - это могло бы выглядеть легким и быстрым для записи чего-то, но производительность может высосать. Если я хочу сделать что-то быстро, что я обычно заканчиваю тем, что писал 2-4 различных версии той же функции. И часто необходимо проявить глазной подход ястреба к проблемам, которые могли бы немного отличаться от того, что каждый используется также.

  • ищущие вещи в списках> приблизительно 1 000 элементов являются медленными, попытайтесь использовать ets таблицы.

  • строка "abc" занимает намного больше места, чем 3 байта. Так попытайтесь использовать двоичные файлы, (который является болью).

, В целом, я думаю, что проблема производительности - что-то для учета в любом случае при записи чего-то в erlang. Чуваки Erlang должны разработать это, и я думаю, что они будут.

1
ответ дан 30 November 2019 в 12:37
поделиться

Взгляните здесь для нахождения 4 различных реализаций для нахождения простых чисел в Erlang (два из которых являются "реальными" решетами), и для результатов измерения производительности:

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

1
ответ дан 30 November 2019 в 12:37
поделиться

мой самый быстрый код до сих пор (быстрее, чем 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).
-1
ответ дан 30 November 2019 в 12:37
поделиться

Достаточно простой, реализует в точности алгоритм и не использует никаких библиотечных функций (только сопоставление с образцом и понимание списка). Действительно, не очень мощный. Я только попытался сделать это как можно проще.

-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)].
1
ответ дан 30 November 2019 в 12:37
поделиться
Другие вопросы по тегам:

Похожие вопросы: