Poczytaj mi Clojure, cz. 12A: Współbieżność – Atomy

Atom to typ referencyjny przeznaczony do obsługi danych przetwarzanych współbieżnie, do których wymagany jest niekoordynowany, synchroniczny dostęp. Możemy dzięki niemu tworzyć proste i ”lekkie” współdzielone obiekty, wyrażające zmieniające się stany (np. liczniki czy odpowiedniki semaforów).

Współbieżność

Wykonywanie współbieżne (ang. concurrent) to cecha systemów i programów komputerowych, w których te same obliczenia dokonywane są jednocześnie (w tym samym czasie) przez więcej niż jeden komponent, przy opcjonalnej komunikacji między komponentami.

Więcej o współbieżności w Clojure można przeczytać w odcinku 12.

Atomy

Atom (pisany wielką literą) w Clojure to coś innego niż lispowy atom, rozumiany jako element języka, który nie jest listą. Clojure nie jest dialektem zgodnym wstecznie z jakąś wzorcową implementacją (np. z Common Lispem) i dzięki temu może wprowadzać własne koncepcje, głęboko zakorzenione w języku i związane ze środowiskiem uruchomieniowym Javy.

Znane z Lispa atomy są pewną kategorią wyrażeń i w tym znaczeniu nazywanie ich atomami ma sens. Jednak w Clojure znajdziemy również strukturę danych Atom (klasy clojure.lang.Atom), służącą do zarządzania współdzielonym, synchronicznymniezależnym stanem.

Współdzielenie oznacza, że dostęp do obiektu pamięciowego realizowany może być w tym samym czasie przez więcej niż jeden uruchomiony wątek, natomiast synchroniczność, że wątek, który zapoczątkował operację na obiekcie, zablokuje innym wątkom dostęp do niego w danym kwancie czasu, a sam nie będzie wykonywał dalszych czynności, dopóki jej nie zakończy.

Atom, podobnie jak Var, jest typem referencyjnym i przechowuje odniesienia, które mogą być zmieniane z użyciem odpowiednich funkcji. Operacje zmian powiązań tego typu z wartościami zachodzą w sposób atomowy – mogą w całości udać się lub nie. To znaczy, że nie wystąpi sytuacja częściowej modyfikacji lub modyfikacji dokonywanej w tym samym czasie przez więcej niż jeden wątek. Jeżeli zmiana z jakichś przyczyn się nie powiedzie, operacja będzie ponawiana do skutku.

Gdy obiekt typu Atom zmienia wartość bieżącą, dochodzi do podmiany (ang. swap) wartości, na którą Atom wskazuje. Nowa zazwyczaj będzie bazowała na poprzedniej (będzie efektem zastosowania na niej jakiejś funkcji), chociaż można też powiązać obiekt referencyjny z podaną wartością stałą.

Korzystanie z Atomów polega na utworzeniu odpowiedniego obiektu, a następnie aktualizowaniu jego powiązań z wartościami (referencji). Zazwyczaj obiekt typu Atom będzie dodatkowo w sposób stały utożsamiany z symbolem określonym zmienną globalną lub powiązaniem leksykalnym. W ten sposób możliwym stanie się posługiwanie się nim z użyciem nazwy widocznej w odpowiednich obszarach programu.

Tworzenie

Tworzenie obiektów typu Atom, atom

Do tworzenia obiektów typu Atom służy funkcja atom. Przyjmuje ona jeden obowiązkowy argument – wartość początkową (która będzie wskazywana przez referencję) i argumenty nieobowiązkowe opcji, wyrażane w sposób nazwany, czyli w postaci par klucz–wartość.

Funkcja zwraca obiekt typu Atom.

Użycie:

  • (atom wartość-początkowa & opcje).

Możliwe opcje to:

  • :meta mapa-metadanowa,
  • :validator funkcja.

Mapa metadanowa po słowie kluczowym :meta powinna być mapą wyrażoną z użyciem powiązanego z nią symbolu lub osadzoną w kodzie jako tzw. mapowe S-wyrażenie. Podane asocjacje staną się metadanymi tworzonego obiektu referencyjnego.

