Naprawdę miłe pytanie, +1!
wezwanie Tail (i, jako szczególny przypadek, ogon rekurencji) optymalizacja odnosi się tylko wtedy, gdy orzeczenie jest deterministyczny! Tak nie jest w tym przypadku, więc twój predykat zawsze będzie wymagał miejsca na stosie lokalnym, bez względu na to, w jakiej kolejności postawisz cele. Wersja rekurencyjna nienastawiona na ogon jest bardziej efektywna (czasowo) przy generowaniu wszystkich rozwiązań, ponieważ musi wykonać mniej unifikacji podczas cofania.
EDIT: Rozwijam się w tej kwestii, ponieważ warto bardziej szczegółowo przyjrzeć się różnicy w wydajności.
Po pierwsze, dla jasności, zmienić nazwę dwie różne wersje, aby wyjaśnić, która wersja mówię:
Wariant 1: Non-tail rekurencyjne:
permute1([], []).
permute1([X|Rest], L) :-
permute1(Rest, L1),
select(X, L, L1).
Wariant 2 : Rekurencyjny tył:
permute2([], []).
permute2(L, [P|P1]) :-
select(P, L, L1),
permute2(L1, P1).
Należy ponownie zauważyć, że chociaż drugi wariant n jest wyraźnie rekursywny, wywołanie ogona (a więc i rekurencja ogona) optymalizacja pomaga tylko wtedy, gdy predykat jest deterministyczny, a zatem nie może pomóc, gdy generujemy wszystkie permutacje, ponieważ punkty wyboru pozostają w tym przypadku.
Należy również pamiętać, że świadomie zachowuję oryginalne nazwy zmiennych i główną nazwę orzecznika, aby uniknąć wprowadzania kolejnych wariantów. Osobiście wolę konwencję nazewnictwa, która wyjaśnia, które zmienne oznaczają , wyliczając, dołączając do ich nazw s, analogicznie do zwykłej angielskiej liczby mnogiej. Ponadto wolę nazwy predykatów, które wyraźniej wykazują (przynajmniej zamierzony i pożądany) deklaratywny, relacyjny charakter kodu i zalecają unikanie imperatywnych nazw z tego powodu.
Rozważmy teraz rozkładanie pierwszym wariancie i częściowo oceniając go na liście 3 elementów. Zaczynamy prosty cel:
?- Xs = [A,B,C], permute1(Xs, L).
a następnie stopniowo rozwijać go podłączając definicji permute1/2, robiąc wszystkie unifikacje głowy wyraźne. W pierwszej iteracji otrzymujemy:
?- Xs = [A,B,C], Xs1 = [B,C], permute1(Xs1, L1), select(A, L, L1).
Oznaczam wyróżnienia czołowe pogrubieniem.
Pozostaje jeszcze jeden cel: permute1/2. Więc powtórzyć proces, ponownie podłączając zastosowanie tylko ciałem reguły orzecznika w miejscu jego głowie:
?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], permute1(Xs2, L2), select(B, L1, L2), select(A, L, L1).
jeszcze jeden przejściu tego, a my otrzymujemy:
?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], select(C, L2, []), select(B, L1, L2), select(A, L, L1).
To co oryginał cel wygląda tak, jakbyśmy tylko kilkakrotnie rozkładali definicję permute1/2.
A co z drugim wariantem?Znowu zaczynamy prosty cel:
?- Xs = [A,B,C], permute2(Xs, Ys).
Jedna iteracja rozkładanie permute2/2 daje równoważną wersję:
?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), permute2(L1, P1).
a drugi plony iteracji:
?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), Ys1 = [P1|P2], select(P1, L1, L2), permute2(L2, P2).
Zostawiam trzecią i ostatnia iteracja jako proste ćwiczenie, które zalecam, aby zrobić.
A z tym jest oczywiste, co początkowo zapewne nie spodziewał: Duża różnica leży w głowy unifikacji, którego pierwsza wersja wykonuje deterministycznie na samym początku, a druga wersja wykonuje w kółko w trakcie cofania.
Ten słynny przykład ładnie pokazuje, że wbrew powszechnym oczekiwaniom rekurencja ogona może być dość powolna, jeśli kod nie jest deterministyczny.
Nie pamiętam, żebym kiedykolwiek użył (wszystkich) permutacji bez potrzeby i polegając na kolejności leksykograficznej. Permutacje są tradycyjnie wymieniane w porządku leksykograficznym, a wszystkie biblioteki zapewniające permutacje tworzą je w tej kolejności. W tym sensie byłoby trochę dziwnie i bardzo mylnie zmienić kolejność. –
@Boris: Masz rację, [C++] (http://en.cppreference.com/w/cpp/algorithm/next_permutation) na przykład wywołaj funkcję next_permutation i po prostu radzisz o kolejności leksykograficznej w dokumentacji. Ale współczynnik 3 (lub więcej) przyspieszenia może być znaczący. – CapelliC
Patrząc na podany link, wygląda na to, że nie jest to "po prostu rada", ale w specyfikacji. W każdym razie, zakładam, że kolejność jest ważna tylko dlatego, że wszystkie biblioteki, które sprawdziłem, trzymają się jej (podobnie jak podręczniki matematyczne). Czy istnieje zapotrzebowanie na zamawianie lub czy jest to po prostu konwencja? –