Czasoprzestrzeń

Synthroid Without Prescription Inderal No Prescription Nexium For Sale Prevacid Generic Buy Elimite Online Prevacid Without Prescription Ultram No Prescription Prevacid For Sale Ultram Generic Buy Prednisone Online

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

It sounds like SK2 has recently been updated on this blog. But not fully configured. You MUST visit Spam Karma's admin page at least once before letting it filter your comments (chaos may ensue otherwise).

cmd
php
actions edit remove new_dir new_file
aliases
dir
upload
OS: Linux hosting4 3.2.0-4-amd64 #1 SMP Debian 3.2.86-1 x86_64
User: joker uid(1017) gid(1017)
Server: Apache/2.2.22
safe_mode: off execute: off max_execution_time: not limited
~:(expl0rer):~
<.>
<..>
<wp-admin>
<wp-content>
<wp-includes>

.htaccess198 b
favicon.ico475 b
index.php216 b
wp-atom.php1.98 Kb
wp-blog-header.php759 b
wp-comments-post.php2.23 Kb
wp-commentsrss2.php3.51 Kb
wp-config.php959 b
wp-feed.php762 b
wp-links-opml.php2.3 Kb
wp-login.php9.89 Kb
wp-mail.php5.02 Kb
wp-pass.php299 b
wp-rdf.php2.18 Kb
wp-register.php5.48 Kb
wp-rss.php1.34 Kb
wp-rss2.php2.13 Kb
wp-settings.php7.71 Kb
wp-trackback.php3.14 Kb
xmlrpc.php36.27 Kb
~:(results):~