W poszukiwaniu idealnej formy

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

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.

Strumień 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:

One day hack