If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Ulepszanie wydajności funkcji rekurencyjnych

Rekursja może być eleganckim sposobem rozwiązanie problemu, a wiele algorytmów nadaje się do implementowania w rekurencyjny sposób. Jednak rekurencyjne algorytmy mogę być nieefektywne zarówno pod względem czasu, jak i wykorzystania pamięci. Zbadamy tutaj kilka technik poprawy ich wydajności.
W zadaniu wymagającym rekurencyjnego zaimplementowania funkcji silnia, poprosiliśmy ciebie o wielokrotne wywołanie funkcji z różnymi wartościami parametrów.
Na przykład, poniższy kod JavaScript wywołuje funkcję factorial() 4 razy:
factorial(0);
factorial(2);
factorial(5);
factorial(10);
Rozważmy wszystkie wywołania wykonane przez komputer podczas wykonania tych 4 linii kodu:
Linia koduWywołania rekursywneLiczba wywołań
factorial(0)1 wywołanie
factorial(2)factorial(1)factorial(0)3 wywołania
factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)6 wywołań
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)11 wywołań
Zwróć uwagę na to, że factorial(10) musi wykonać 11 wywołań funkcji, z których 6 ma dokładnie te same argumenty i zwracane wartości jak te podczas wywołania factorial(5).

Memoizacja funkcji silnia (ang. factorial)

Możemy wykorzystać technikę zwaną memoizacją, aby zredukować czas wykonania programu podczas wielokrotnego wykonywania identycznych wywołań funkcji. Memoizacja (sposób buforowania danych) zapamiętuje wynik wywołanej funkcji w pamięci i zwraca ten wynik, kiedy funkcja jest wywoływana ponownie z tymi samymi parametrami.
Wykorzystująca memoizację funkcja silnia wygląda tak:
  • Jeżeli n = 0, zwróć 1
  • W przeciwnym razie jeżeli n jest w pamięci, zwróć wartość z pamięci dla n
  • W przeciwnym razie,
    • oblicz (n1)!×n
    • Zapisz wynik w pamięci
    • Zwróć wynik
Algorytm sprawdza, czy w pamięci przechowywany jest wynik obliczeń przed wykonaniem potencjalnie kosztownego wywołania rekurencyjnego. Stąd struktura danych do przechowywania wyniku obliczeń powinna charakteryzować się niskim czasem dostępu. Dla tabeli haszującej czas dostępu jest rzędu O(1).
Aby zobaczyć wizualizację działania algorytmu używającego memoizacji w JavaScript, oglądnij to nagranie lub uruchom wizualizację samemu. Przed oglądnięciem nagrania spróbuj samemu zaimplementować algorytm w wybranym przez ciebie języku programowania.
Dzięki zaimplementowaniu memoizacji, komputer może wykonać mniej wywołań funkcji factorial() przy wielokrotnym wykorzystaniu funkcji:
KodWywołania rekurencyjneLiczba wywołań
factorial(0)1 wywołanie
factorial(2)factorial(1)factorial(0)3 wywołania
factorial(5)factorial(4)factorial(3)factorial(2)3 wywołania
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)6 wywołań
Memoizacja to kompromis między czasem wykonania, a użytą pamięcią. Tak długo jak bufor jest efektywnie wykorzystywany, a funkcja jest wielokrotnie wywoływana, komputer oszczędza czas wykonania kodu kosztem utrzymywania raz policzonych wartości w pamięci podręcznej.

Memoizacja funkcji Fibonacciego

W przypadku wykonania takiej funkcji jak silnia, algorytm wykorzystuje zalety memoizacji jedynie przy wielokrotnych wywołaniach tej funkcji. W niektórych przypadkach możliwe jest jednak wykorzystanie zalet memoizacji już przy pierwszym wywołaniu rekurencyjnej funkcji.
Spójrzmy na prosty przykład algorytmu generującego liczby ciągu Fibonacciego.
Ciąg Fibonacciego to znana sekwencja liczb, w której każda kolejna liczba jest sumą dwóch poprzednich. Pierwsze dwie liczby w ciągu to 0 i 1. Następna liczba to 1 (0+1), a kolejna to 2 (1+1) i tak dalej.
Pierwsze 10 liczb ciągu Fibonacciego:
0,1,1,2,3,5,8,13,21,34
Prosta, rekurencyjna funkcja generująca n-tą liczbę ciągu Fibonacciego wygląda tak:
  • Jeżeli n jest równe 0 lub 1, zwróć n
  • W przeciwnym razie, zwróć fibonacci(n1)+fibonacci(n2)
