Производительность пролога и тип рекурсии
Я играл сpermutation
в паре программ и наткнулся на этот маленький эксперимент:
Метод перестановки 1:
permute([], []).
permute([X|Rest], L) :-
permute(Rest, L1),
select(X, L, L1).
Метод перестановки 2:
permute([], []).
permute(L, [P | P1]) :-
select(P, L, L1),
permute(L1, P1).
Метод перестановки 3 (используйте встроенный):
permute(L, P) :- permutation(L, P).
Я понимаю, что этоХорошей практикой является использование хвостовой рекурсии, и в целом использование встроенных модулей должно быть эффективным. Но когда я запускаю следующее:
time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).
Я получил следующие результаты, которые относительно последовательны в нескольких прогонах:
Способ 1:
% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)
Способ 2:
% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)
Способ 3:
% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)
Таким образом, нехвостовой рекурсивный метод значительно эффективнее в реальном времени.
Является ли конкретный тип рекурсии более эффективным в реальном времени, при прочих равных условиях (я знаю, что 'не всегда простая предпосылка)? Этот эксперимент говорит мне о том, что я, возможно, не хочу всегда стремиться к хвостовой рекурсии, но мне может понадобиться сначала выполнить анализ производительности, а затем сравнить производительность с другими преимуществами, которые имеет хвостовая рекурсия.