Walcząc z czasem

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

W ćwiczeniu 1.10 mamy okazję zapoznać się z funkcją Ackermanna, a raczej jej odmianą przygotowaną przez autorów Wizard Booka. Definicja prawdziwej funkcji Ackermanna jest trochę inna, obie wersje mają jednak tę właściwość, że rosną bardzo szybko.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

Pierwsze polecenie każe obliczyć wartość trzech wyrażeń: (A 1 10), (A 2 4) i (A 3 3). Rozwinięcia są proste, ale dość żmudne przy obliczeniach.

  • (A 1 10)
    (A 0 (A 1 9))
    (A 0 (A 0 (A 1 8)))
    (A 0 (A 0 (A 0 (A 1 7))))
    ; ...
    (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
    (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
    (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
    ; ...
    (A 0 512)
    1024
    
  • (A 2 4)
    (A 1 (A 2 3))
    (A 1 (A 1 (A 2 2)))
    (A 1 (A 1 (A 1 (A 2 1))))
    (A 1 (A 1 (A 1 2)))
    (A 1 (A 1 (A 0 (A 1 1))))
    (A 1 (A 1 (A 0 2)))
    (A 1 (A 1 4))
    (A 1 (A 0 (A 1 3)))
    (A 1 (A 0 (A 0 (A 1 2))))
    (A 1 (A 0 (A 0 (A 0 (A 1 1)))))
    (A 1 (A 0 (A 0 (A 0 2))))
    (A 1 (A 0 (A 0 4)))
    (A 1 (A 0 8))
    (A 1 16)
    (A 0 (A 1 15))
    (A 0 (A 0 (A 1 14)))
    ; ...
    (A 0 32768)
    65536
    
  • (A 3 3)
    (A 2 (A 3 2))
    (A 2 (A 2 (A 3 1)))
    (A 2 (A 2 2))
    (A 2 (A 1 (A 2 1)))
    (A 2 (A 1 2))
    (A 2 (A 0 (A 1 1)))
    (A 2 (A 0 2))
    (A 2 4)
    ; to juz obliczylismy w poprzednim przykladzie, wiec...
    65536
    

Druga część zadania polega na podaniu zwartej definicji matematycznej funkcji (A 0 n), (A 1 n) i (A 2 n). Definicja funkcji Ackermanna mówi o tym, że (A x y) to (A (- x 1) ... przyłożone y-razy do 2 (pomijając przypadek, gdy y jest równe 0). (A 0 n) jest równe 2n z definicji (drugi predykat wyrażenia cond). (A 1 n) to 2n przyłożone (n-1)-razy do 2 lub 0, gdy n jest zerem. Definicja (A 1 n) wygląda więc następująco:

A(1,n) = 2^n gdy n>0 lub 0 gdy n=0

W podobny sposób dochodzimy do definicji (A 2 n):

A(2,n) = 2^(A(2,n-1)) gdy n>1 lub 2 gdy n=1 lub 0 gdy n=0

Na tym kończy się zadanie, ja jednak zacząłem się zastanawiać nad możliwością przyspieszenia obliczeń. Obliczenie (A 2 5) zajmuje u mnie około 4.5 sekundy, co pomimo wielkości wyniku (19729 cyfr :-), jest wynikiem całkiem słabym. Pierwszą myślą było oczywiście przepisanie definicji rekurencyjnej na iteracyjną. Najpierw stworzyłem pomocniczą funkcję iter-fun, która symuluje rekurencyjne złożenie (f (f (f ... (f start)))))):

(define (iter-fun f num start)
  (if (= num 0)
      start
      (iter-fun f (- num 1) (f start))))

Wykorzystując ją przepisałem funkcję Ackermanna do następującej postaci:

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        (else (iter-fun (lambda (i) (A (- x 1) i))
                        (- y 1)
                        2))))

Z nową definicją na czasie obliczenia (A 2 5) zyskałem tylko około pół sekundy. To wciąż dawało jednak wynik w okolicach 3.9 sekundy. Dla porównania, ten sam algorytm zapisany w Pythonie wykonuje się u mnie przez 1.2 sekundy.

def iter_fun(f, num, start):
    for i in xrange(num):
        start = f(start)
    return start
 
def A(x, y):
    if y == 0:
        return 0
    elif x == 0:
        return 2*y
    else:
        return iter_fun(lambda i: A(x-1, i), y-1, 2)

Więc jednak z tym kodem nie jest tak źle. Można jednak trochę oszukać i wykorzystując matematyczne definicję funkcji A(0,n) i A(1,n) zapisać kod w taki sposób:

(define (A x y)
  (define (A0 n)
    (* 2 n))
  (define (A1 n)
    (if (= n 0)
        0
        (expt 2 n)))
  (cond ((= y 0) 0)
        ((= x 0) (A0 y))
        ((= x 1) (A1 y))
        (else (iter-fun (lambda (i) (A (- x 1) i))
                        (- y 1)
                        2))))

Ten kod generuje poprawną wartość wyrażenia (A 2 5) w niezmierzalnie małym czasie. Testując go dla dużych wartości (A 1 n) można przekonać się o tym, że MzScheme ma lepiej napisaną arytmetykę dużych liczb od Pythona (a co najmniej ich potęgowanie). To, co mnie jednak najbardziej zastanowiło, to różnica w wydajności pomiędzy wersjami 2.3 i 2.4 Pythona. Oto bezpośrednie wyniki uzyskane z interpreterów MzScheme 301, Pythona 2.3 i Pythona 2.4:

MzScheme 301

> (time (expt 2 100000000))
cpu time: 568 real time: 570 gc time: 420

Python 2.3

Python 2.3.5 (#2, Mar  6 2006, 10:12:24)
[GCC 4.0.3 20060304 (prerelease) (Debian 4.0.2-10)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> a = timeit.Timer('2**100000000')
>>> a.timeit(1)
5.5458259582519531

Python 2.4

Python 2.4.2 (#2, Nov 20 2005, 17:04:48)
[GCC 4.0.3 20051111 (prerelease) (Debian 4.0.2-4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> a = timeit.Timer('2**100000000')
>>> a.timeit(1)
13.069931030273438

Pythonowy moduł timeit zwraca czas w sekundach, a funkcja MzScheme time w milisekundach. Różnica więc jest wyraźnie widoczna, dlaczego jednak nowsza wersja Pythona działa ponad dwa razy wolniej od wersji wcześniejszej?

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):~