performance - practica - programacion de cuellos de botella

¿Cuál es el cuello de botella en este predicado relacionado con las primes?

Question

Así que aquí está: estoy tratando de calcular la suma de todos los primos por debajo de dos millones (para este problema ), pero mi programa es muy lento. Sé que el algoritmo en sí mismo es terriblemente malo y uno de fuerza bruta, pero parece mucho más lento de lo que debería.
Aquí limito la búsqueda a 20,000 para que el resultado no se espere demasiado.
No creo que este predicado sea difícil de entender, pero lo explicaré de todos modos: calculo la lista de todos los primos por debajo de 20,000 y luego los sumo. La parte de suma está bien, la parte de primos es realmente lenta.

problem_010(R) :-
    p010(3, [], Primes),
    sumlist([2|Primes], R).
p010(20001, Primes, Primes) :- !.
p010(Current, Primes, Result) :-
    (
        prime(Current, Primes)
    ->  append([Primes, [Current]], NewPrimes)
    ;   NewPrimes = Primes
    ),
    NewCurrent is Current + 2,
    p010(NewCurrent, NewPrimes, Result).
prime(_, []) :- !.
prime(N, [Prime|_Primes]) :- 0 is N mod Prime, !, fail.
prime(ToTest, [_|Primes]) :- prime(ToTest, Primes).

Me gustaría conocer algo sobre por qué es tan lento. ¿Es una buena implementación del estúpido algoritmo de fuerza bruta, o hay alguna razón que hace que Prolog caiga?

EDITAR: Ya encontré algo, al agregar nuevos números primos en lugar de dejarlos en el encabezado de la lista, tengo números primos que aparecen con mayor frecuencia al inicio, por lo que es ~ 3 veces más rápido. Todavía necesito alguna idea, aunque :)

Answer 1

Considere usar por ejemplo un método de tamiz ("Tamiz de Eratóstenes"): Primero cree una lista [2,3,4,5,6, .... N], usando por ejemplo numlist / 3. El primer número en la lista es un primo, guárdelo. Elimine sus múltiplos del resto de la lista. El siguiente número en la lista restante es nuevamente un primo. Nuevamente elimine sus múltiplos. Y así. La lista se reducirá con bastante rapidez y terminarás solo con primos restantes.

Answer 2

OK, antes de editar, el problema era solo el algoritmo (imho). Como ha notado, es más eficiente verificar si el número está dividido primero por los primos más pequeños; en un conjunto finito, hay más números divisibles por 3 que por 32147.

Otra mejora del algoritmo es detener la comprobación cuando los números primos son mayores que la raíz cuadrada del número.

Ahora, después de su cambio, hay algunos problemas de prólogo: utiliza append / 3. append / 3 es bastante lento, ya que debe recorrer toda la lista para colocar el elemento al final. En su lugar, debe usar listas de diferencias, lo que hace que colocar el elemento en la cola sea realmente rápido.

Ahora, ¿qué es una lista de diferencias? En lugar de crear una lista normal [1,2,3], se crea esta [1,2,3 | T]. Tenga en cuenta que dejamos la cola desinstalada. Entonces, si queremos agregar un elemento (o más) al final de la lista, podemos simplemente decir T = [4 | NT]. ¿increíble?

La siguiente solución (acumular números primos en orden inverso, detener cuando prime> sqrt (N), listas de diferencias para adjuntar) toma 0.063 para 20k primos y 17seg para primos de 2m mientras que su código original tomó 3.7sec para 20k y el append / 3 versión 1.3 segundo.

problem_010(R) :-
    p010(3, Primes, Primes),
    sumlist([2|Primes], R).
p010(2000001, _Primes,[]) :- !.                                %checking for primes till 2mil
p010(Current, Primes,PrimesTail) :-
    R is sqrt(Current),
    (
        prime(R,Current, Primes)
    ->  PrimesTail = [Current|NewPrimesTail]
    ;   NewPrimesTail = PrimesTail
    ),
    NewCurrent is Current + 2,
    p010(NewCurrent, Primes,NewPrimesTail).