Funkcja podawana po słowie kluczowym :validator powinna być jednoargumentowym obiektem funkcyjnym, który nie generuje efektów ubocznych lub wartością nil. Funkcja ta będzie wywoływana za każdym razem, gdy dochodzi do zmiany stanu obiektu typu Atom i przekazywana jej będzie nowa wartość. Powinna ona zwracać wartość false lub zgłaszać wyjątek, gdy nowa wartość jest nieakceptowalna. Operację taką nazywamy walidacją, a wyrażającą ją funkcję walidatorem. Pierwsze wywołanie walidatora będzie testowało wartość początkową Atomu.

Przykład użycia funkcji atom
1
2
3
(atom              0)  ; => #<[email protected]: 0>
(atom 0 :meta {:a 1})  ; => #<[email protected]: 0>
(atom        [1 2 3])  ; => #<[email protected]: [1 2 3]>

Wyrażenie z linii nr 1 tworzy obiekt referencyjny typu Atom, który odnosi się do wartości 0. Zauważmy, że 0 jest lispowym atomem, ale nie Atomem z Clojure!

Wyrażenie drugie (z linii nr 2) działa tak samo, lecz dodatkowo ustawia metadaną.

Ostatnie wyrażenie przykładu ustawia wartość początkową na wektor stworzony z użyciem wektorowego S-wyrażenia.

Identyfikowanie Atomów

Atomy są obiektami, z którymi, podobnie jak z innymi pamięciowymi wartościami, można powiązać symboliczne identyfikatory i w ten sposób określać ich tożsamości. Możemy więc stwarzać odnoszące się do obiektów typu Atom globalne zmienne, jak również korzystać z innych rodzajów powiązań (np. leksykalnych).

Przykłady tworzenia powiązań z obiektami typu Atom
1
2
(def nasz-atom (atom 0))        ; zmienna globalna
(let [atomek (atom 0)] atomek)  ; powiązanie leksykalne

Pobieranie wartości

Odczytywanie wartości Atomów, deref

Żeby odczytać wartość Atomu możemy użyć funkcji deref. Przyjmuje ona jeden argument, którym powinien być obiekt typu Atom, a zwraca wartość, do której odniesienie jest przechowywane w tym obiekcie.

Użycie:

  • (deref atom).
Przykład użycia funkcji deref
1
2
3
(def nasz-atom (atom 0))
(deref nasz-atom)
; => 0

Dereferencja Atomów, makro @

Makro czytnika @ (znak małpki) umieszczone przed wyrażeniem sprawia, że jeśli zwracany przez nie obiekt jest typem referencyjnym, to wywołana zostanie na nim funkcja odpowiedzialna za odczyt wskazywanej wartości. W przypadku Atomów będzie to omówiona wyżej funkcja deref.

Użycie:

  • @atom.
Przykład dereferencji Atomu z użyciem makra czytnika @
1
2
3
(def nasz-atom (atom 0))
@nasz-atom
; => 0

Zmiany wartości

Aktualizowanie wartości, swap!

Zmiana stanu obiektu typu Atom, czyli aktualizacja odniesienia, aby wskazywało inną wartość, możliwa jest z zastosowaniem funkcji swap!.

Pierwszy przyjmowany argument powinien być symbolem identyfikującym obiekt typu Atom lub inne wyrażenie, które przeliczone zwróci ten obiekt. Drugim argumentem powinna być funkcja, która jako pierwszy argument przyjmie wartość bieżącą, do której odnosi się Atom i na jej podstawie obliczy i zwróci nową wartość. Zostanie ona użyta do zastąpienia poprzedniego referencyjnego odniesienia w Atomie. Opcjonalnie możemy podać dodatkowe argumenty, które zostaną przekazane jako kolejne argumenty wywoływanej funkcji.

Gdyby któryś z kroków pośrednich (między odczytem a aktualizacją referencji) nie powiódł się, cała operacja będzie ponowiona, dlatego istotne jest, aby użyte funkcje nie miały niezamierzonych efektów ubocznych – należy zakładać, że funkcja obliczająca nową wartość będzie wywołana więcej niż raz.

Wartością zwracaną przez funkcję swap! jest nowa wartość bieżąca referencji.

Użycie:

  • (swap! atom funkcja & argument…).
