Prolog 재귀 순서가 중요합니까?

무엇이든 최적화 할 때 먼저 측정해야합니다! (우리 대부분은 이것을 잊는 경향이 있습니다 ....)

Prolog를 최적화 할 때 다음 사항을 확인하십시오.

• 꼬리 재귀는 더 나은 경향이 있습니다 (그러므로 "일련의 명령문 전후"질문이 있습니다).
• 필요하지 않은 선택 지점을 만들지 마십시오 (Prolog 구현에 따라 다름).
• 최적의 알고리즘을 사용하십시오 (예 : 필요하지 않은 경우 목록을 두 번 탐색하지 마십시오).

다소 표준 Prolog 구현에 대해 "최적화 된"솔루션은 약간 다를 수 있습니다. 이름을 지정하겠습니다 list_uniq(명령 줄 uniq도구 와 유사 ).

list_uniq ([], []). % 기본 케이스 
list_uniq ([H | T], U) : 
    -list_uniq_1 (T, H, U). % 도우미 술어
 
list_uniq_1 ([], X, [X]). 
list_uniq_1 ([H | T], X, U) 
    :-( 
    H == X- > list_uniq_1 (T, X, U) 
    ; [X | U1] = U, 
        list_uniq_1 (T, H, U1) 
    ).

그것은 다른 reduce0/2것이 사용하기 때문에 @CapelliC에 의해 지체 의 고유 비 결정론하지 않도록 [X|Xs]하고 [X,X|Xs]첫 번째 인수를.

이제 "최적화"되었다고 주장합니다.

• 목록을 정확히 한 번 순회합니다 (반전 할 필요 없음).
• 그것은 꼬리 재귀
• 선택 포인트를 생성 및 폐기하지 않습니다.

@CapelliC와 동일한 12 가지 추론을 얻게되며, 더 긴 목록을 사용하면 차이점을 볼 수 있습니다.

?-길이 (As, 100000), 맵리스트 (= (a), As), 
   길이 (Bs, 100000), 맵리스트 (= (b), Bs), 
   길이 (Cs, 100000), 맵리스트 (= (c), Cs), 
   append ([As, Bs, Cs, As, Cs, Bs], L), 
   time (list_uniq (L, U)). 
% 600,006 추론, 0.057 초 동안 0.057 CPU (100 % CPU, 10499893 입술) 
As = [a, a, a, a, a, a, a, a, a | ...], 
Bs = [b, b, b, b, b, b, b, b, b | ...], 
Cs = [c, c, c, c, c, c, c, c, c | ...], 
L = [a, a, a, a, a, a, a, a, a | ...], 
U = [a, b, c, a, c, b].

와 같은 쿼리 reduce0, reduce1, reduce2CapelliC의 대답 @에서 :

% 감소 0 (L, U) 
% 600,001 추론, 0.125 CPU 0.125 초 (100 % CPU, 4813955 입술) 
% 감소 1 (L, U) 
% 1,200,012 추론, 0.393 CPU 0.394 초 (100 % CPU, 3050034 입술) 
% 감소 2 (L, U) 
% 2,400,004 추론, 0.859 CPU 0.861 초 (100 % CPU, 2792792 입술)

따라서 컷 ( !)을 사용하여 선택 포인트를 만들고 버리는 것도 대가가 있습니다.

그러나은 list_uniq/2첫 번째 인수가 근거가 아닌 쿼리에 대해 잘못 될 수 있습니다.

?-list_uniq ([a, B], [a, b]). 
B = b. % OK
 
?-list_uniq ([a, A], [a]). 그릇된. % 잘못되었습니다!

reduce0/2또한 reduce1/2잘못 될 수 있습니다.

?-reduce0 ([a, B], [a, b]).
그릇된. 

?-reduce1 ([a, B], [a, b]). 그릇된.

에 관해서는 이것에 대해 reduce2/2잘 모르겠습니다.

?-reduce2 ([a, A], [a, a]). 
A = a.

대신의 정의에 사용 if_/3에서 이 답변 :

list_uniq_d ([], []). % 기본 케이스 
list_uniq_d ([H | T], U) : 
    -list_uniq_d_1 (T, H, U). % Helper 술어 

list_uniq_d_1 ([], X, [X]). 
list_uniq_d_1 ([H | T], X, U) : 
        -if_ 
    (H = X, list_uniq_d_1 (T, H, U), 
        ([X | U1] = U, 
            list_uniq_d_1 (T, H, U1) 
        ) 
    ).

그것으로:

?-list_uniq_d ([a, a, a, b], U). 
U = [a, b]. 

?-list_uniq_d ([a, a, a, b, b], U). 
U = [a, b]. 

?-list_uniq_d ([a, A], U). 
A = a, 
U = [a]; 
U = [a, A], 
dif (A, a). 

?-list_uniq_d ([a, A], [a]). 
A = a; 
그릇된. % 
댕글 링 선택 점
 ?-list_uniq_d ([a, A], [a, a]). 
그릇된. 

?-list_uniq_d ([a, B], [a, b]). 
B = b. 

?-list_uniq_d ([a, A], [a, a]). 
그릇된.

시간이 더 걸리지 만 술어가 올바른 것 같습니다 . 다른 타이밍에 사용 된 것과 동일한 쿼리를 사용합니다.

% 3,000,007 inferences, 1.140 CPU in 1.141 seconds (100% CPU, 2631644 Lips)