Prolog: tính OEIS A031877 ("số đảo ngược không tầm thường") sử dụng CLP (FD)

Question

Duyệt qua tuyệt vờiOn-Line Encyclopedia of Integer Sequences (x en.wikipedia.org), tôi stumbled khi dãy số nguyên sau:

A031877: Số đảo ngược không đặc biệt (số là bội số nguyên của số lần đảo ngược của chúng), không bao gồm số palindromic và bội số của 10.

Bằng cách tái sử dụng một số mã tôi đã viết cho câu trả lời của tôi cho th e câu hỏi liên quan "Faster implementation of verbal arithmetic in Prolog" Tôi có thể viết ra một giải pháp khá dễ dàng - nhờ clpfd!

:- use_module(library(clpfd)). 

Chúng ta định nghĩa mối quan hệ lõia031877_ndigits_/3 dựa trên digits_number/2 (được định nghĩa trước đó):

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. 

Mối quan hệ cốt lõi được xác định và chấm dứt phổ bất cứ khi nào N_digit là một số nguyên bê tông . Tự mình xem 100 giá trị đầu tiên của 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 

Hãy chạy một số truy vấn!

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

?- a031877_ndigits_(87912000000987912,17,_). 
false.        % fails, as expected 

Tiếp theo, hãy tìm một số con số đảo ngược không tầm thường bao gồm chính xác bốn thập phân-chữ số:

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

OK! Hãy đo thời gian chạy cần thiết để chứng minh việc chấm dứt toàn bộ truy vấn trên!

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

Bây giờ, đó là cách quá dài!

Tôi có thể làm gì để tăng tốc độ? Sử dụng các ràng buộc khác và/hoặc các ràng buộc khác? Có lẽ ngay cả những người thừa? Hoặc có thể xác định và loại bỏ các đối xứng làm giảm kích thước không gian tìm kiếm? Điều gì về các lĩnh vực clp (*) khác nhau (b, q, r, set)? Hoặc các kỹ thuật thống nhất/tuyên truyền khác nhau? Hay đúng hơn là Prolog phong cách coroutining?

Bạn có ý tưởng? Tôi muốn tất cả! Cảm ơn trước.

Answer 1

... Cho đến nay không có câu trả lời :(

tôi đã đưa ra những điều sau ...

Làm thế nào về việc sử dụng các biến khác nhau cho 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. 

Hãy đo một số runtimes!

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

Tốt hơn! Nhưng chúng ta có thể đi xa hơn không?

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

Vẫn còn nhiều chỗ để cải thiện! Phải có ...

Answer 2

Chúng tôi có thể làm tốt hơn bằng cách dịch các thuộc tính lý thuyết số thành ngôn ngữ của các ràng buộc!

Tất cả các cụm từ có dạng 87 ... 12 = 4 * 21 ... 78 hoặc 98 ... 01 = 9 * 10 ... 89.

Chúng tôi thực hiện a031877_ndigitsNEWER_/3 dựa trên a031877_ndigitsNEW_/3 và thêm trực tiếp trên tài sản là hai trở ngại hữu hạn tên miền:

 
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. 

Hãy chạy lại các tiêu chuẩn, chúng tôi sử dụng trước đó!

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

Tóm tắt: Đối với ba truy vấn, chúng tôi luôn quan sát thấy giảm đáng kể yêu cầu tìm kiếm. Chỉ cần xem xét số lượng suy luận suy giảm: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

Chúng tôi có thể làm tốt hơn nữa (trong khi vẫn giữ được tính cắt xén của mã) không? Tôi không biết, tôi đoán vậy ...