Czasoprzestrzeń

Na wykładzie 1b pan Sussman wprowadza nas w tematykę złożoności obliczeniowej. Mimo tego, że jest to domena informatyki teoretycznej, robi to na tyle przystępnie, że nawet najbardziej oporni są w stanie coś z tego wynieść. To, na co chciałbym zwrócić uwagę, to sposób w jaki język Scheme ułatwia dosłowne pokazanie rozwoju procesu podczas wykonania. Przykład użyty na wykładzie znaleźć można w książce jako ćwiczenie 1.9. Pełna jego treść podana jest na końcu części 1.2.1, ja przytoczę tylko odpowiednie kody źródłowe. Zadanie polega na opisaniu procesu generowanego przez każdą z procedur. Pierwszy kod źródłowy wygląda następująco:

(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))

Procedury inc i dec odpowiednio zwiększają i zmniejszają swój argument o jeden. Ta definicja dodawania mówi więc, że sumą a i b jest b jeżeli a jest równe zero, w przeciwnym razie jest to suma a-1 i b+1. Stary problem jest więc zastępowany przez nowy problem. Proces kolejnych redukcji problemu do problemów je zastępujących jest przedstawiony na obrazku poniżej. Wykonywana operacja to (+ 3 4).

Iteracja

Jak wyraźnie widać, ta technika upraszczania problemu, chociaż korzysta z definicji rekurenycjnej (funkcja + wywołuje samą siebie) generuje proces iteracyjny. Dzieje się tak dlatego, bo w momencie wywołania (+ (dec a) (inc b)) iterpreter wie, że może zastąpić, “nadpisać” oryginalne wywołanie tym nowym. A ma taką możliwość, bo wynik tego wywołania jest jednocześnie wynikiem oryginalnego wywołania. Dlatego (+ 3 4) znaczy to samo co (+ 2 5), co znaczy to samo co (+ 1 6), itd. aż do momentu, gdy problem uprości się do postaci, w której jesteśmy w stanie udzielić jednoznacznej odpowiedzi (w tym przypadku nastąpi to, gdy a dojdzie do zera). Inaczej jednak jest dla drugiego kodu.

(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))

Tutaj definiujemy sumę a i b jako zwiększoną o jeden sumę a-1 i b. Kształt procesu generowanego przez tę procedurę jest zupełnie inny.

Rekurencja

W tym przypadku nie zastępujemy starego problemu nowym problemem, ale definiujemy dla niego zupełnie nowy podproblem, którego rozwiązanie pomoże nam w rozwiązaniu. Musimy więc ze zwróceniem wyniku poczekać, aż interpreter obliczy (+ (dec a) b). Dopiero, gdy ten podproblem zostanie rozwiązany, będziemy mogli zwiększyć zwrócony przez wywołaną podprocedurę wynik o jeden i ogłosić nasze rozwiązanie. Fakt, że musimy pamiętać o wykonaniu dodatkowych operacji, powoduje, że interpreter nie może zastąpić starego problemu nowym, jak to uprzednio się odbywało. Co więcej, dla każdego wywołania naszej sumy musi pamiętać, w jakie miejsce wrócić. I to jest przyczyną liniowej pamięciowej złożoności tego procesu. Liniowy proces rekurencyjny nie tylko generuje liczbę kroków liniowo zależną od danych wejściowych (stąd liniowa złożoność czasowa), ale i potrzebuje dodatkowej pamięci dla każdego wywołania rekurencyjnego.

Jeżeli więc chcemy, by nasze programy były jak najszybsze i jak najmniejsze powinniśmy, gdzie to jest możliwe, zastępować procesy rekurencyjne iteracyjnymi. Uważni czytelnicy zapewne pamiętają, jak dla zabawy definiowałem funkcję sum-of-squares obliczającą sumę kwadratów wszystkich swoich elementów. Dla przypomnienia, kod wyglądał następująco:

(define (sum-of-squares L)
(if (null? L)
0
(+ (square (car L)) (sum-of-squares (cdr L)))))

Jako, że języki, na których uczyłem się programować wpoiły mi iterację jako najnaturalniejszy z modeli obliczeń, nie trudno mi było wyobrazić sobie iteracyjny sposób obliczania tej funkcji. Przykładowo w Pythonie zapisałbym to tak:

def sum_of_squares(L):
sum = 0
for el in L:
sum += el**2
return sum

Czyli, ogólnie rzecz biorąc, w każdym momencie iteracji przechowuję dotychczas obliczoną sumę elementów w specjalnej zmiennej sum. W Scheme do dyspozycji mamy tylko definicje rekurencyjne, więc rozwiązanie jest odrobinę dłuższe:

(define (sum-of-squares L)
(define (sos L sum)
(if (null? L)
sum
(sos (cdr L) (+ sum (square (car L))))))
(sos L 0))

Zdefiniowałem pomocniczą funkcję sos, która jako drugi argument przechowuje sumę, którą należy dodać do ostatecznego wyniku. Iterację zaczynamy od sumy równej zero, stąd wartością wywołania (sum-of-squares L) jest (sos L 0). Proces jest iteracyjny, bo za każdym razem stare wywołanie funkcji sos jest zastępowane przez nowe. Nie ma dodatkowych obliczeń do wykonania, ani miejsca powrotu do zapamiętania. Nowa definicja procedury sum-of-squares generuje więc proces iteracyjny.

Komentuj wpis