Пролог: реализовать алгоритм Луна с эффективностью

Question

Я пытаюсь применить алгоритм Луна в SWI-Prolog. Но у меня проблемы с запуском. Когда я тестирую несколько простых чисел, например, 123, результат получается быстро. Если я тестирую более длинный номер, например 5379173895860200, он работает так долго, что я могу только прервать это выполнение. Нужна помощь в поиске проблемы. код:

luhn(N):- 
    spliter(N,Y), 
    reverse(Y, Z), 
    check(Z,X), 
    sum_all(X, Res), 
    T is Res mod 10, 
    T is 0. 

spliter(0,[]). 
spliter(N,L):- 
    N1 is floor(N/10), 
    X is N mod 10, 
    spliter(N1, L2), 
    L = [X|L2]. 

check(A,B):- 
    double(A,B,_). 

double([],[],0). 
double([H|T], [H1|T1], C):- 
    double(T,T1, C1), 
    C is C1 +1, 
    H1 is H*(1+ C mod 2). 

sum_all([],0). 
sum_all([H|T],Sum):- 
    sum_all(T,Subsum), 
    X is floor(H/10), 
    Y is H mod 10, 
    Sum is (Subsum + X + Y). 

Answer 1

Вот мой перевод Python от Wikipedia

is_luhn_valid(Card_number):- 
    luhn_checksum(Card_number, 0). 

luhn_checksum(Card_number, Checksum) :- 
    digits_of(Card_number, Digits), 
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 0), Odd_digits), 
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 1), Even_digits), 
    sum_list(Odd_digits, Checksum_t), 
    findall(S, (
     member(T, Even_digits), 
     T1 is T * 2, 
     digits_of(T1, D1), 
     sum_list(D1, S) 
    ), St), 
    sum_list(St, St1), 
    Checksum is (Checksum_t + St1) mod 10. 

digits_of(Number, Digits) :- 
    number_codes(Number, Cs), 
    maplist(code_digit, Cs, Digits). 
code_digit(C, D) :- D is C - 0'0. 

друг от друга быть более многословным, это кажется правильным WRT тестовый пример из приведенной выше страницы. Но:

?- is_luhn_valid(123). 
false. 

в то время как ваш код:

?- luhn(123). 
true ; 
true ; 
... 

и, конечно

?- luhn(124). 
.... 

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

фрагмент следа:

?- leash(-all),trace. 
true. 

[trace] ?- luhn(124). 
    Call: (7) so:luhn(124) 
    Call: (8) so:spliter(124, _G9437) 
... 
    Exit: (8) 2 is 12 mod 10 
    Call: (8) 2 is 0 
    Fail: (8) 2 is 0 
    Redo: (11) so:spliter(0, _G9461) 
    Call: (12) _G9465 is floor(0/10) 
... 

Проблема, кажется, что сплитер/2 добавляет 0s перед последовательностью, в то время как вместо этого он должен выйти из строя.

Об эффективности: мой фрагмент кода можно переписать в виде

luhn_checksum(Card_number, Checksum) :- 
    digits_of(Card_number, Digits), 
    aggregate_all(sum(V), (
     nth0(I, Digits, D), 
     ( I mod 2 =:= 0 
     -> V = D   % Odd_digits 
     ; Dt is D * 2, % Even_digits 
      digits_of(Dt, Ds), 
      sum_list(Ds, V) 
     )), 
     Checksum_t), 
    Checksum is Checksum_t mod 10. 

использования библиотеки (aggregate)

редактировать

Я думаю сплитер/2 должны проверить, если N> 0, в противном случае он будет возвращаться навсегда ... try

spliter(N,L):- N>0, 
    N1 is floor(N/10), 
    ... 

Answer 2

Нет необходимости брать большое количество, чтобы увидеть проблему с вашим кодом. Достаточно рассмотреть luhn(1), который также петли и «эффективный» luhn(0).

Проблема, которая у вас есть, - это не эффективность, а прекращение. Прекращение - очень тонкое понятие в Prolog. Если вы используете Prolog через петлю toplevel, многие системы показывают вам только первый ответ. И некоторые даже не показывают никакого дальнейшего ответа, если запрос не содержит переменных. Таким образом, вы можете легко получить ложное впечатление о том, что ваша программа работает и завершается, когда на самом деле это не так.

Существует очень простой способ, как вы можете протестировать завершение в любой системе. Просто добавьте цель false на ваш запрос. Теперь даже luhn(0),false Петли.

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

 
luhn(N):- 
    spliter(N,Y), false, 
    reverse(Y, Z), 
    check(Z,X), 
    sum_all(X, Res), 
    T is Res mod 10, 
    T is 0. 

spliter(0,[]) :- false. 
spliter(N,L):- 
    N1 is floor(N/10), 
    X is N mod 10, 
    spliter(N1, L2), false, 
    L = [X|L2]. 

Эта крошечная часть вашей программы (называется failure-slice) достаточно, чтобы понять незавершение. Фактически любое целое число N приведет к циклу. Вам нужно просто добавить N > 0 как первый гол spliter/2.

Для более см failure-slice

^{Fine печати
1 На самом деле, это будет работать только в чистых, монотонных программ, как программы.}