Walcząc z czasem

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