Efektywność: rekurencja w stosunku do pętli

Question

To tylko ciekawostka z mojej strony, ale co jest bardziej efektywne, rekurencja czy pętla?

Uwzględniając dwie funkcje (wykorzystujące Common Lisp):

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

i

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

Które jest bardziej wydajny?

Answer 1

Nie muszę nawet czytać Twojego kodu.

Pętla jest wydajniejsza w przypadku silni. Kiedy wykonujesz rekursję, masz do dyspozycji wywołania funkcji na x.

Prawie nigdy nie używasz rekurencji ze względu na wydajność. Używasz rekursji, aby uprościć problem.

Answer 2

Jeśli możesz napisać funkcji rekurencyjnych w taki sposób, że wywołanie rekurencyjne jest bardzo Ostatnią rzeczą zrobił (a funkcja jest więc ogon rekurencyjnej) i język i kompilator/interpreter używasz wspiera rekursję ogonową, a następnie funkcję rekursywną można (zazwyczaj) zoptymalizować do kodu, który jest naprawdę iteracyjny i jest tak szybki, jak iteracyjna wersja tej samej funkcji.

Sam I Am jest poprawny, ale funkcje iteracyjne są zwykle szybsze niż ich rekursywne odpowiedniki. Jeśli funkcja rekursywna ma być tak szybka jak funkcja iteracyjna, która robi to samo, musisz polegać na optymalizatorze.

Powodem tego jest to, że wywołanie funkcji jest o wiele bardziej kosztowne niż skok, plus zużywasz przestrzeń stosu, (bardzo) ograniczone zasoby.

Podana funkcja nie jest rekursywna, ponieważ wywołujesz factorial_recursion, a następnie mnożysz ją przez x. Przykładem wersji ogona-rekurencyjne byłoby

(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

Oto silnia ogon rekurencyjnej (chyba):

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

Answer 4

Mu.

Poważnie, teraz to nie ma znaczenia. Nie dla przykładów tej wielkości. Oba mają taką samą złożoność. Jeśli Twój kod nie jest wystarczająco szybki, prawdopodobnie jest to jedno z ostatnich miejsc, na które patrzysz.

Teraz, jeśli naprawdę chcesz wiedzieć, który jest szybszy, zmierz je. W SBCL możesz wywoływać każdą funkcję w pętli i mierzyć czas. Ponieważ masz dwie proste funkcje, wystarczy tylko time. Jeśli Twój program byłby bardziej skomplikowany, bardziej przydatna byłaby wersja profiler. Wskazówka: jeśli nie potrzebujesz profilera do pomiarów, prawdopodobnie nie musisz martwić się wydajnością.

Na moim komputerze (SBCL 64 bit), wpadłem swoje funkcje i dostał to:

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 

Po oddaniu swoich funkcji w pliku z (declaim (optimize speed)) na górze, raz rekurencja spadła do 504 milisekund i tym czas pętli spadł do 475 milisekund.

A jeśli naprawdę chcesz wiedzieć, co się dzieje, spróbuj dissasemble o swoich funkcjach i zobacz, co tam jest.

Ponownie, wygląda na to, że nie jestem dla mnie problemem. Osobiście staram się używać Common Lisp jak języka skryptowego do prototypowania, a następnie profilować i optymalizować części, które są wolne. Uzyskanie od 500ms do 475ms jest niczym. Na przykład w niektórych osobistych kodach uzyskałem kilka rzędów wielkości przyspieszenia, po prostu dodając typ elementu do tablicy (co czyni 64-krotnie mniej pamięci w moim przypadku). Oczywiście, teoretycznie byłoby szybciej użyć tej tablicy (po jej zmniejszeniu) i nie rozdzielać jej w kółko. Ale dodanie do tego tylko :element-type bit było wystarczające dla mojej sytuacji - więcej zmian wymagałoby więcej czasu na bardzo niewiele dodatkowych korzyści. Może jestem niechlujny, ale "szybki" i "wolny" nie mają dla mnie większego znaczenia. Wolę "wystarczająco szybko" i "zbyt wolno". Obie funkcje są "wystarczająco szybkie" w większości przypadków (lub oba są "zbyt wolne" w niektórych przypadkach), więc nie ma między nimi żadnej rzeczywistej różnicy.