Przykład użycia funkcji swap!
1
2
3
4
5
(def nasz-atom (atom 0))

@nasz-atom                ; => 0
(swap! nasz-atom inc)     ; => 1
@nasz-atom                ; => 1

Ustawianie wartości, reset!

Funkcja reset! pozwala podmienić obiekt, do którego odnosi się Atom, ale bez obliczania nowej wartości na bazie aktualnie powiązanej z Atomem. Przyjmuje ona dwa argumenty: obiekt typu Atom i nową wartość.

Wartością zwracaną jest nowa wartość bieżąca referencji.

Użycie:

  • (reset! atom wartość).
Przykład użycia funkcji reset!
1
2
3
4
(def nasz-atom (atom 0))
@nasz-atom                ; => 0
(reset! nasz-atom "A")    ; => "A"
@nasz-atom                ; => "A"

Warunkowe ustawianie wartości, compare-and-set!

Funkcja compare-and-set! pozwala podmienić obiekt, do którego odnosi się Atom pod warunkiem, że jego wartość bieżąca jest równa podanej wartości. Pierwszym argumentem wywołania funkcji powinien być obiekt typu Atom, drugim wartość, która zostanie porównana z wartością bieżącą wskazywaną przez Atom, a ostatnim nowa wartość – zostanie ona powiązana z Atomem, jeżeli wspomniany warunek o równości będzie spełniony.

Funkcja zwraca true, jeżeli doszło do podmiany referencji, a false w przeciwnym razie.

Użycie:

  • (compare-and-set! atom poprzednia-wartość nowa-wartość).
Przykład użycia funkcji compare-and-set!
1
2
3
4
5
6
7
8
(def atomek (atom 0))
@atomek                        ; => 0

(compare-and-set! atomek 2 5)  ; => false
@atomek                        ; => 0

(compare-and-set! atomek 0 5)  ; => true
@atomek                        ; => 5

Walidatory

Atomy można opcjonalnie wyposażyć w mechanizmy testujące poprawność ustawianych wartości bieżących. Służą do tego funkcje set-validator!get-validator.

Walidator (ang. validator) to w tym przypadku czysta (wolna od efektów ubocznych), jednoargumentowa funkcja, która przyjmuje wartość poddawaną sprawdzaniu. Jeśli jest ona niedopuszczalna, funkcja powinna zwrócić wartość false lub wygenerować wyjątek.

Zarządzanie walidatorami, set-validator!

Funkcja set-validator! umożliwia ustawianie lub usuwanie walidatora dla podanego jako pierwszy argument obiektu typu Atom.

Jako drugi argument należy podać funkcję, która powinna przyjmować jeden argument i nie generować efektów ubocznych. Będzie ona wywoływana za każdym razem, gdy dojdzie do zmiany stanu referencji i jako argument przekazywana będzie jej wartość, z którą zażądano powiązania. Funkcja ta powinna zwracać wartość false lub zgłaszać wyjątek, gdy przyjmowana wartość jest nieakceptowalna.

Pierwsze sprawdzenie stanu jest dokonywane już w momencie ustawiania walidatora. Bieżąca wartość wskazywana referencją musi więc już wtedy być odpowiednia.

Jeżeli zamiast obiektu funkcyjnego podamy wartość nil, to walidator zostanie odłączony od podanego obiektu typu Atom.

Funkcja set-validator! zwraca wartość nil, jeżeli udało się ustawić walidator.

