stats

Poczytaj mi Clojure, cz. 16

Współbieżność: Atomy

Grafika

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ć współdzielone obiekty wyrażające zmieniające się stany, gdy zależy nam na tym, aby podczas zmiany wartości bieżącej uwzględniona była jej poprzednia wartość, chociaż dopuszczamy drobne zmiany w kolejności operacji, gdy więcej niż jedna aktualizacja zostanie zlecona w podobnym czasie.

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 15.

Atomy

Atom (pisany wielką literą) to w Clojure coś innego niż lispowy atom, rozumiany jako S-wyrażenie, które nie jest listą. Znane z Lispu atomy są pewną kategorią wyrażeń i w tym znaczeniu nazywanie ich atomami ma sens. Jednak w Clojure znajdziemy również typ danych Atom (bazujący na klasie clojure.lang.Atom), służący do zarządzania współdzielonym, synchronicznymniekoordynowanym stanem.

Współdzielenie oznacza, że żądanie dostępu do obiektu pamięciowego realizowane 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 podczas jej trwania, 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 do wartości, które mogą być zmieniane z użyciem odpowiednich funkcji. Operacje zmian powiązań referencji 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 wskazanej funkcji), chociaż można też powiązać obiekt referencyjny z podaną wartością stałą, ignorując zastaną.

Korzystanie z Atomów polega na utworzeniu odpowiedniego obiektu, a następnie aktualizowaniu jego powiązania z wartością z użyciem przekazywanej funkcji. Zazwyczaj obiekt typu Atom będzie dodatkowo w sposób stały utożsamiany z symbolem określonym pewną 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.

Warto zaznaczyć, że – w przeciwieństwie do omawianego w dalszej części Agenta – podczas zmiany wartości bieżącej Atomu przekazywana funkcja aktualizująca będzie wywoływana do skutku, tzn. dopóki z powodzeniem uda się ustawić nową wartość. Przyczyną ponownego wywołania może być nałożenie się żądań zmian w podobnym oknie czasowym i dezaktualizacja wartości bieżącej w trakcie ustawiania nowej. Nie powinniśmy więc zakładać, że zawarte w funkcji uaktualniającej wyrażenia będą przeliczane tylko raz.

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ą (wskazywaną następnie przez referencję) i nieobowiązkowe argumenty 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 podczas wywołania nie generuje efektów ubocznych, albo wartością nil. Przekazana funkcja będzie wywoływana za każdym razem, gdy dojdzie do zmiany stanu obiektu referencyjnego i przekazywana jej będzie nowo ustawiana wartość. Powinna ona zwracać false lub zgłaszać wyjątek, gdy wartość ta jest nieakceptowalna. Operację taką nazywamy walidacją, a wyrażającą ją funkcję walidatorem. Do pierwszego wywołania walidatora dojdzie podczas ustawiania wartości początkowej.

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]>
(atom 0) ; =&gt; #&lt;[email protected]: 0&gt; (atom 0 :meta {:a 1}) ; =&gt; #&lt;[email protected]: 0&gt; (atom [1 2 3]) ; =&gt; #&lt;[email protected]: [1 2 3]&gt;

Wyrażenie z linii nr 1 tworzy obiekt referencyjny typu Atom, który odnosi się do wartości 0. Zauważmy, że 0 nazwiemy 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 utworzony z wykorzystaniem 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. 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
(def nasz-atom (atom 0)) ; zmienna globalna (let [atomek (atom 0)] atomek) ; powiązanie leksykalne

Mogą również zdarzyć się sytuacje, w których powiązanie leksykalne będzie widoczne wewnątrz definiowanej funkcji anonimowej stanowiącej domknięcie. Jest to sposób na obsługę współdzielonego, lecz ograniczonego leksykalnie stanu.

Pobieranie wartości

Odczytywanie wartości Atomów, deref

Żeby odczytać wartość bieżącą Atomu możemy użyć funkcji deref. Przyjmuje ona jeden argument, którym powinien być obiekt typu Atom, a zwraca wartość bieżącą.

Użycie:

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

Dereferencja Atomów, makro @

