Prolog prestazioni e la ricorsione di tipo

Question

stavo giocando con permutation in un paio di programmi e d'imbatterci in questo piccolo esperimento:

metodo Permutazione 1:

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

metodo Permutazione 2:

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

Metodo di permutazione 3 (utilizzare il built-in):

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

Capisco che sia una buona pratica ricorrere alla ricorsione in coda, e generalmente l'uso di built-in dovrebbe essere efficiente. Ma quando ho eseguito il seguente:

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

ho ottenuto i seguenti risultati, che sono relativamente coerenti tra diverse piste:

Metodo 1:

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

Metodo 2:

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

Metodo 3:

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

Quindi il metodo ricorsivo non-tail è significativamente più efficiente in tempo reale.

È un tipo di ricorrenza particolare generalmente più efficiente in tempo reale, a parità di altre condizioni (so che non è sempre una premessa semplice)? Ciò che questo esperimento mi dice è che forse non voglio essere sempre alla ricerca di una ricorsione in coda, ma potrei aver bisogno di fare prima un'analisi delle prestazioni, quindi valutare il beneficio delle prestazioni rispetto ad altri benefici che la ricorsione in coda ha.

Answer 1

Davvero una bella domanda.

In attesa che qualcuno pubblichi un'analisi tempo/spazio, l'unica avvertenza che posso offrire è che il metodo 1 & 2 non termina quando il primo argomento è libero, mentre il metodo 3 lo fa.

Ad ogni modo, il metodo 1 sembra davvero molto più efficiente di quello integrato. Buono a sapersi.

modificare: e dato che l'attuazione biblioteca semplicemente regolare istanza di argomenti e chiama il metodo 1, ho intenzione di discutere su SWI-Prolog mailing list il metodo 2 in alternativa (o, si preferisce farlo da soli , fammi sapere).

altri Cambia: Ho dimenticato in precedenza sottolineare che permutazione/3 (diciamo, metodo 2), dà lessicografico ordinate soluzioni, mentre il metodo 1 non è così. Penso che potrebbe essere un forte requisito preferenziale, ma dovrebbe essere espresso come un'opzione, dato il guadagno di prestazioni che il metodo 1 consente.

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)). 
% 3,112,758 inferences, 3,160 CPU in 3,162 seconds (100% CPU, 984974 Lips) 
P = [1, 4, 8, 3, 7, 6, 5, 9, 2|...] . 

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)). 
% 10,154,843 inferences, 9,779 CPU in 9,806 seconds (100% CPU, 1038398 Lips) 
P = [2, 7, 8, 3, 9, 1, 5, 4, 6|...] . 

YAP dà ancora più guadagno!

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)). 
% 0.716 CPU in 0.719 seconds (99% CPU) 
P = [1,4,8,3,7,6,5,9,2,0] 

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)). 
% 8.357 CPU in 8.368 seconds (99% CPU) 
P = [2,7,8,3,9,1,5,4,6,0] 

Edit: Ho postato un commento su SWI-Prolog doc page su questo tema.

Answer 2

Sospetto che ciò che ha dato il via a questa indagine sia stato the discussion about tail-recursive sum/2 using an accumulator rispetto a no. L'esempio sum/2 è molto semplice e asciutto; una versione sta facendo l'aritmetica in pila, l'altra sta usando un accumulatore. Tuttavia, come la maggior parte delle cose nel mondo reale, la verità generale è "dipende". Per esempio, confrontare l'efficienza dei metodi 1 e 2 utilizzando piena esemplificazione:

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])). 
% 18 inferences, 0.000 CPU in 0.000 seconds (66% CPU, 857143 Lips) 
true ; 
% 86,546 inferences, 0.022 CPU in 0.022 seconds (100% CPU, 3974193 Lips) 
false. 

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])). 
% 18 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 857143 Lips) 
true ; 
% 47 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 940000 Lips) 
false. 

Metodo 1 battiti metodo 2 quando si sta generando soluzioni (come nel tuo test), ma il metodo 2 battiti Metodo 1 quando sei semplicemente controllando Guardando il codice è facile capire perché: il primo deve ri-permutare l'intera coda della lista, mentre il secondo deve solo provare a selezionare un elemento. In questo caso potrebbe essere facile puntare al caso generatore e dire che è più desiderato. Quella determinazione è semplicemente uno dei compromessi di cui bisogna tenere conto quando si ha a che fare con Prolog. È molto difficile fare predicati che sono tutte cose per tutte le persone e comportarsi sempre alla grande; devi decidere quali sono i "percorsi privilegiati" e quali no.

Mi ricordo vagamente che qualcuno ha recentemente mostrato un esempio di liste aggiunte "durante il ritorno" e come si può prendere qualcosa che non è o non dovrebbe essere ricorsivo e farlo funzionare grazie all'unificazione, ma non lo faccio t avere il collegamento a portata di mano. Speriamo che chiunque l'abbia presentato l'ultima volta (Will?) Si presenterà e lo condividerà.

Ottima domanda, a proposito. Il tuo metodo di indagine è valido, dovrai solo prendere in considerazione anche altri modelli di istanziazione. Parlando personalmente, di solito cerco di preoccuparmi più di correttezza e generalità che di prestazioni in anticipo. Se vedo immediatamente come usare un accumulatore, lo farò, ma altrimenti non lo farò fino a quando non mi imbatterò in un'esigenza reale di prestazioni migliori. La ricorsione della coda è solo un metodo per migliorare le prestazioni; spesso ci sono altre cose che devono essere affrontate come male o peggio.

Answer 3

Davvero una bella domanda, +1!

coda di chiamata (e, come un caso speciale, la coda ricorsione) l'ottimizzazione si applica solo se il predicato è deterministico! Questo non è il caso, quindi il tuo predicato richiederà sempre lo spazio locale dello stack, indipendentemente dall'ordine in cui punti gli obiettivi. La versione ricorsiva non-tail è più efficiente in termini di tempo quando si generano tutte le soluzioni perché è necessario eseguire un numero inferiore di unioni durante il backtracking.

EDIT: Mi sto espandendo su questo punto poiché vale la pena studiare la differenza di prestazioni in modo più dettagliato.

In primo luogo, per chiarezza, a rinominare le due versioni differenti per chiarire quale versione di cui sto parlando:

Variante 1: Non-coda ricorsiva:

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

Variante 2 : Ricorsivo di coda:

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

Notare che, sebbene la seconda versione n è chiaramente coda ricorsiva, coda chiamata (e quindi anche ricorsione della coda) ottimizzazione aiuta solo se il predicato è deterministico, e quindi non può aiutare quando generiamo tutte le permutazioni, perché i punti di scelta sono ancora lasciati in quel caso.

Nota anche che sto deliberatamente mantenendo il nome della variabile originale e il nome del predicato principale per evitare di introdurre più varianti. Personalmente, preferisco una convenzione di denominazione che chiarisca quali variabili denotano gli elenchi aggiungendo uno s ai loro nomi, in analogia al normale plurale inglese. Inoltre, preferisco i nomi dei predicati che mostrano più chiaramente la natura dichiarativa e relazionale (almeno intenzionale e intenzionale) del codice e raccomandano di evitare nomi imperativi per questo motivo.

---

consideri ora dispiegarsi la prima variante e parzialmente valutazione per un elenco di 3 elementi. Si comincia con un obiettivo semplice:

?- Xs = [A,B,C], permute1(Xs, L). 

e poi gradualmente aprirlo inserendo nella definizione di permute1/2, rendendo tutte le unificazioni testa esplicito. Nella prima iterazione, otteniamo:

 
?- Xs = [A,B,C], Xs1 = [B,C], permute1(Xs1, L1), select(A, L, L1). 

sto segnando l'unificazione testa in grassetto.

Ora, rimane ancora un obiettivo di permute1/2. Quindi ripetiamo il processo, ancora una volta di collegare unico organo norma applicabile del predicato nel luogo della sua testa:

 
?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], permute1(Xs2, L2), select(B, L1, L2), select(A, L, L1). 

Un altro passo di questo, e otteniamo:

 
?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], select(C, L2, []), select(B, L1, L2), select(A, L, L1). 

Questo è ciò che l'originale l'obiettivo sembra se abbiamo appena spiegato la definizione di permute1/2 ripetutamente.

---

Ora, che dire della seconda variante?Anche in questo caso, si parte con un obiettivo semplice:

?- Xs = [A,B,C], permute2(Xs, Ys). 

Un'iterazione del dispiegarsi permute2/2 cede la versione equivalente:

 
?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), permute2(L1, P1). 

e una seconda rendimenti di iterazione:

 
?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), Ys1 = [P1|P2], select(P1, L1, L2), permute2(L2, P2). 

lascio la terza e ultima iterazione come semplice esercizio che ti consiglio vivamente di fare.

---

E da questo è chiaro quello che inizialmente probabilmente non avevamo previsto: Una grande differenza sta nelle unificazioni testa, che la prima versione esegue in modo deterministico proprio all'inizio, e la seconda versione esegue più e più volte su backtracking.

Questo famoso esempio mostra che, contrariamente alle aspettative comuni, la ricorsione della coda può essere piuttosto lenta se il codice non è deterministico.