Przykład użycia funkcji set-validator!
1
2
3
4
5
6
7
8
(def atomek (atom 0))
(set-validator! atomek #(integer? %))  ; akceptujemy tylko liczby całkowite

(reset! atomek 1)
; => 1

(reset! atomek "napis")
; >> java.lang.IllegalStateException: Invalid reference state

Pobieranie walidatora, get-validator

Mając obiekt typu Atom, możemy pobrać funkcyjny obiekt jego walidatora, posługując się funkcją get-validator. Przyjmuje ona jeden argument, który powinien być obiektem typu Atom, a zwraca obiekt funkcji lub nil, jeśli walidatora nie ustawiono.

Użycie:

  • (get-validator atom).
Przykład użycia funkcji get-validator
1
2
3
4
5
6
7
8
(def atomek (atom 0))
(def nasz-walidator #(< % 5))

(set-validator! atomek nasz-walidator)
; => nil

(get-validator atomek)
; => #<user$nasz_walidator [email protected]>

Podpięcia

Obiekty typu Atom można wyposażać w podpięcia (ang. hooks) w postaci tzw. funkcji obserwujących (ang. watch functions). Wywoływane są one, gdy zmienia się stan referencji, a służą do wykonywania dodatkowych, niezależnych operacji w reakcji na te zmiany.

Dodawanie obserwatorów, add-watch

Do obiektu typu Atom możemy dodawać funkcję obserwującą z użyciem add-watch. Funkcja ta przyjmuje trzy argumenty. Pierwszym powinien być Atom, do którego chcemy podłączyć funkcję, drugim unikatowy klucz identyfikujący podpięcie, a ostatnim wspomniana funkcja. Unikatowość powinna być zachowana w obrębie pojedynczego, nadzorowanego obiektu.

Funkcja add-watch zwraca obiekt typu Atom, do którego podpięto funkcję obserwującą.

Funkcja obserwująca powinna przyjmować 4 argumenty: klucz, obiekt typu Atom, a także poprzednią wartość oraz nową wartość wskazywaną przez referencję. Zostanie ona wywołana w sposób asynchroniczny za każdym razem, gdy dojdzie do zmiany stanu Atomu, przy czym może się to zdarzyć również w czasie jej wywoływania. W związku z tym należy polegać na przekazanych jako dwa ostatnie argumenty wartościach, a nie dokonywać dereferencji obiektu typu Atom.

Możemy zarejestrować wiele funkcji obserwujących, a w przypadku korzystania z tego samego funkcyjnego obiektu jesteśmy w stanie rozróżniać wywołania, korzystając z przekazywanego jako argument klucza.

Wywołanie add-watch z takim samym kluczem, jak już podany, zastępuje poprzednią funkcję obserwującą.

Użycie:

  • (add-watch atom klucz funkcja).
Przykład użycia funkcji add-watch
1
2
3
4
5
6
(def atomek (atom 0))
(add-watch atomek :debug #(println (apply str (interpose ", " %&))))

(swap! atomek inc)  ; >> :debug, [email protected], 0, 1
(swap! atomek inc)  ; >> :debug, [email protected], 1, 2
(swap! atomek inc)  ; >> :debug, [email protected], 2, 3

Usuwanie obserwatorów, remove-watch

Funkcja remove-watch pozwala usunąć funkcję obserwującą przypisaną do obiektu typu Atom. Przyjmuje ona dwa obowiązkowe argumenty: obiekt referencyjny i unikatowy klucz identyfikujący podpięcie.

Wartością zwracaną jest obiekt typu Atom, od którego odłączono funkcję obserwującą.

Użycie:

  • (remove-watch atom klucz).
Przykład użycia funkcji remove-watch
1
2
3
4
5
6
7
8
9
10
11
12
(def atomek (atom 0))
(defn reporter [& args] (println (first args)))
(add-watch atomek :debug reporter)
(add-watch atomek :inna  reporter)

(swap! atomek inc)
; >> :debug
; >> :inna

(remove-watch atomek :inna)
(swap! atomek inc)
; >> :debug

Przykłady zastosowań

Globalne tożsamości

Korzystając ze zmiennych globalnych, jesteśmy w stanie tworzyć stałe tożsamości dla wyrażających zmienne stany (przez odniesienia do różnych wartości) obiektów typu Atom. W ten sposób możemy w całym programie odwoływać się do konkretnego Atomu z użyciem nadanej mu symbolicznej nazwy o globalnym zasięgu.

Spróbujmy zaimplementować przykładowy licznik w postaci funkcji, która za każdym wywołaniem będzie zwiększała jego wartość o jeden i zwracała ją, a jeżeli podamy argument, dokonane zostanie przypisanie konkretnej wartości początkowej:

Przykład globalnego licznika i wieloczłonowej funkcji obsługującej
1
2
3
4
5
6
7
8
9
10
11
12
13
(defonce atom-licznika (atom -1))

(defn licznik
  ([x] (reset! atom-licznika (int x)))
  ([]  (swap!  atom-licznika inc)))

(licznik)      ; => 0
(licznik)      ; => 1
(licznik)      ; => 2

(licznik 100)  ; => 100
(licznik)      ; => 101
(licznik)      ; => 102

W pierwszej linii przykładu widzimy wywołanie makra defonce. Służy ono do jednokrotnego ustawiania powiązania głównego podanej zmiennej globalnej. W tym przypadku symbol atom-licznika zostanie powiązany z obiektem typu Atom stworzonym z użyciem funkcji atom. Wartością początkową będzie -1.

W linii nr 3 mamy definicję funkcji wieloczłonowej, czyli takiej, która ma warianty dla różnych zestawów przyjmowanych argumentów. Pierwsze ciało (linia nr 4) przyjmuje jeden argument i służy do ustawiania wartości licznika, jednocześnie zwracając tą wartość. Ciało drugie (linia nr 5) nie przyjmuje argumentów, a wartościowanie jego wyrażenia sprawia, że jako efekt uboczny wywoływana jest funkcja, która zwiększa wartość licznika o jeden, zaś po tej operacji emitowana jest przez funkcję nowa wartość.

Domknięcia

Ciekawym i znajdującym praktyczne zastosowanie sposobem tworzenia Atomów powiązanych ze stałymi tożsamościami jest korzystanie z domknięć. Stwórzmy zmienną globalną, powiązaną z anonimową funkcją, która dokonuje zwiększenia o jeden wartości wskazywanej przez obiekt typu Atom (identyfikowany powiązaniem leksykalnym w ciele obejmującej konstrukcji let):

Przykład użycia domknięcia do śledzenia obiektu typu Atom
1
2
3
4
5
6
7
(defonce licznik
  (let [a (atom -1)]
    #(swap! a inc)))

(licznik)  ;=> 0
(licznik)  ;=> 1
(licznik)  ;=> 2

W powyższym przykładzie anonimowa funkcja z linii nr 3 zamyka w sobie powiązanie symbolu a z obiektem typu Atom, które jest widoczne w obejmującym kontekście leksykalnym. Funkcja ta zostaje w linii nr 1 nazwana z użyciem zmiennej globalnej. Możemy więc korzystać z symbolu licznik do tworzenia formuły funkcyjnej, która uruchomi podprogram realizujący operację zwiększenia o jeden wartości wskazywanej przez Atom.

Spójrzmy jeszcze na podobną implementację licznika, lecz zrealizowaną z użyciem funkcji generującej obiekty typu Atom:

Przykład generatora liczników
1
2
3
4
5
6
7
8
9
(defn utwórz-licznik [wartość]
  (let [a (atom (dec wartość))]
    #(swap! a inc)))

(defonce licznik (utwórz-licznik 0))

(licznik)  ; => 0
(licznik)  ; => 1
(licznik)  ; => 2

Implementacja spamiętywania

Spamiętywanie (ang. memoization) to sposób optymalizacji programów komputerowych przez zapisywanie rezultatów wywołań czasochłonnych operacji, aby przy kolejnych ich wywołaniach korzystać z zapamiętanych wartości dla takich samych warunków wejściowych (np. argumentów).

W Clojure istnieje gotowa funkcja wyższego rzędu, memoize, która służy do buforowania wywołań innych funkcji z wykorzystaniem asocjacyjnej struktury, której kluczami są wartości przekazywanych argumentów. Nie zawsze jednak będziemy chcieli polegać wyłącznie na argumentach i zapisywać tylko zwracaną przez funkcję wartość (np. w przypadku obliczeń rekurencyjnych, gdzie przydałoby się zapamiętywanie rezultatów pośrednich). W takich przypadkach możemy pokusić się o stworzenie własnej funkcji spamiętującej.

Implementując mechanizmy buforowania obliczeń, możemy skorzystać z Atomów, aby synchronizować modyfikacje struktur z rezultatami, które mogą być współdzielone między równolegle realizowanymi wątkami. Oczywiście tak naprawdę żadne struktury nie będą modyfikowane, lecz będziemy mieć do czynienia z uaktualnieniami odniesień do coraz to nowych buforów.

Przykład spamiętywania wywołań funkcji
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defn !
  ([n] (! n 1))
  ([n acc] (if (zero? n) acc (recur (dec n) (*' acc n)))))

(defn spamiętaj [f]
  (let [a (atom {})]
    (fn [& args]
      (if-let [wynik (find @a args)]
        (val wynik)
        (let [r (apply f args)]
          (swap! a assoc args r)
          r)))))

(def ! (spamiętaj !))

(time (do (! 8000) nil))  ; >> "Elapsed time: 260.910553 msecs"
(time (do (! 8000) nil))  ; >> "Elapsed time: 0.085696 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 168.098467 msecs"

Zamiast definiować funkcję spamiętaj możemy też posłużyć się wspomnianą, wbudowaną funkcją memoize, która również korzysta z Atomów.

Widzimy, że w linii nr 17 rezultat nie był przeliczany, lecz serwowany z podręcznej mapy, do której dostępem zarządza referencyjny obiekt typu Atom. W związku z tym czas wykonywania był nieporównywalnie mniejszy.

Optymizm kończy się jednak w linii nr 18, gdzie możemy zaobserwować, że niezależnie od tego, czy posłużymy się memoize czy własną funkcją spamiętaj, nie będziemy mieli do czynienia z wykorzystaniem rezultatów pośrednich rekurencyjnych wywołań, ponieważ zapisywane są tylko ostateczne wyniki obliczeń zwracane przez funkcję. Jeżeli wywołamy ją dla argumentu o wartości 8000, a potem dla 7999, to rekursywne operacje mnożenia dla tego samego zakresu ciągu rezultatów (od 1 do 7999) będą za drugim razem obliczane ponownie. Spróbujmy więc przerobić nieco nasz kod, aby było inaczej:

Przykład spamiętywania rekurencyjnych wywołań z buforem rezultatów pośrednich
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(def !                                      ; definicja zmiennej globalnej
  (let [mem (atom [1 2 6 24])]              ; Atom z buforem rezultatów
    (fn f                                   ; funkcja anonimowa
      ([n]                                  ; pierwsze ciało (jeden argument):
       (let [mem-cnt (count @mem)]          ; ostatnio zapamiętany wynik
         (if (<= n mem-cnt)                 ; czy zapamiętano?
           (nth @mem (dec n))               ; · tak: zwróć zapamiętany rezultat
           (f n                             ; · nie: zacznij od ostatniego pamiętanego
              (inc mem-cnt)
              (nth @mem (dec mem-cnt))))))
      ([n cur acc]                          ; drugie ciało (trzy argumenty):
       (let [new-cur (inc cur)              ; nowy nr kolejny
             new-acc (*' acc cur)           ; nowy rezultat
             cur-idx (dec cur)]             ; bieżący indeks wektora podręcznego
         (swap! mem assoc cur-idx new-acc)  ; zapamiętaj rezultat
         (if (= n cur)                      ; warunek zakończenia
           new-acc                          ; · przypadek bazowy
           (recur n new-cur new-acc)))))))  ; · przypadek rekursywny

(time (do (! 8000) nil))  ; >> "Elapsed time: 180.090641 msecs"
(time (do (! 8001) nil))  ; >> "Elapsed time: 0.108044 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.185428 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.048888 msecs"

Zamiast definiować funkcję nazwaną z użyciem defn skorzystaliśmy tu z funkcji anonimowej (fn), którą potem nazwaliśmy, tworząc zmienną globalną (def). Dzięki temu funkcja może korzystać z powiązanego z obiektem typu Atom symbolu mem (linia nr 2). Mamy do czynienia z domknięciem, ponieważ powiązanie jest utworzone i widoczne w obejmującym definicję funkcji zasięgu leksykalnym.

Przypomnijmy, że mamy do czynienia z funkcją wieloczłonową, tzn. taką która może mieć kilka wariantów, różniących się zestawami przyjmowanych argumentów. W naszym przypadku mamy dwa ciała: pierwsze jednoargumentowe (linie od 4 do 10), drugie trójargumentowe (linie od 11 do końca). Zadaniem pierwszego jest przygotowanie liczników przekazywanych jako argumenty i sprawdzenie, czy można kontynuować obliczenia z wykorzystaniem zapisanych w pamięci podręcznej wyników, a następnie wywołanie wariantu trójargumentowego dla określonych wartości początkowych. Ciało drugie to właściwa funkcja obliczeniowa.

W powyższym kodzie zmieniliśmy nieco algorytm wyliczania silni: zamiast zmniejszać licznik o 1 przy każdym rekursywnym wywołaniu i dążyć do zera, rozpoczynamy od 1 i sprawdzamy, czy już przemnożyliśmy wszystkie kolejne rezultaty pośrednie. Dzięki temu jesteśmy w stanie umieszczać je w pamięci podręcznej, a przy tym wciąż korzystać z optymalizacji w postaci rekurencji ogonowej. Rezultaty pośrednie (wartości silni dla kolejnych liczb całkowitych) przekazywane są jako ostatni argument wywołania funkcji wyliczającej (parametr acc), a jako jej drugi argument (parametr cur) przekazywana jest bieżąca pozycja wyniku w ciągu. Pierwszy parametr (n) zawiera wartość używaną do określenia warunku zakończenia rekurencji.

Zamiast korzystać z zewnętrznej funkcji spamiętującej, buforowanie rezultatów zostało ściśle zintegrowane z implementacją algorytmu. Dzięki temu w buforze nie są zapisywane wyłącznie rezultaty dla konkretnych argumentów, ale również wyniki pośrednie, które w przypadku obliczeń silni nadają się do ponownego użycia w kolejnych wywołaniach. Efekty możemy zauważyć, badając czasy wykonania: obliczenia dla liczb większych niż wcześniej zapamiętane są rozpoczynane od ostatnio zapisanych wyników, a nie od początku, co skutkuje znacznie krótszymi czasami realizacji algorytmu.

Do przechowywania rezultatów używamy wektora, który jest strukturą danych dobrze pasującą do problemu: jego kluczami są kolejne liczby całkowite, a dostęp do elementu o wskazanej pozycji odbywa się w stałym czasie.

Warto nadmienić, że podobny efekt (buforowania rezultatów pośrednich) możemy uzyskać również wtedy, gdy wyrazimy dany algorytm z użyciem leniwej sekwencji.

Na koniec możemy pokusić się o modyfikację naszej funkcji w taki sposób, aby była bardziej hermetyczna (nie pozwalała na bezpośrednie wywoływanie wariantu wieloargumentowego) i zwięźlej wyrażona. Zamiast tworzyć dodatkowe ciało skorzystamy z konstrukcji loop. Dzięki temu uda się też uniknąć przekazywania przez argument wartości używanej w warunku zakończenia rekurencji (parametr n). Poza tym dodamy obsługę przypadku, gdy argumentem jest zero, a zamiast akumulować poprzednio obliczone wyniki w parametrze wywołania, będziemy je pobierali z bufora rezultatów, do którego wcześniej trafiają:

Przykład rekurencji ogonowej ze spamiętywaniem dla funkcji silnia (loop)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(def !                                            ; definicja zmiennej globalnej
  (let [m (atom [1 1 2 6 24])]                    ; Atom z buforem rezultatów
    (fn [n]                                       ; funkcja:
      (let [m-count (count @m)]                   ; nr ostatnio zapamiętanego wyniku
        (if (< n m-count)                         ; czy zapamiętano dla bieżącego?
          (nth @m n)                              ; · tak: zwróć zapamiętany rezultat
          (loop [cur m-count]                     ; · nie: wywołaj konstrukcję liczącą
            (let [r (*' (nth @m (dec cur)) cur)]  ; nowy rezultat
              (swap! m assoc cur r)               ; zapamiętaj rezultat
              (if (= n cur)                       ; warunek zakończenia
                r                                 ; · przypadek bazowy
                (recur (inc cur))))))))))         ; · przypadek rekursywny

(time (do (! 8000) nil))  ; >> "Elapsed time: 154.966845 msecs"
(time (do (! 8001) nil))  ; >> "Elapsed time: 0.104064 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.092260 msecs"
(time (do (! 7999) nil))  ; >> "Elapsed time: 0.064882 msecs"

Ten materiał jest częścią większej całości, którą można zobaczyć odwiedzając poniższy odnośnik:

Komentarze