Makro czytnika @ (znak małpki) umieszczone przed wyrażeniem sprawia, że jeżeli reprezentowany nim obiekt jest typem referencyjnym, wywołana zostanie na nim funkcja odpowiedzialna za odczyt wskazywanej wartości bieżącej. 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
(def nasz-atom (atom 0)) @nasz-atom ; =&gt; 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!.

Pierwszym przyjmowanym argumentem powinien być obiekt typu Atom. Drugim funkcja, która jako pierwszy argument przyjmie wartość bieżącą Atomu i na jej podstawie obliczy 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
(def nasz-atom (atom 0)) @nasz-atom ; =&gt; 0 (swap! nasz-atom inc) ; =&gt; 1 @nasz-atom ; =&gt; 1

Ustawianie wartości, reset!

Funkcja reset! pozwala podmienić obiekt, do którego odnosi się Atom, ale bez obliczania nowej wartości na bazie aktualnej. 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"
(def nasz-atom (atom 0)) @nasz-atom ; =&gt; 0 (reset! nasz-atom &#34;A&#34;) ; =&gt; &#34;A&#34; @nasz-atom ; =&gt; &#34;A&#34;

Ustawianie warunkowe, 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 wartości bieżącej, 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
(def atomek (atom 0)) @atomek ; =&gt; 0 (compare-and-set! atomek 2 5) ; =&gt; false @atomek ; =&gt; 0 (compare-and-set! atomek 0 5) ; =&gt; true @atomek ; =&gt; 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żeli 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, walidator zostanie odłączony od podanego obiektu typu Atom.

Funkcja set-validator! zwraca wartość nieustaloną 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
(def atomek (atom 0)) (set-validator! atomek #(integer? %)) ; akceptujemy tylko liczby całkowite (reset! atomek 1) ; =&gt; 1 (reset! atomek &#34;napis&#34;) ; &gt;&gt; java.lang.IllegalStateException: Invalid reference state

Pobieranie walidatora, get-validator

Mając obiekt typu Atom, możemy pobrać funkcyjny obiekt przypisanego mu walidatora z użyciem get-validator. Funkcja ta przyjmuje jeden argument typu Atom, a zwraca obiekt funkcji lub wartość nieustaloną nil, gdy 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]>
(def atomek (atom 0)) (def nasz-walidator #(&lt; % 5)) (set-validator! atomek nasz-walidator) ; =&gt; nil (get-validator atomek) ; =&gt; #&lt;user$nasz_walidator [email protected]&gt;

Podpięcia

Obiekty typu Atom można wyposażać w podpięcia (ang. hooks) w postaci tzw. funkcji nadzorczych (ang. watch functions). Są one wywoływane, gdy zmienia się stan referencji (wyrażany wartością bieżącą), 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ę nadzorczą 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ę nadzorczą.

Funkcja nadzorcza powinna przyjmować 4 argumenty: klucz, obiekt typu Atom, a także poprzednią wartość oraz nową wartość bieżącą Atomu. 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 w ciele funkcji.

Możemy zarejestrować wiele funkcji nadzorczych, 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 wcześniej 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
(def atomek (atom 0)) (add-watch atomek :debug #(println (apply str (interpose &#34;, &#34; %&amp;)))) (swap! atomek inc) ; &gt;&gt; :debug, [email protected], 0, 1 (swap! atomek inc) ; &gt;&gt; :debug, [email protected], 1, 2 (swap! atomek inc) ; &gt;&gt; :debug, [email protected], 2, 3

Usuwanie obserwatorów, remove-watch

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

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

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
(def atomek (atom 0)) (defn reporter [&amp; args] (println (first args))) (add-watch atomek :debug reporter) (add-watch atomek :inna reporter) (swap! atomek inc) ; &gt;&gt; :debug ; &gt;&gt; :inna (remove-watch atomek :inna) (swap! atomek inc) ; &gt;&gt; :debug

Przykłady zastosowań

Globalne tożsamości

Korzystając ze zmiennych globalnych, jesteśmy w stanie tworzyć w przestrzeniach nazw globalne identyfikatory dla wyrażających zmieniające się stany 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 zasięgu nieograniczonym. Będziemy mieli więc dwa typy referencyjne: Var identyfikowany symbolem w przestrzeni nazw i Atom wskazywany wartością bieżącą tego pierwszego.

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
(defonce atom-licznika (atom -1)) (defn licznik ([x] (reset! atom-licznika (int x))) ([] (swap! atom-licznika inc))) (licznik) ; =&gt; 0 (licznik) ; =&gt; 1 (licznik) ; =&gt; 2 (licznik 100) ; =&gt; 100 (licznik) ; =&gt; 101 (licznik) ; =&gt; 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 korzystania z Atomów jest użycie 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
(defonce licznik (let [a (atom -1)] #(swap! a inc))) (licznik) ;=&gt; 0 (licznik) ;=&gt; 1 (licznik) ;=&gt; 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 formy wywołania funkcji, która uruchomi podprogram realizujący operację zwiększenia o jeden wartości bieżącej utworzonego Atomu.

Spróbujmy podobnej implementacji licznika, lecz zrealizowanej z użyciem funkcji generującej obiekt typu Atom o ustalonej wartości początkowej:

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
(defn utwórz-licznik [wartość] (let [a (atom (dec wartość))] #(swap! a inc))) (defonce licznik (utwórz-licznik 0)) (licznik) ; =&gt; 0 (licznik) ; =&gt; 1 (licznik) ; =&gt; 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 spamiętywania, możemy skorzystać z Atomów, aby bezpiecznie synchronizować zmiany współdzielonych 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"
(defn ! ([n] (! n 1)) ([n acc] (if (zero? n) acc (recur (dec n) (*&#39; acc n))))) (defn spamiętaj [f] (let [a (atom {})] (fn [&amp; 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)) ; &gt;&gt; &#34;Elapsed time: 260.910553 msecs&#34; (time (do (! 8000) nil)) ; &gt;&gt; &#34;Elapsed time: 0.085696 msecs&#34; (time (do (! 7999) nil)) ; &gt;&gt; &#34;Elapsed time: 168.098467 msecs&#34;

Zamiast definiować funkcję spamiętaj możemy też posłużyć się wspomnianą, wbudowaną funkcją memoize, która też 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 rekurencyjne operacje mnożenia dla przeliczanego już wcześniej ciągu rezultatów (od 1 do 7999) będą wykonywane 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
24
(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 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           ; zapamiętaj rezultat
                cur-idx new-acc)
         (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"
(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 (&lt;= n mem-cnt) ; czy zapamiętano? (nth @mem (dec n)) ; · tak: zwróć zapamiętany rezultat (f n ; · nie: zacznij od 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 (*&#39; acc cur) ; nowy rezultat cur-idx (dec cur)] ; bieżący indeks wektora podręcznego (swap! mem assoc ; zapamiętaj rezultat cur-idx new-acc) (if (= n cur) ; warunek zakończenia new-acc ; · przypadek bazowy (recur n new-cur new-acc))))))) ; · przypadek rekursywny (time (do (! 8000) nil)) ; &gt;&gt; &#34;Elapsed time: 180.090641 msecs&#34; (time (do (! 8001) nil)) ; &gt;&gt; &#34;Elapsed time: 0.108044 msecs&#34; (time (do (! 7999) nil)) ; &gt;&gt; &#34;Elapsed time: 0.185428 msecs&#34; (time (do (! 7999) nil)) ; &gt;&gt; &#34;Elapsed time: 0.048888 msecs&#34;

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.

Korzystamy tu z funkcji wieloczłonowej, czyli takiej, 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"
(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 (&lt; 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 (*&#39; (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)) ; &gt;&gt; &#34;Elapsed time: 154.966845 msecs&#34; (time (do (! 8001) nil)) ; &gt;&gt; &#34;Elapsed time: 0.104064 msecs&#34; (time (do (! 7999) nil)) ; &gt;&gt; &#34;Elapsed time: 0.092260 msecs&#34; (time (do (! 7999) nil)) ; &gt;&gt; &#34;Elapsed time: 0.064882 msecs&#34;
Jesteś w sekcji .
Tematyka:

Taksonomie: