performance - Prólogo: cálculo de OEIS A031877("números de reversión no triviales") utilizando clp(FD)

optimization prolog

Question

Al navegar a través de la asombrosa Enciclopedia en línea de las secuencias de enteros (véase en.wikipedia.org ), tropecé con la siguiente secuencia de números enteros:

A031877 : Números de reversión no triviales (números que son múltiplos enteros de sus reversiones), excluyendo números palindrómicos y múltiplos de 10.

Al volver a utilizar algún código que escribí para mi respuesta a la pregunta relacionada " Implementación más rápida de la aritmética verbal en Prolog ", podría escribir una solución sin esfuerzo, gracias a clpfd .

:- use_module(library(clpfd)).

Definimos la relación núcleo a031877_ndigits_/3 basada en digits_number/2 (definida anteriormente):

a031877_ndigits_(Z_big,N_digits,[K,Z_small,Z_big]) :-
K #> 1,
length(D_big,N_digits),
reverse(D_small,D_big),
digits_number(D_big,Z_big),
digits_number(D_small,Z_small),
Z_big #= Z_small * K.

La relación núcleo es determinista y termina universalmente siempre que N_digit sea ​​un entero concreto. ¡Vea usted mismo los primeros 100 valores de N_digit !

?- time((N in 0..99,indomain(N),a031877_ndigits_(Z,N,Zs),false)).
% 3,888,222 inferences, 0.563 CPU in 0.563 seconds (100% CPU, 6903708 Lips)
false

Vamos a ejecutar algunas consultas!

?- a031877_ndigits_(87912000000087912,17,_). true % succeeds, as expected ; false. ?- a031877_ndigits_(87912000000987912,17,_). false. % fails, as expected

A continuación, vamos a encontrar algunos números de inversión no triviales que comprenden exactamente cuatro dígitos decimales:

?- a031877_ndigits_(Z,4,Zs), labeling([],Zs).
Z = 8712, Zs = [4,2178,8712]
; Z = 9801, Zs = [9,1089,9801]
; false.

¡DE ACUERDO! ¡Midamos el tiempo de ejecución necesario para demostrar la finalización universal de la consulta anterior!

?- time((a031877_ndigits_(Z,4,Zs),labeling([],Zs),false)).
% 11,611,502 inferences, 3.642 CPU in 3.641 seconds (100% CPU, 3188193 Lips)
false. % terminates universally

¡Ahora, es demasiado tiempo!

¿Qué puedo hacer para acelerar las cosas? Use diferentes y / u otras restricciones? Tal vez incluso redundantes? ¿O tal vez identificar y eliminar simetrías que reducen el tamaño del espacio de búsqueda? ¿Qué hay de los diferentes dominios clp (*) (b, q, r, set)? O diferentes técnicas de consistencia / propagación? ¿O más bien Prologismo de estilo Prolog?

¿Tienes ideas? ¡Los quiero todos! Gracias por adelantado.

Answer 1

¡Podemos mejorar traduciendo las propiedades teóricas numéricas al lenguaje de las restricciones!

Todos los términos tienen la forma 87 ... 12 = 4 * 21 ... 78 o 98 ... 01 = 9 * 10 ... 89.

Implementamos a031877_ndigitsNEWER_/3 base a a031877_ndigitsNEW_/3 y directamente agregamos la propiedad anterior como dos restricciones de dominio finito:

a031877_ndigitsNEWER_(Z_big,N_digits,[K|D_big]) :- K in {4}//{9}, % (new) length(D_big,N_digits), D_big ins (0..2)//(7..9), % (new) reverse(D_small,D_big), digits_number(D_big,Z_big), digits_number(D_small,Z_small), Z_big #= Z_small * K.

Vamos a volver a ejecutar los puntos de referencia que utilizamos antes!

?- time((a031877_ndigitsNEWER_(Z,5,Zs),labeling([ff],Zs),false)).
% 73,011 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 11602554 Lips)
false.
?- time((a031877_ndigitsNEWER_(Z,6,Zs),labeling([ff],Zs),false)).
% 179,424 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 6399871 Lips)
false.
?- time((a031877_ndigitsNEWER_(Z,7,Zs),labeling([ff],Zs),false)).
% 348,525 inferences, 0.037 CPU in 0.037 seconds (100% CPU, 9490920 Lips)
false.

Resumen: para las tres consultas, observamos consistentemente una reducción significativa de la búsqueda requerida. Solo considere cuánto se redujeron los recuentos de inferencias: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

¿Podemos hacerlo aún mejor (preservando la declaratividad del código)? No lo sé, supongo que sí ...

Answer 2

Hasta ahora ... no hay respuestas :(

Se me ocurrió lo siguiente ...

¿Qué hay de usar diferentes variables para labeling/2 ?

a031877_ndigitsNEW_(Z_big,N_digits,/* [K,Z_small,Z_big] */ [K|D_big]) :- K #> 1, length(D_big,N_digits), reverse(D_small,D_big), digits_number(D_big,Z_big), digits_number(D_small,Z_small), Z_big #= Z_small * K.

¡Midamos algunos tiempos de ejecución!

?- time((a031877_ndigits_(Z,4,Zs),labeling([ff],Zs),false)).
% 14,849,250 inferences, 4.545 CPU in 4.543 seconds (100% CPU, 3267070 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,4,Zs),labeling([ff],Zs),false)).
% 464,917 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 8962485 Lips)
false.

¡Mejor! ¿Pero podemos ir más allá?

?- time((a031877_ndigitsNEW_(Z,5,Zs),labeling([ff],Zs),false)).
% 1,455,670 inferences, 0.174 CPU in 0.174 seconds (100% CPU, 8347374 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,6,Zs),labeling([ff],Zs),false)).
% 5,020,125 inferences, 0.614 CPU in 0.613 seconds (100% CPU, 8181572 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,7,Zs),labeling([ff],Zs),false)).
% 15,169,630 inferences, 1.752 CPU in 1.751 seconds (100% CPU, 8657015 Lips)
false.

Todavía hay mucho margen de mejora, ¡seguro! Debe haber ...