Tamiz de eratóstenes en erlang -- performance campo con beginner campo con primes campo con sieve-of-eratosthenes campo con erlang camp codereview Relacionados El problema

Sieve of Eratosthenes in Erlang


4
vote

problema

Español

Acabo de empezar a aprender Erlang. Aquí está mi crack en la proa, basada en ( https: // www .cs.hmc.edu / ~ oneill / papeles / sieve-jfp.pdf ):

  -module(seive). -export([seive/1]).  seive(N) ->     L = lists:seq(1,N),     {Megass, Ss, Micros} = erlang:timestamp(),     S = doseive(L, 2),     {Megase, Se, Microe} = erlang:timestamp(),     {Megase-Megass, Se-Ss, Microe-Micros, S}.  doseive(L, Index) ->     Isq = Index*Index-1,     if Isq > length(L) -> [X || X <- L, X /= -1]; %done crossing out     true ->          case  lists:nth(Index, L) == -1 of         true -> doseive(L, Index + 1); %nothing to cross this pass         false ->              {L1, L2} = lists:split(Isq, L),              L3 = lists:map(fun(X) -> if X == -1 orelse (X rem Index == 0 andalso X /= Index) -> -1; true  -> X  end end , L2),              doseive(lists:append(L1, L3), Index + 1)     end end.   

Esto toma 52 segundos para generar los primeros dos millones de números primos:

  6> seive:seive(2000000). {0,19,53218,  [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,   73,79,83,89|...]}   

Esperaba que fuera más rápido en función de otras soluciones en la web.

pegado a serial (Ni siquiera he intentado una solución paralela, así que me gustaría intentarlo por primera vez), ¿cuáles son los problemas con mi código? Busqué versiones de mapa "en su lugar" para que no copie continuamente las listas en nuevas listas, lo que creo que es lo que me está matando, pero la esencia del funcionario es esta inmutable.


Si estuve en un lenguaje imperativo, le itificaría sobre un hashmap, pero no hay función "actualización de mapas" para los laps. Supongo que podría intentar acceder a los valores en un bucle, pero esta solución mejor se presta a idiomas imperativos. Sería bueno tener algo así como

  mapupdate(F, V) %updates all values for keys to V where F(key) is true   

También probé una solución con Filtro:

  doseivev2(L, Index) -> if Index > length(L) -> L; true ->     case Index > length(L) of          true -> L;         false ->             %if you do filter, you dont know what index p^2 is anymore...             doseivev2(lists:filter(fun(X) -> X =< Index orelse X rem Index /= 0 end, L), Index + 1) end end.   

Pero es Waaaay más lento. Ni siquiera termina por 1m.

Original en ingles

I just started learning Erlang. Here is my crack at the Seive, based on (https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf):

-module(seive). -export([seive/1]).  seive(N) ->     L = lists:seq(1,N),     {Megass, Ss, Micros} = erlang:timestamp(),     S = doseive(L, 2),     {Megase, Se, Microe} = erlang:timestamp(),     {Megase-Megass, Se-Ss, Microe-Micros, S}.  doseive(L, Index) ->     Isq = Index*Index-1,     if Isq > length(L) -> [X || X <- L, X /= -1]; %done crossing out     true ->          case  lists:nth(Index, L) == -1 of         true -> doseive(L, Index + 1); %nothing to cross this pass         false ->              {L1, L2} = lists:split(Isq, L),              L3 = lists:map(fun(X) -> if X == -1 orelse (X rem Index == 0 andalso X /= Index) -> -1; true  -> X  end end , L2),              doseive(lists:append(L1, L3), Index + 1)     end end. 

This takes 52 seconds to generate the first two million primes:

6> seive:seive(2000000). {0,19,53218,  [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,   73,79,83,89|...]} 

I was expecting it to be faster based on other solutions on the web.

Sticking to serial (I have not even attempted a parallel solution yet, so I'd like to try that on my own first), what are the problems with my code? I looked for "in place" versions of map so that I don't continuously copy lists into new lists, which I think is what is killing me, but the essence of functional is this immutable-ness.


If I was in an imperative language, I would iterate over a hashmap, but there is no "map-update" function for hashmaps. I guess I could try accessing values in a loop, but this solution better lends itself to imperative languages. Would be nice to have something like

mapupdate(F, V) %updates all values for keys to V where F(key) is true 

I also tried a solution with filter:

doseivev2(L, Index) -> if Index > length(L) -> L; true ->     case Index > length(L) of          true -> L;         false ->             %if you do filter, you dont know what index p^2 is anymore...             doseivev2(lists:filter(fun(X) -> X =< Index orelse X rem Index /= 0 end, L), Index + 1) end end. 

but it is WAAAAY slower. Does not even finish for 1M.

              

Lista de respuestas

1
 
vote

Lo señala, este programa copia y atraviesa las listas demasiadas veces. Debe pensar reducir el tamaño de la lista en cada iteración primordial, puede inicializar la primera lista sin todos los múltiplos de 2,3,5 (es bastante fácil), debe pasar la longitud (L) como un parámetro ( necesita recorrer la lista en cada iteración).

Dado que el algoritmo del tamiz se basa en la modificación de un conjunto de datos, la lista no es la mejor estructura de datos para trabajar. Creo que deberías tener un resultado mucho mejor con ETS.

[editar] He probado su versión en mi computadora portátil usando el temporizador: TC / 3 y encontré 24s (su medida es 19.5s, no 52S). Una versión que usa ETS y las diferentes optimizaciones que sugiero tarda 1.2s para el mismo trabajo.

Con 10000000 los tiempos son 252 y 7s, lo que sugiere que con su algoritmo, el tiempo de ejecución está aumentando más que con ETS (ración 10 y 6 para un conjunto de datos 5 veces más grande).

Último punto, está devolviendo 1 como un primo que no es correcto.

 

You point it, this program copies and traverse the lists too many times. You should think to reduce the size of the list at each prime iteration, you can initialize the first list without all the multiples of 2,3,5 (it is quite easy), you should pass length(L) as a parameter (it needs to traverse the list at each iteration).

Since the sieve algorithm is based on the modification of a set of data, the list is not the best data structure to work with. I think you should have much better result with ets.

[edit] I have tested your version on my laptop using timer:tc/3 and found 24s (your measure is 19.5s, not 52s). a version using ets and the different optimizations I suggest takes 1.2s for the same job.

With 10000000 the times are 252s and 7s, which suggests that with your algorithm the execution time is increasing more than with ets (ration 10 and 6 for a data set 5 time bigger).

Last point, you are returning 1 as a prime which is not correct.

 
 
0
 
vote

Esto detiene algunas de las respuestas y respuestas parciales de la pregunta cerrada HTTPS: / /stackoverflow.com/questions/146622/sieve-of-eratosthedes-in-erlang/389740 , junto con comparaciones de rendimiento. Todos se ejecutaron en la misma Ubuntu VM. Esperemos que esto sea útil para otros que encuentran esta pregunta y están buscando una comparación de opciones.

  %% Not really SoE according to https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf %% Θ(n^2/(log n)^2) unfaithful_sieve([]) -> []; unfaithful_sieve([H|T]) -> [H| unfaithful_sieve([ X || X <- T, X rem H /= 0 ])]; unfaithful_sieve(N) -> unfaithful_sieve(lists:seq(2, N)).  3> euler_common:stopwatch(fun() -> euler_common:unfaithful_sieve(2000000) end). Elapsed time: 325 seconds ok   

wow, eso fue lento.

  %% SoE according to https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf %% The main difference is that we clear multiples starting at each Prime^2. %% Θ(n log log n) sieve(N) ->     Array = array:new([{size, N+1}, {fixed,true}, {default, 1}]),     lists:sublist(     convert_flags_to_list_of_primes(array:to_list(sieve(Array, N, 2)), 0, []), 3, N     ).  sieve(Array, Max, Max) -> Array; sieve(Array, Max, Index) ->     case array:get(Index, Array) of     0 -> sieve(Array, Max, Index+1);     1 -> sieve(clear_multiples(Array, Index), Max, Index+1)     end.  clear_multiples(Array, Prime) -> clear_multiples(Array, Prime * Prime, Prime). clear_multiples(Array, Index, Prime) ->     case Index > array:size(Array) - 1 of     true -> Array;     false ->         clear_multiples(array:set(Index, 0, Array), Index + Prime, Prime)     end.  convert_flags_to_list_of_primes([], _Index, Primes) -> lists:reverse(Primes); convert_flags_to_list_of_primes([1|T], Index, Primes) -> convert_flags_to_list_of_primes(T, Index+1, [Index|Primes]); convert_flags_to_list_of_primes([0|T], Index, Primes) -> convert_flags_to_list_of_primes(T, Index+1, Primes).  4> euler_common:stopwatch(fun() -> euler_common:sieve(2000000) end). Elapsed time: 4 seconds ok   

Creo que uno es fiel a SOE, y obviamente es mucho más rápido. Sin embargo, es terriblemente largo.

  %% A way better solution from https://stackoverflow.com/questions/146622/sieve-of-eratosthenes-in-erlang %% (https://stackoverflow.com/users/72346/matt-h) 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  5> euler_common:stopwatch(fun() -> euler_common:primes(2000000) end). Elapsed time: 1 seconds ok   

woah. Esta es la solución proporcionada por @matt_H en respuesta a https://stackoverflow.com / Preguntas / 146622 / Sieve-of-eratostedes-in-erlang / 389740 # 389740 . Es más rápido por un tiro largo, y es conciso.

 

This pulls together some of the answers and partial answers from the closed question https://stackoverflow.com/questions/146622/sieve-of-eratosthenes-in-erlang/389740, along with performance comparisions. The were all run in the same Ubuntu VM. Hopefully this will be helpful for others who find this question and are looking for a comparison of options.

%% Not really SoE according to https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf %% xcex98(n^2/(log n)^2) unfaithful_sieve([]) -> []; unfaithful_sieve([H|T]) -> [H| unfaithful_sieve([ X || X <- T, X rem H /= 0 ])]; unfaithful_sieve(N) -> unfaithful_sieve(lists:seq(2, N)).  3> euler_common:stopwatch(fun() -> euler_common:unfaithful_sieve(2000000) end). Elapsed time: 325 seconds ok 

Wow, that was slow.

%% SoE according to https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf %% The main difference is that we clear multiples starting at each Prime^2. %% xcex98(n log log n) sieve(N) ->     Array = array:new([{size, N+1}, {fixed,true}, {default, 1}]),     lists:sublist(     convert_flags_to_list_of_primes(array:to_list(sieve(Array, N, 2)), 0, []), 3, N     ).  sieve(Array, Max, Max) -> Array; sieve(Array, Max, Index) ->     case array:get(Index, Array) of     0 -> sieve(Array, Max, Index+1);     1 -> sieve(clear_multiples(Array, Index), Max, Index+1)     end.  clear_multiples(Array, Prime) -> clear_multiples(Array, Prime * Prime, Prime). clear_multiples(Array, Index, Prime) ->     case Index > array:size(Array) - 1 of     true -> Array;     false ->         clear_multiples(array:set(Index, 0, Array), Index + Prime, Prime)     end.  convert_flags_to_list_of_primes([], _Index, Primes) -> lists:reverse(Primes); convert_flags_to_list_of_primes([1|T], Index, Primes) -> convert_flags_to_list_of_primes(T, Index+1, [Index|Primes]); convert_flags_to_list_of_primes([0|T], Index, Primes) -> convert_flags_to_list_of_primes(T, Index+1, Primes).  4> euler_common:stopwatch(fun() -> euler_common:sieve(2000000) end). Elapsed time: 4 seconds ok 

I think that one is faithful to SoE, and is obviously much faster. It's awfully long, though.

%% A way better solution from https://stackoverflow.com/questions/146622/sieve-of-eratosthenes-in-erlang %% (https://stackoverflow.com/users/72346/matt-h) 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  5> euler_common:stopwatch(fun() -> euler_common:primes(2000000) end). Elapsed time: 1 seconds ok 

Woah. This is the solution provided by @matt_h in answer to https://stackoverflow.com/questions/146622/sieve-of-eratosthenes-in-erlang/389740#389740. It's faster by a long shot, and it's concise.

 
 

Relacionados problema

10  Erlang concurrencia en los círculos  ( Erlang concurrency in circles ) 
Soy nuevo en Erlang (2 días para ser honesto) y apreciaría mucho una revisión por pares. Estoy haciendo estos ejercicios y estuvo un poco atascado en este p...

11  Algoritmo genético para "Hello World"  ( Genetic algorithm for hello world ) 
He escrito una implementación de Erlang del algoritmo genético para un programa "Hello World" como se describe aquí . Esta es mi primera vez que escriba cu...

5  Tome un número y devuelva la representación del idioma inglés  ( Take a number and return english language representation ) 
Como muchos, comencé con la programación de procedimientos. Por supuesto, al aprender un lenguaje funcional, los viejos hábitos pueden morir duro, por lo que ...

2  Código de lento Erlang para encontrar trillizos pitagóricos  ( Slow erlang code to find pythagorean triplets ) 
¿Por qué este código de Erlang toma aproximadamente un minuto en mi máquina? en Pascal, algo así, tomó menos entonces el segundo en mi máquina. ¿Qué puedo...

1  La función de aplanamiento en la lista en Erlang se siente demasiado lada  ( List flattening function in erlang feels too wordy ) 
Escribí una función de aplanamiento de la lista recursiva de cola, pero no estoy muy contento con eso. a) ¿Se necesita la recursión de la cola aquí, o la fu...

4  Simple Rock Paper Tijeras En Erlang  ( Simple rock paper scissors in erlang ) 
Soy muy nuevo en Erlang y estoy específicamente interesado en hacer mi Erlang idiomático (en otras palabras, ¿puede decir que no conozco a Erlang de este códi...

7  Código Erlang para enumerar todas las direcciones IP  ( Erlang code to list all ip addresses ) 
Este es un código Erlang que escribí para generar una cadena de todas las direcciones IP de la máquina. La cadena se imprime simplemente al usuario para que l...

6  Mapa de Newbie / Reducir el contador de frecuencia de la palabra  ( Newbie map reduce word frequency counter ) 
Te presento mi primer módulo para aprender un poco de Erlang a la espera de su escrutinio. Hace un recuento de frecuencia de palabras con mapa / reducción. So...

1  Cola prioritaria en erlang  ( Priority queue in erlang ) 
Soy nuevo en Erlang y estoy tratando de portuar mi Project Euler Soluciones en C # a Erlang. Tengo una implementación de la cola prioritaria con las pruebas...

5  Caza del tesoro de Erlang  ( Erlang treasure hunt ) 
Tengo la siguiente tarea: Crea un juego de caza de tesoros simple. Crear una matriz bidimensional de números enteros 10 por 10. En un azar Posición en ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos