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 kodu	Wywołania rekursywne	Liczba 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 left parenthesis, n, minus, 1, right parenthesis, !, times, 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, left parenthesis, 1, right parenthesis.

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:

Kod	Wywołania rekurencyjne	Liczba 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, plus, 1), a kolejna to 2 (1, plus, 1) i tak dalej.

Pierwsze 10 liczb ciągu Fibonacciego:

0, comma, 1, comma, 1, comma, 2, comma, 3, comma, 5, comma, 8, comma, 13, comma, 21, comma, 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óć start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis

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, equals, 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 start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis
- 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, equals, 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, equals, 5 do n, equals, 10:

n	Liczba wywołań funkcji	Po memoizacji
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

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ą start text, t, w, o, B, e, h, i, n, d, end text aby zapamiętać wynik left parenthesis, n, minus, 2, right parenthesis i zainicjalizuj ją 0
- Stwórz zmienną start text, o, n, e, B, e, h, i, n, d, end text, aby zapamiętać wynik left parenthesis, n, minus, 1, right parenthesis i zainicjalizuj ją 1
- Stwórz zmienną start text, r, e, s, u, l, t, end text, aby przechowywać wynik końcowy i zainicjalizuj ją 0
- Powtórz left parenthesis, n, minus, 1, right parenthesis razy:
  - Ustaw start text, r, e, s, u, l, t, end text jako sumę start text, t, w, o, B, e, h, i, n, d, end text i start text, o, n, e, B, e, h, i, n, d, end text
  - Ustaw wartość start text, t, w, o, B, e, h, i, n, d, end text na aktualną wartość start text, o, n, e, B, e, h, i, n, d, end text
  - Ustaw start text, o, n, e, B, e, h, i, n, d, end text na aktualną wartość start text, r, e, s, u, l, t, end text
  - Zwróć start text, r, e, s, u, l, t, end text

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, left parenthesis, n, right parenthesis złożoność czasową jak algorytm wykorzystujący memoizację, ale wymaga tylko O, left parenthesis, 1, right parenthesis 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.

[Źródło]

Chcesz dołączyć do dyskusji?

Zaloguj się

Sortuj według

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.