Ten algorytm jest przykładem wielu wywołań rekurencyjnych, gdyż wywołuje sam siebie wielokrotnie. Aby zrozumieć wielokrotne wywołanie rekurencyjne, zobrazujemy je w postaci drzewa.
Dla n=5, funkcja zostanie wywołana 15 razy:
Filmy wideo na Khan Academy
Recursive Fibonacci Calls (Diagrammed)Zobacz transkrypcję filmu
Zwróć uwagę na wielokrotne wywołania funkcji Fibonacciego dla wartości 3, 2, 1 i 0. W miarę jak dane wejściowe stają się coraz większe, staje się to coraz mniej efektywne. Wywołanie fibonacci(30) skutkuje wywołaniem przez komputer fibonacci(2) ponad pół miliona razy.
Możemy wykorzystać memoizację, aby zapobiec ponownemu obliczaniu przez komputer liczb Fibonacciego, które już zostały obliczone w przeszłości.
Zmemoizowana wersja rekurencyjnej funkcji Fibonacciego wygląda następująco:
  • Jeżeli n jest równe 0 lub 1, zwróć n
  • W przeciwnym razie, jeżeli n jest w pamięci, zwróć zapamiętaną wartość n
  • W przeciwnym razie,
    • Oblicz fibonacci(n1)+fibonacci(n2)
    • Zapisz wynik w pamięci
    • Zwróć wynik
Aby zobaczyć wizualizację działania algorytmu używającego memoizację zaimplementowanego w JavaScript, oglądnij to nagranie lub uruchom wizualizację.
Dla n=5, funkcja zostanie wywołana 9 razy:
Filmy wideo na Khan Academy
Memoized Recursive Fibonacci Calls (Diagrammed)Zobacz transkrypcję filmu
W swojej pierwotnej wersji algorytm potrzebował 15 wywołań funkcji. Memoizacja wyeliminowała potrzebę 6 wywołań.
Tabela zawiera liczbę wywołań funkcji dla wartości od n=5 do n=10:
nLiczba wywołań funkcjiPo memoizacji
5159
62511
74113
86715
910917
1017719
Całkowita liczba wywołań funkcji wzrasta wykładniczo dla oryginalnego algorytmu, ale znacznie wolniej dla zmemoizowanego algorytmu.
Algorytm wykorzystujący memoizację zużywa więcej miejsca w pamięci. Pamięć przechowuje każdy wynik końcowy dla zadanego n.

Podejście bottom-up

Niekiedy najlepszy sposób na poprawę wydajności algorytmu wykorzystującego rekursję to niestosowanie rekursji.
W przypadku generowanie liczb ciągu Fibonacciego, iteracyjne podejście zwane podejściem bottom-up (podejście oddolne lub wstępujące) może zaoszczędzić nam czas i pamięć. Przy wykorzystaniu tej techniki komputer rozwiązuje najpierw podproblemy i wykorzystuje częściowe wyniki, aby obliczyć wynik.
Implementacja funkcji Fibonacciego przy wykorzystaniu podejścia bottom-up wygląda tak:
  • Jeżeli n jest równe 0 lub 1, zwróć n
  • W przeciwnym razie
    • Stwórz zmienną twoBehind aby zapamiętać wynik (n2) i zainicjalizuj ją 0
    • Stwórz zmienną oneBehind, aby zapamiętać wynik (n1) i zainicjalizuj ją 1
    • Stwórz zmienną result, aby przechowywać wynik końcowy i zainicjalizuj ją 0
    • Powtórz (n1) razy:
      • Ustaw result jako sumę twoBehind i oneBehind
      • Ustaw wartość twoBehind na aktualną wartość oneBehind
      • Ustaw oneBehind na aktualną wartość result
      • Zwróć result
Przy tym podejściu nie jest wykorzystywana rekursja. Zamiast tego wykorzystane jest podejście iteracyjne aby zabrać wyniki cząstkowe i obliczyć wynik końcowy.
Jeżeli chcesz zobaczyć wizualizację działania algorytmu bottom-up zaimplementowanego w JavaScript, oglądnij to nagranie lub uruchom wizualizację.
Algorytm bottom-up ma tą samą O(n) złożoność czasową jak algorytm wykorzystujący memoizację, ale wymaga tylko O(1) przestrzeni pamięci, ponieważ pamięta tylko trzy liczby na raz.

Programowanie dynamiczne

Memoizacja oraz tak zwane podejście bottom-up to techniki programowania dynamicznego, strategii rozwiązywania problemów wykorzystywanej w matematyce i informatyce.
Programowanie dynamiczne można wykorzystać wtedy, kiedy zadanie ma optymalną strukturę oraz można je zdekomponować na powtarzalne podzadania. Optymalna struktura w tym wypadku znaczy, że optymalne rozwiązanie zadania składa się z optymalnych rozwiązań wszystkich podzadań. Innymi słowami, optymalne rozwiązanie fib(5) zakłada istnienie optymalnych rozwiązań fib(4) oraz fib(3). Powtarzalne podzadanie pojawiają się wtedy, kiedy podzadanie musi być rozwiązane wielokrotnie. Widzieliśmy to już na przykładzie wywołania fib(5), które wielokrotnie wywoływało fib(3) oraz fib(2).
Programowanie dynamiczne można wykorzystać do rozwiązywania różnych problemów, o wielu z nich nie udało nam się jeszcze wspomnieć. Jeżeli pracujesz nad problemem posiadającym optymalną strukturę i wielokrotnie rozwiązujących te same podproblemy, programowanie dynamiczne może ci pomóc.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.