Bawiłem się zpermutation w kilku programach i natknął się na ten mały eksperyment:

Metoda permutacji 1:

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

Metoda permutacji 2:

permute([], []).
permute(L, [P | P1]) :-
    select(P, L, L1),
    permute(L1, P1).

Metoda permutacji 3 (użyj wbudowanego):

permute(L, P) :- permutation(L, P).

Rozumiem, że dobrą praktyką jest używanie rekurencji ogonowej, a generalnie używanie wbudowanych ma być wydajne. Ale kiedy uruchomię następujące:

time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).

Otrzymałem następujące wyniki, które są stosunkowo spójne w kilku seriach:

Metoda 1:

% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)

Metoda 2:

% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)

Metoda 3:

% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)

Tak więc metoda rekurencyjna nie-ogonowa jest znacznie bardziej wydajna w czasie rzeczywistym.

Czy dany typ rekurencji jest generalnie bardziej efektywny w czasie rzeczywistym, a wszystkie inne rzeczy są równe (wiem, że nie zawsze jest to proste założenie)? Eksperyment ten mówi mi, że mogę nie chcieć zawsze dążyć do rekursji ogonowej, ale być może muszę najpierw wykonać analizę wydajności, a następnie zważyć wydajność w porównaniu z innymi korzyściami, jakie ma rekursja ogonowa.