24. července 2011

Nekonečná lenost sekvencí

Velmi silnou (a zajímavou) zbraní Clojure jsou sekvence (neboli seq, čti [si:k]). Sekvence je logický seznam, který implementuje jednoduché rozhraní ISeq a umožňuje sekvenční přístup k datům - a to nejenom k těm, u kterých bychom to čekali (kolekce = seznamy, mapy, apod.), ale i k těm, kde potřebné sekvenční implementační detaily chybí, např. stromové struktury (XML, adresáře), databázové result sety  či textové soubory (buď jeden velký řetězec, nebo vektor řádků), I/O streamy, anebo obyčejné znakové řetězce (String).

Věc, na kterou bych se chtěl podívat je jednak lenost (laziness) a jednak (možná) nekonečnost (infiniteness) sekvencí. Laziness je známá např. z databázového/ORM světa, kdy se lazy typicky dotahují data v 1:N vztazích. Výhodou lazy sekvencí je:

  • odsunutí výpočtu, který možná nebude potřeba,
  • možnost práce s velkými daty, která se nevejdou do paměti,
  • odsunutí I/O operací, až budou opravdu potřeba.

Co se týká nekonečnosti, tam je to jasné - některé sekvence prostě jsou nekonečné: přirozená čísla, prvočísla, Fibonacciho posloupnost, atd.

Ukázkový příklad jsem převzal z knížky Programming Clojure a sice protože mi přišel tak dobrý, že se mi zdálo zbytečné vymýšlet příklad vlastní (ach ta lenost :-). Zajímá vás, jak vypadá milionté prvočíslo?
(use '[clojure.contrib.lazy-seqs :only (primes)])
; nil
(def ordinals-and-primes
  (map vector (iterate inc 1) primes))
; #'user/ordinals-and-primes
(first (drop 999999 ordinals-and-primes))
; [1000000 15485863]

Pro vysvětlení, Var primes obsahuje lazy sekvenci prvočísel, Var ordinals-and-primes obsahuje dvojice hodnot [pořadové-číslo prvočíslo]. Poslední příkaz (first (drop ... provede samotný výpočet sekvence prvočísel, zahodí prvních 999.999 hodnot a vrátí (pomocí first) tu 1.000.000tou. Vypočítat milion prvočísel chvilku trvá, takže třetí příkaz chvilku poběží. Spočítanou sekvenci už má pak ale Clojure nacachovanou, takže hodnoty pod milion nebo lehce nad vrací okamžitě.

Žádné komentáře:

Okomentovat