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 Lispu 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, synchronicznym i niezależ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.
atom
|
|
(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).
Atom
|
|
(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)
.
deref
|
|
(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żeli
zwracany przez nie obiekt jest typem referencyjnym, 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
.
@
|
|
(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…)
.
swap!
|
|
(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ść)
.
reset!
|
|
(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ść)
.
compare-and-set!
|
|
(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!
i 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
, to walidator zostanie
odłączony od podanego obiektu typu Atom
.
Funkcja set-validator!
zwraca wartość nil
, jeżeli udało się ustawić
walidator.
set-validator!
|
|
(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
, gdy
walidatora nie ustawiono.
Użycie:
(get-validator atom)
.
get-validator
|
|
(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)
.
add-watch
|
|
(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)
.
remove-watch
|
|
(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:
|
|
(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
):
Atom
|
|
(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 formy
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
:
|
|
(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.
|
|
(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:
|
|
(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ą:
|
|
(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"