Efficienza: ricorsione vs ciclo

Question

Questa è solo la mia curiosità, ma cosa è più efficiente, ricorsione o ciclo?

Date due funzioni (utilizzando Common Lisp):

(defun factorial_recursion (x) 
    (if (> x 0) 
     (* x (factorial_recursion (decf x))) 
     1)) 

e

(defun factorial_loop (x) 
    (loop for i from 1 to x for result = 1 then 
     (* result i) finally 
     (return result))) 

che è più efficiente?

Answer 1

Non ho nemmeno bisogno di leggere il tuo codice.

Il ciclo è più efficiente per i fattoriali. Quando esegui la ricorsione, hai fino a x chiamate di funzione nello stack.

Quasi mai si utilizza la ricorsione per motivi di prestazioni. Usa la ricorsione per rendere il problema più semplice.

Answer 2

Se è possibile scrivere funzioni ricorsive in modo tale che la chiamata ricorsiva è l'ultima cosa fatto (e la funzione è quindi tail-ricorsiva) e la lingua e compilatore/interprete si utilizza supporta la ricorsione di coda, quindi la funzione ricorsiva può (di solito) essere ottimizzata in codice che è realmente iterativo ed è veloce come una versione iterativa della stessa funzione.

Sam I Am è corretto, tuttavia, le funzioni iterative sono in genere più veloci delle controparti ricorsive. Se una funzione ricorsiva deve essere veloce come una funzione iterativa che fa la stessa cosa, devi fare affidamento sull'ottimizzatore.

La ragione di questo è che una chiamata di funzione è molto più costoso di un salto, più si consumano spazio di stack, un (molto) risorsa finita.

La funzione fornita non è ricorsiva della coda perché si chiama factorial_recursion e quindi si moltiplica per x. Un esempio di una versione ricorsiva in coda sarebbe

(defun factorial-recursion-assist (x cur) 
    (if (> x 1) 
     (factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x))) 
     cur)) 

(defun factorial-recursion (x) 
    (factorial-recursion-assist x 1)) 

(print (factorial-recursion 4)) 

Answer 3

Ecco un fattoriale ricorsiva in coda (credo):

(defun fact (x) 
    (funcall (alambda (i ret) 
      (cond ((> i 1) 
        (self (1- i) (* ret i))) 
        (t 
        ret))) 
      x 1)) 

Answer 4

Mu.

Seriamente ora, non importa. Non per esempi di queste dimensioni. Entrambi hanno la stessa complessità. Se il tuo codice non è abbastanza veloce per te, questo è probabilmente uno degli ultimi posti che guardi.

Ora, se vuoi davvero sapere quale è più veloce, misurali. Su SBCL, è possibile chiamare ciascuna funzione in un ciclo e misurare il tempo. Dato che hai due semplici funzioni, è sufficiente time. Se il tuo programma fosse più complicato, un profiler sarebbe più utile. Suggerimento: se non hai bisogno di un profiler per le tue misure, probabilmente non devi preoccuparti delle prestazioni.

Sulla mia macchina (SBCL 64 bit), ho eseguito le funzioni e ha ottenuto questo:

CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000))) 
Evaluation took: 
    0.540 seconds of real time 
    0.536034 seconds of total run time (0.496031 user, 0.040003 system) 
    [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ] 
    99.26% CPU 
    1,006,632,438 processor cycles 
    511,315,904 bytes consed 

NIL 
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000))) 
Evaluation took: 
    0.485 seconds of real time 
    0.488030 seconds of total run time (0.488030 user, 0.000000 system) 
    [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ] 
    100.62% CPU 
    902,043,247 processor cycles 
    511,322,400 bytes consed 

NIL 

Dopo aver messo le funzioni in un file con (declaim (optimize speed)) in alto, il tempo di ricorsione è sceso a 504 millisecondi e il il tempo di ciclo è sceso a 475 millisecondi.

E se vuoi davvero sapere cosa sta succedendo, prova dissasemble sulle tue funzioni e guarda cosa c'è dentro.

Ancora una volta, questo mi sembra un non-problema. Personalmente, cerco di usare Common Lisp come un linguaggio di scripting per la prototipazione, quindi di profilare e ottimizzare le parti che sono lente. Passare da 500 a 475 ms non è niente. Ad esempio, in alcuni codici personali, ho ottenuto un paio di ordini di grandezza accelerando semplicemente l'aggiunta di un tipo di elemento a un array (rendendo così la memoria dell'array 64 volte più piccola nel mio caso). Certo, in teoria sarebbe stato più veloce riutilizzare quella matrice (dopo averla resa più piccola) e non allocarla più e più volte. Ma semplicemente aggiungere :element-type bit è stato sufficiente per la mia situazione: più modifiche avrebbero richiesto più tempo per un piccolo vantaggio extra. Forse sono sciatto, ma "veloce" e "lento" non significano molto per me. Preferisco "abbastanza veloce" e "troppo lento". Entrambe le funzioni sono 'abbastanza veloci' nella maggior parte dei casi (o entrambe sono 'troppo lente' in alcuni casi) quindi non c'è una vera differenza tra loro.