prime(_,_, Tail) :- var(Tail),!.
prime(R,_N, [Prime|_Primes]):-
    Prime>R.
prime(_R,N, [Prime|_Primes]) :-0 is N mod Prime, !, fail.
prime(R,ToTest, [_|Primes]) :- prime(R,ToTest, Primes).

también, considerando agregar los números mientras los generas para evitar el o (n) adicional debido a la suma / 2
Al final, siempre puede implementar el algoritmo AKS que se ejecuta en tiempo polinomial (XD)

Answer 3

En primer lugar, agregar al final de una lista usando append/3 es bastante lento. Si debe hacerlo, utilice listas de diferencias en su lugar. (Personalmente, trato de evitar append/3 tanto como sea posible)

En segundo lugar, su prime/2 siempre itera sobre toda la lista al verificar un primo. Esto es innecesariamente lento. En su lugar, puede verificar su id para encontrar un factor integral hasta la raíz cuadrada del número que desea verificar.

problem_010(R) :-
    p010(3, 2, R).
p010(2000001, Primes, Primes) :- !.
p010(Current, In, Result) :-
    ( prime(Current) -> Out is In+Current ; Out=In ),
    NewCurrent is Current + 2,
    p010(NewCurrent, Out, Result).

prime(2).
prime(3).
prime(X) :-
    integer(X),
    X > 3,
    X mod 2 =/= 0,
    /+is_composite(X, 3).   % was: has_factor(X, 3)

is_composite(X, F) :-       % was: has_factor(X, F) 
    X mod F =:= 0, !.
is_composite(X, F) :- 
    F * F < X,
    F2 is F + 2,
    is_composite(X, F2).

Descargo de responsabilidad: Encontré esta implementación de prime/1 y has_factor/2 mediante google.

Este código da:

?- problem_010(R).
R = 142913828922
Yes (12.87s cpu)

Aquí hay un código aún más rápido:

problem_010(R) :-
    Max = 2000001,
    functor(Bools, [], Max),
    Sqrt is integer(floor(sqrt(Max))),
    remove_multiples(2, Sqrt, Max, Bools),
    compute_sum(2, Max, 0, R, Bools).

% up to square root of Max, remove multiples by setting bool to 0
remove_multiples(I, Sqrt, _, _) :- I > Sqrt, !.
remove_multiples(I, Sqrt, Max, Bools) :-
    arg(I, Bools, B),
    (
        B == 0
    ->
        true % already removed: do nothing
    ;
        J is 2*I, % start at next multiple of I
        remove(J, I, Max, Bools)
    ),
    I1 is I+1,
    remove_multiples(I1, Sqrt, Max, Bools).

remove(I, _, Max, _) :- I > Max, !.
remove(I, Add, Max, Bools) :-
     arg(I, Bools, 0), % remove multiple by setting bool to 0
     J is I+Add,
     remove(J, Add, Max, Bools).

% sum up places that are not zero
compute_sum(Max, Max, R, R, _) :- !.
compute_sum(I, Max, RI, R, Bools) :-
    arg(I, Bools, B),
    (B == 0 -> RO = RI ;  RO is RI + I ),
    I1 is I+1,
    compute_sum(I1, Max, RO, R, Bools).

Esto corre un orden de magnitud más rápido que el código que di más arriba:

?- problem_010(R).
R = 142913828922
Yes (0.82s cpu)

Answer 4

Primero, Prolog no falla aquí.

Hay formas muy inteligentes de generar números primos. ¡Pero como un comienzo barato simplemente acumula los primos en orden inverso! (7.9s -> 2.6s) De esta manera, los más pequeños se prueban antes. Luego, considere probar solo contra primos hasta 141. Los primos más grandes no pueden ser un factor.

Entonces, en lugar de avanzar solo a través de números que no son divisibles por 2, puede agregar 3, 5, 7.

Hay personas que escriben artículos sobre este "problema". Véase, por ejemplo, este documento , aunque es un poco sofisticado discutir cuál fue el algoritmo "genuino" en realidad, hace 22 siglos cuando se celebró la última versión del ábaco como tabletas de Salamina .