W poszukiwaniu idealnej formy
lipiec 27th, 2006 at 10:15 pm (scheme, python)
ZaczÄ???o siÄ? niewinnie. Otworzy??em ko??cowe strony pierwszego rozdzia??u Wizard Booka z nadziejÄ? na rozwiÄ?zanie kilku zada?? i rych??e przej??cie do czÄ???ci m??wiÄ?cej o abstrakcji danych, po czym przeczyta??em tre??Ä? zadania 1.22 i zabra??em siÄ? do pracy. Og??lnie rzecz biorÄ?c nale??a??o napisaÄ? procedurÄ? search-for-primes, kt??ra szuka 3 liczb pierwszych wiÄ?kszych od zadanego n i pokazuje czas wykorzystany na obliczenie ka??dej z nich. Definicje funkcji wypisujÄ?cych zosta??y podane w Ä?wiczeniu, ale jako ??e ja zawsze wiem lepiej (i nie podoba mi siÄ? mieszanie kodu obliczajÄ?cego z wy??wietlajÄ?cym), napisa??em je po swojemu. ZaczÄ???em od napisania og??lnej funkcji do mierzenia czasu wykoniania dowolnej funkcji:
(define (timed-function-test fun)
(let ((start-time (runtime))
(result (fun))
(end-time (runtime)))
(values result (- end-time start-time))))
Jej dzia??anie jest proste: pobiera czas poczÄ?tkowy, wywo??uje funkcjÄ? zapamiÄ?tujÄ?c wynik, pobiera czas ko??cowy i zwraca dwie warto??ci: warto??Ä? wywo??anej funkcji i czas jej wykonania. Tak, naprawdÄ? zwraca dwie warto??ci, a to dziÄ?ki formie specjalnej values. P????niej tego wyboru po??a??owa??em, o wiele wygodniej u??yÄ? jest zwyk??ej pary, values nie dajÄ? siÄ? bowiem zagnie??d??aÄ? i og??lnie rzecz biorÄ?c nie mo??na z nimi zrobiÄ? nic poza natychmiastowego roz??o??enia na zwracane warto??ci przy pomocy let-values. Wr??cimy jednak do tego jeszcze p????niej.
Do powy??szej definicji timed-function-test dodaÄ? jeszcze trzeba skÄ?d wziÄ???o siÄ? runtime. W implementacji Scheme, kt??rej u??ywam (mzscheme) nie ma funkcji runtime, jest za to current-inexact-milliseconds, kt??re mo??na z ??atwo??ciÄ? zaliasowaÄ?:
(define runtime current-inexact-milliseconds)
KorzystajÄ?c z procedury timed-function-test funkcjÄ? timed-prime-test zdefiniowaÄ? mo??na nastÄ?pujÄ?co:
(define (timed-prime-test n)
(timed-function-test (lambda () (prime? n))))
Obudowujemy funkcjÄ? prime? lambdÄ? bez argument??w, dziÄ?ki temu w??a??nie funkcja timed-function-test mo??e jÄ? wywo??aÄ? poprzez proste (fun).
1.
Mierzenie czasu mamy ju?? opracowane, czas zajÄ?Ä? siÄ? szukaniem samych liczb pierwszych.
(define (search-for-primes how-many start)
(define (_search-for-primes how-many start results)
(if (= how-many 0)
(reverse results)
(let-values (((primality elapsed-time)
(timed-prime-test start)))
(_search-for-primes (if primality
(- how-many 1)
how-many)
(+ start 2)
(if primality
(cons (cons start elapsed-time)
results)
results)))))
(_search-for-primes how-many
(if (even? start)
(+ start 1)
start)
‘()))
WewnÄ?trz definiujÄ? pomocniczÄ? funkcjÄ? _search-for-primes, by m??c zbieraÄ? liczby pierwsze na li??cie results, jak i po to by zawsze zaczynaÄ? poszukiwania od liczby nieparzystej (stÄ?d forma if z predykatem even?). W ka??dej iteracji zwiÄ?kszamy bowiem aktualnÄ? liczbÄ? do sprawdzenia o 2, wychodzÄ?c z za??o??enia, ??e ??adna liczba parzysta poza 2 nie jest pierwsza i warto skupiÄ? siÄ? tylko na liczbach nieparzystych. Nie zmniejsza to z??o??ono??ci, ale liczba krok??w jest o po??owÄ? mniejsza. Przy pomocy formy specjalnej let-values przypisujÄ? do zmiennych primality i elapsed-time warto??ci zwr??cone przez timed-prime-test. Je??eli sprawdzona liczba by??a pierwsza wywo??ujemy siebie ze zmniejszonÄ? o jeden warto??ciÄ? how-many i dodanÄ? do listy wynik??w results liczbÄ? i czasem jej obliczania. Je??eli trafili??my na liczbÄ? z??o??onÄ?, wywo??ujemy siebie z niezmienionymi warto??ciami how-many i results, zwiÄ?kszajÄ?c tylko aktualnÄ? liczbÄ? o 2.
2.
Ot, podrÄ?cznikowy przyk??ad wykorzystania rekursji do iteracji. Problem w tym, ??e kod ten jest brzydki. Przedstawia on imperatywnÄ? ideÄ? zapisanÄ? przy pomocy dziwacznej lispowej sk??adni. Podobny kod w Pythonie mo??na by zapisaÄ? nastÄ?pujÄ?co:
def search_for_primes(how_many, start):
result = []
if start % 2 == 0:
start += 1
while how_many > 0:
primality, elapsed_time = timed_prime_test(start)
if primality:
how_many -= 1
result.append((start, elapsed_time))
start += 2
return result
Tak, to jest o wiele czytelniejsze. Ale nie da??em za wygranÄ?. Scheme nie ma czego zazdro??ciÄ? Pythonowi, je??eli chodzi o sk??adniÄ?, bo sk??adniÄ? mo??e mieÄ? takÄ?, jakÄ? tylko sobie wymarzymy 8-). Pobawi??em siÄ? wiÄ?c trochÄ? makrami i uda??o mi siÄ? przepisaÄ? funkcjÄ? search-for-primes tak by przypomina??a Pythonowy kod:
(define (search-for-primes how-many start)
(define result-list ‘())
(begin
(if (even? start)
(inc! start))
(while (> how-many 0)
(let-values (((primality elapsed-time)
(timed-prime-test start)))
(begin
(if primality
(begin
(dec! how-many)
(append-to-list! result-list
(cons start elapsed-time))))
(inc! start 2))))
result-list))
Prawdopodobnie mo??na by za pomocÄ? wiÄ?kszej ilo??ci magii jeszcze bardziej ten kod upodobniÄ? do Pythonowego, tyle ??e jaki w tym sens. Moim celem nie jest nauczenie siÄ? programowania w Pythonie ze sk??adniÄ? Scheme, ale poznanie nowych sposob??w rozwiÄ?zywania problem??w. A w tym przypadku czujÄ?, ??e brnÄ? w z??ym kierunku. Musi istnieÄ? bardziej naturalny dla Scheme spos??b rozwiÄ?zania tego zadania.
3.
ZaczÄ???em wiÄ?c od analizy tego, co by??o z??ego w starej wersji search-for-primes. Przede wszystkim nie podoba??o mi siÄ? to w jaki spos??b wykonywane sÄ? kolejne iteracje. Stara??em siÄ? wykorzystaÄ? zwyk??Ä? rekurencjÄ?, wed??ug zasad jakich nauczy??em siÄ? wcze??niej. ChcÄ?c uczyniÄ? wykonywany proces iteracyjnym wykorzysta??em do zbierania wynik??w listÄ? results. Efektem jest procedura, kt??ra nie przypomina pierwotnie postawionego problemu. W??a??nie, na czym ten problem polega??? Nale??y wyselekcjonowaÄ? M liczb pierwszych wiÄ?kszych od zadanego N i pokazaÄ? czas wykonania procedury sprawdzajÄ?cej dla ka??dej z nich. Selekcja, czyli filtrowanie! To jest w??a??nie to, czego szuka??em. U??o??Ä? ca??Ä? procedurÄ? w jeden ciÄ?g funkcji filtrujÄ?cych i mapujÄ?cych, na jednym ko??cu wpuszczajÄ?c do strumienia liczby nieparzyste, a na drugim wyciÄ?gajÄ?c liczby pierwsze. Strumie?? - to jest odpowied??!
By jednak m??c wykorzystaÄ? tÄ? technikÄ? musia??em utworzyÄ? generator - funkcjÄ?, kt??ra zachowuje stan i przy kolejnych wywo??aniach zwraca (generuje) kolejne warto??ci. W Pythonie tworzenie generator??w jest bardzo proste:
def nieparzyste():
i = 1
while True:
yield i
i += 2
gen = nieparzyste()
print gen.next() # => 1
print gen.next() # => 3
print gen.next() # => 5
W Scheme z generatorami jeszcze siÄ? nie spotka??em. Przeszuka??em wiÄ?c archiwa grupy comp.lang.scheme, potem zasiÄ?gnÄ???em rady Google. Wreszcie w artykule Iterators: Signs of Weakness in Object-Oriented Languages znalaz??em to, czego szuka??em. I rozwiÄ?zanie okaza??o siÄ? najprostsze jak to tylko mo??liwe. Nale??y utworzyÄ? listÄ? z op????nionym warto??ciowaniem (czy te?? warto??ciowaniem leniwym od ang. lazy evaluation). TakÄ? listÄ? mo??na ??atwo wykorzystaÄ? do napisania generatora: kolejne warto??ci listy obliczane sÄ? bowiem dopiero wtedy, gdy sÄ? potrzebne. A jak stworzyÄ? takÄ? leniwÄ? listÄ?? Przy pomocy lambda, proszÄ? bardzo:
(define-syntax lazy-cons
(syntax-rules ()
((_ x y)
(cons x (lambda () y)))))
Makro to przekszta??ca (lazy-cons x y) na (cons x (lambda () y)), zamykajÄ?c drugÄ? warto??Ä? w lambdzie, tym samym op????niajÄ?c jej obliczenie.
Pobranie pierwszego elementu pary nastÄ?puje przez zwyk??e car:
(define lazy-car car)
Uzyskanie za?? drugiego elementu wymaga wywo??ania lambdy:
define (lazy-cdr x)
((cdr x)))
DziÄ?ki temu mechanizmowi uzyskujemy mo??liwo??Ä? tworzenia niesko??czonych list. ListÄ? liczb naturalnych mo??na otrzymaÄ? za pomocÄ? nastÄ?pujÄ?cej definicji:
(define (infinity-starting-at start)
(lazy-cons start (infinity-starting-at (+ start 1))))
(define natural-numbers
(infinity-starting-at 1))
Do kolejnych element??w odwo??ujemy siÄ? tak samo, jak do zwyczajnej listy, tyle ??e korzystajÄ?c z “leniwych” wersji funkcji car i cdr.
> (lazy-car natural-numbers)
1
> (lazy-car (lazy-cdr natural-numbers))
2
> (lazy-car (lazy-cdr (lazy-cdr natural-numbers)))
3
> (lazy-car (lazy-cdr (lazy-cdr (lazy-cdr natural-numbers))))
4
Leniwe listy ju?? mia??em zaimplementowane, teraz przyszed?? czas na leniwe wersje funkcji map i filter. Definicja pierwszej jest bardzo prosta:
define (lazy-map fun lazy-list)
(if (null? lazy-list)
‘()
(lazy-cons (fun (lazy-car lazy-list))
(lazy-map fun (lazy-cdr lazy-list)))))
Ka??dÄ? z warto??ci listy lazy-list przepuszczamy przez funkcjÄ? fun. Na miejsce starej listy otrzymujemy nowÄ?, z ka??dÄ? warto??ciÄ? bÄ?dÄ?cÄ? wynikiem dzia??ania fun. Implementacja lazy-filter jest tylko odrobinÄ? bardziej skomplikowana:
(define-opt (lazy-filter decide-fun lazy-list [how-many -1])
(if (or (null? lazy-list) (= how-many 0))
‘()
(let ((current (lazy-car lazy-list)))
(if (decide-fun current)
(lazy-cons current
(lazy-filter decide-fun
(lazy-cdr lazy-list)
(- how-many 1)))
(lazy-filter decide-fun
(lazy-cdr lazy-list)
how-many)))))
Kilka rzeczy wymaga tutaj komentarza. Po pierwsze, u??yte przeze mnie nawiasy kwadratowe s??u??Ä? tylko i wy??Ä?czenie zwiÄ?kszeniu czytelno??ci. Ich dzia??anie jest dok??adnie takie same jak nawias??w okrÄ?g??ych. Tymczasem samo define-opt zosta??o zdefiniowane w SRFI 89, rozszerzeniu do standardu, kt??re implementuje opcjonalne i kluczowe parametry dla funkcji. W tym przypadku domy??lnÄ? warto??ciÄ? dla how-many jest -1. Tym samym funkcja lazy-filter mo??e byÄ? wywo??ana z dwoma lub trzema parametrami. Jej dzia??anie polega na przefiltrowaniu na podstawie funkcji decide-fun podanej leniwej listy, tzn. wyborze tych element??w listy, dla kt??rych funkcja zwraca warto??Ä? prawda. Opcjonalny parametr how-many ka??e filtrowi przerwaÄ? dzia??anie po wyselekcjonowaniu podanej ilo??ci element??w.
Jeste??my ju?? prawie gotowi. OstatniÄ? rzeczÄ?, jaka jest potrzebna, jest funkcja konwertujÄ?ca dowolnÄ? leniwÄ? listÄ? na zwyk??Ä? listÄ?. Nie radzÄ? jej odpalaÄ? na listach niesko??czonych. ;-)
(define (lazy->list L)
(if (null? L)
L
(cons (lazy-car L) (lazy->list (lazy-cdr L)))))
Gotowe, mo??emy ju?? swobodnie korzystaÄ? z leniwych list. Przyk??adowo, by uzyskaÄ? pierwsze dziesiÄ?Ä? parzystych liczb, mo??emy napisaÄ?:
> (lazy->list (lazy-filter even? natural-numbers 10))
(2 4 6 8 10 12 14 16 18 20)
Wyselekcjonowanie 5 liczb nieparzystych, a nastÄ?pnie przemno??enie ka??dej z nich przez dwa wyglÄ?da??o by nastÄ?pujÄ?co:
> (lazy->list (lazy-map
(lambda (x) (* x 2))
(lazy-filter odd? natural-numbers 5)))
(2 6 10 14 18)
Implementacja search-for-primes jest teraz bardzo ??atwa do napisania:
;; pozbycie sie ‘values’ na rzecz zwyklego ‘cons’
(define (timed-function-test fun)
(let ((start-time (runtime))
(result (fun))
(end-time (runtime)))
(cons result (- end-time start-time))))
(define (timed-prime-test n)
(timed-function-test (lambda () (cons (prime? n) n))))
(define (search-for-primes how-many start)
(define odd-numbers
(lazy-filter odd? (infinity-starting-at start)))
(define (decide test-result)
(caar test-result))
(define (get-rid-of-primality test-result)
(cons (cdar test-result) (cdr test-result)))
(lazy->list (lazy-map get-rid-of-primality
(lazy-filter decide
(lazy-map timed-prime-test
odd-numbers)
how-many))))
Tak, to jest ju?? bardziej w stylu Scheme. Jak dla mnie jednak wciÄ??? zbyt rozwlekle. Klucz do uproszczenia tego kodu ju?? wiemy jak nazwaÄ?: abstrakcja.
4.
Jednym ze s??abych punkt??w poprzedniej implementacji jest niejasno??Ä? operacji wykonywanych na strukturze test-result. Postanowi??em wiÄ?c obudowaÄ? dostÄ?p do ka??dej ze sk??adowych struktury odpowiedniÄ? funkcjÄ?. Argumenty funkcji sÄ? teraz r??wnie?? przechowywane w??r??d wynik??w timed-function-test.
(define (make-timed-result fun-args fun-result elapsed-time)
(cons fun-args (cons fun-result elapsed-time)))
(define (get-fun-args timed-result)
(car timed-result))
(define (get-fun-result timed-result)
(cadr timed-result))
(define (get-elapsed-time timed-result)
(cddr timed-result))
(define (timed-function-test fun args)
(let ((start-time (runtime))
(result (apply fun args))
(end-time (runtime)))
(make-timed-result args result (- end-time start-time))))
KolejnÄ? rzeczÄ?, kt??ra prosi??a siÄ? o ulepszenie by?? kod wy??wietlajÄ?cy. Tutaj posunÄ???em siÄ? trochÄ? dalej, dajÄ?c u??ytkownikowi mo??liwo??Ä? ustalenia formatu wy??wietlanych danych. Dla zadanej listy wynik??w timed-results kolejne linie wy??wietlane sÄ? wed??ug formatu output-string. W formacie mo??na korzystaÄ? z trzech specjalnych ciÄ?g??w: %a zostanie zastÄ?piony listÄ? argument??w dla badanej funkcji, %r jej wynikiem, a %t czasem jej wykonania. Implementacja poni??ej.
(define (cut-precision inexact digits)
(define factor (expt 10 digits))
(/ (round (* inexact factor)) factor))
(define (replace-all dictionary string)
(if (null? dictionary)
string
(letrec ((rule (car dictionary))
(from (car rule))
(to (cdr rule)))
(replace-all (cdr dictionary)
(regexp-replace* from string to)))))
(define (report-timed-result output-string timed-result)
(let ((fun-args (format “~a” (get-fun-args timed-result)))
(fun-result (format “~a” (get-fun-result timed-result)))
(elapsed-time (number->string
(cut-precision (get-elapsed-time timed-result)
4))))
(begin
(display (replace-all (list (cons “%a” fun-args)
(cons “%r” fun-result)
(cons “%t” elapsed-time))
output-string))
(newline))))
(define (display-timed-results output-string timed-results)
(if (not (null? timed-results))
(let ((first-result (car timed-results)))
(begin
(report-timed-result output-string first-result)
(display-timed-results output-string (cdr timed-results))))))
Jako, ??e liczenie czasu wykonania funkcji szukajÄ?cej liczby pierwsze jest szczeg??lnym przypadkiem og??lniejszego problemu, najpierw zdefiniowa??em og??lnÄ? funkcjÄ? generate-statistics:
(define-opt (generate-statistics function feed decide-fun how-many
[output-string “%a->%r: %t”])
(define dtr display-timed-results)
(define tft timed-function-test)
(dtr output-string
(lazy->list (lazy-filter decide-fun
(lazy-map (lambda args
(tft function args))
feed)
how-many))))
Definicja search-for-primes wyglÄ?da w??wczas najpro??ciej jak to tylko mo??liwe:
(define (search-for-primes how-many start)
(define odd-numbers
(lazy-filter odd? (infinity-starting-at start)))
(define (decide timed-result)
(get-fun-result timed-result))
(generate-statistics prime? odd-numbers decide how-many “%a: %t”))
Uff, doj??cie do tej postaci trochÄ? wysi??ku mnie kosztowa??o, ale i rezultat jest nareszcie zadowalajÄ?cy. Do??Ä? na dzi??, do zobaczenia nastÄ?pnym razem. :-)
pliki
Dla wnikliwych, poni??ej zamieszczam linki do pe??nych kod??w ??r??d??owych wszystkich przedstawionych w tym wpisie przyk??ad??w:
- search-for-primes-1.ss: pierwsza naiwna implementacja
- search-for-primes-2.ss: druga, w stylu Pythona, wykorzystujÄ?ca makra
- search-for-primes-3.ss: trzecia, wykorzystujÄ?ca leniwe listy
- search-for-primes-4.ss: czwarta, r??wnie?? z leniwymi listami, z lepszym wy??wietlaniem
- search-for-primes-common.ss: definicje dotyczÄ?ce zadania
- search-for-primes-lazy.ss: implementacja leniwych list
- search-for-primes-macro.ss: makra s??u??Ä?ce drugiej implementacji
- 89.ss: kod SRFI 89