Pyrsistent: persistentní datové struktury v Pythonu

Obsah

1. Pyrsistent: persistentní datové struktury v Pythonu

2. Neměnnost (immutability) datových struktur

3. Persistence datových struktur a sdílení struktury (structural sharing)

4. Instalace knihovny pyrsistent

5. Od standardních seznamů a n-tic k vektorům

6. Interní implementace vektorů

7. Základní operace s vektory

8. Persistence kontejneru

9. Persistence kontejneru vs. neměnnost hodnot v něm uložených

10. Přístup k prvkům vektorů

11. Slicing

12. Persistentní mapy a množiny

13. Persistentní množiny

14. Konstrukce persistentních množin

15. Operace add a remove

16. Množinové operace

17. Test na existenci prvku v množině

18. Obsah druhé části článku

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Pyrsistent: persistentní datové struktury v Pythonu

V dnešním článku se seznámíme s jednou implementací persistentních datových struktur určenou pro použití v programovacím jazyku Python. Tato implementace je nabízena knihovnou pojmenovanou příznačně pyrsistent. Autoři této knihovny se přitom inspirovali programovacím jazykem Clojure, jenž je do značné míry postaven právě na persistentních datových strukturách a taktéž na neměnných hodnotách (což ovšem nejsou zcela totožné pojmy). V knihovně pyrsistent nalezneme zejména tuto pětici datových struktur neboli kontejnerů:

1. pvector – persistentní vektor, obdoba Pythonovského seznamu
2. pset – persistentní množina
3. pmap – persistentní mapa (asociativní pole)
4. plist – persistentní seznam (interně dosti odlišný od vektorů)
5. pdeque – persistentní obousměrná fronta

To však není vše, protože v knihovně pyrsistent nalezneme i další zajímavosti – precord, pclass atd., kterým se budeme věnovat jindy.

2. Neměnnost (immutability) datových struktur

Všech pět typů datových struktur (seznamů, vektorů, množin, map a front) má několik důležitých společných vlastností. Základní vlastností společnou všem pěti typům datových struktur je jejich neměnnost (immutability). To znamená, že již ve chvíli, kdy je některá datová struktura vytvořena, je po celou další dobu její existence v běžícím programu určen její obsah, tj. hodnoty všech prvků struktury – ovšem termín hodnota je zde chápán ve smyslu programovacího jazyka Python. Na první pohled to sice možná může vypadat zvláštně, ale i s takto se chovajícími strukturami je možné v reálným programech pracovat a to dokonce velmi efektivním způsobem (navíc se i zjednodušuje testování aplikace). Ostatně i v samotném Pythonu jsou některé hodnoty a objekty neměnné. Pravděpodobně nejviditelnějším příkladem jsou řetězce a samozřejmě taktéž všechny hodnoty primitivního datového typu (číslo, pravdivostní hodnota, None…).

3. Persistence datových struktur a sdílení struktury (structural sharing)

Kromě (ne zcela na 100% dodržené) neměnnosti (immutability) je další společnou vlastností výše zmíněných datových struktur i podpora pro znovupoužití již jednou alokovaných bloků paměti při „modifikaci“ těchto struktur. Ve skutečnosti víme, že datové struktury jsou persistentní, takže do nich například nelze přidávat ani z nich ubírat prvky. To nám však nezabraňuje vytvořit novou strukturu s přidaným, vymazaným či změněným prvkem – a to většinou bez nutnosti klonování původních dat. Většina standardních operací poskytovaných knihovnou pyrsistent se totiž snaží o to, aby jednou vytvořené sekvence (dejme tomu pro jednoduchost seznam) mohly být znovupoužity i v případě, že je vytvořen nový seznam, který v sobě obsahuje i seznam starší. Ten stále existuje a mohou na něj existovat reference používané například i v jiných paralelně běžících workerech či ve vláknech – což nám nijak nevadí ani nás to nijak neomezuje, protože tato vlákna (či korutiny) nemohou (až na výjimky popsané dále) obsah struktury modifikovat.

Vzhledem k tomu, že se obsah starého seznamu nemůže změnit (seznam je neměnitelný), může například nějaká funkce jednoduše k seznamu přidat nový první prvek (head) s tím, že tento prvek ukazuje na původní seznam – jinými slovy není nutné, alespoň v tomto případě, vytvářet kopii (ať již plytkou či hlubokou) původního seznamu, což přispívá k tomu, že mnohé operace nad persistentními strukturami jsou ve skutečnosti velmi rychlé, i když by se podle jejich popisu mohlo zdát, že jejich implementace vyžaduje provedení časově složitých operací. Je pouze důležité si zvolit správnou datovou strukturu, což se v praxi týká rozhodování mezi použitím seznamů, vektorů či množin (asi nejvíce přehlížená struktura vůbec).

4. Instalace knihovny pyrsistent

Knihovna pyrsistent je nabízena přes PyPi a navíc nevyžaduje žádné (tranzitivní) závislosti, takže její instalace by měla být jednoduchá a přímočará. Knihovnu nainstalujeme pro aktuálně přihlášeného uživatele následujícím způsobem:

$ pip3 install --user pyrsistent
 
Collecting pyrsistent
  Downloading pyrsistent-0.18.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (119 kB)
     |████████████████████████████████| 119 kB 2.1 MB/s
Installing collected packages: pyrsistent
Successfully installed pyrsistent-0.18.1

V kontextu „moderních“ frameworků se jedná o relativně malou knihovnu uloženou v několika souborech, o čemž se můžeme snadno přesvědčit:

$ ls -l /home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent
 
total 332
-rw-rw-r-- 1 ptisnovs ptisnovs 18372 Jun 27 15:14 _checked_types.py
-rw-rw-r-- 1 ptisnovs ptisnovs 11963 Jun 27 15:14 _field_common.py
-rw-rw-r-- 1 ptisnovs ptisnovs  3232 Jun 27 15:14 _helpers.py
-rw-rw-r-- 1 ptisnovs ptisnovs  3534 Jun 27 15:14 _immutable.py
-rw-rw-r-- 1 ptisnovs ptisnovs  1479 Jun 27 15:14 __init__.py
-rw-rw-r-- 1 ptisnovs ptisnovs  7188 Jun 27 15:14 __init__.pyi
-rw-rw-r-- 1 ptisnovs ptisnovs  6730 Jun 27 15:14 _pbag.py
-rw-rw-r-- 1 ptisnovs ptisnovs  9702 Jun 27 15:14 _pclass.py
-rw-rw-r-- 1 ptisnovs ptisnovs 12203 Jun 27 15:14 _pdeque.py
-rw-rw-r-- 1 ptisnovs ptisnovs  8293 Jun 27 15:14 _plist.py
-rw-rw-r-- 1 ptisnovs ptisnovs 14702 Jun 27 15:14 _pmap.py
-rw-rw-r-- 1 ptisnovs ptisnovs  7032 Jun 27 15:14 _precord.py
-rw-rw-r-- 1 ptisnovs ptisnovs  5693 Jun 27 15:14 _pset.py
-rw-rw-r-- 1 ptisnovs ptisnovs 22694 Jun 27 15:14 _pvector.py
drwxrwxr-x 2 ptisnovs ptisnovs  4096 Jun 27 15:14 __pycache__
-rw-rw-r-- 1 ptisnovs ptisnovs     0 Jun 27 15:14 py.typed
-rw-rw-r-- 1 ptisnovs ptisnovs  3428 Jun 27 15:14 _toolz.py
-rw-rw-r-- 1 ptisnovs ptisnovs  3800 Jun 27 15:14 _transformations.py
-rw-rw-r-- 1 ptisnovs ptisnovs  1767 Jun 27 15:14 typing.py
-rw-rw-r-- 1 ptisnovs ptisnovs 10409 Jun 27 15:14 typing.pyi

Její celková velikost nepřesahuje 1MB:

$ du -h /home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent
 
296K    /home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/__pycache__
628K    /home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent

Kontrola, zda je možné knihovnu pyrsistent naimportovat:

$ python3
 
Python 3.8.10 (default, Mar 15 2022, 12:22:08)
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import pyrsistent
>>> help(pyrsistent)

5. Od standardních seznamů a n-tic k vektorům

Nejprve si zopakujme základní informace o standardních datových strukturách Pythonu – konkrétně o n-ticích a seznamech. N-tice je vlastně jediným skutečně persistentním a současně i neměnným kontejnerem, protože po její konstrukci je již možné n-tice pouze spojovat (bez sdílení struktury) popř. získávat z n-tice jednotlivé prvky:

t1 = (1, 2, 3)
t2 = t1 + (4, )
 
print(t1)
print(t2)

Naproti tomu seznamy persistentní nejsou, protože do nich je možné přidávat nové prvky popř. prvky mazat (pomocí del):

list1 = [1, "foo", (1, 2, 3), None]
print(list1)
print(type(list1))
 
list1.append("Five!")
print(list1)
print(type(list1))

Prvky seznamů jsou taktéž obecně měnitelné (zde konkrétně poslední – pátý – prvek seznamu):

l = []
 
list1 = [1, "foo", (1, 2, 3), l]
print(list1)
print(type(list1))
 
l.append(1)
print(list1)
print(type(list1))
 
l.append(2)
print(list1)
print(type(list1))
 
l = []
print(list1)
print(type(list1))

A měnitelnost seznamů vede i k takovým „paradoxům“, že seznam může obsahovat sám sebe, což musí být interně řešeno specializovaným kódem:

list1 = [1, 2, 3]
print(list1)
print(type(list1))
 
list1.append(list1)
print(list1)
print(type(list1))

6. Interní implementace vektorů

V programovacím jazyku Python je možné na mnoha místech standardní seznamy nahradit za vektory, protože práce s vektory může být více efektivní, například ve vícevláknových programech. Vektor můžeme považovat za jednorozměrné pole hodnot libovolných typů, takže by se mohlo zdát, že složitost přístupu k jeho prvkům bude konstantní O(N). Ve skutečnosti jsou však vektory interně implementovány poněkud složitějším (a velmi zajímavým) způsobem a to především z toho důvodu, aby bylo snadné k vektorům připojovat další prvky – tak vznikne nový vektor, ovšem původní vektor musí samozřejmě zůstat zachovaný (structural sharing). Z tohoto důvodu se v knihovně pyrsistent (ale i v Clojure a v některých dalších moderních programovacích jazycích) používají pro implementaci vektorů takzvané RRB-Stromy (RRB-Trees, Relaxed Radix Balanced Trees). V pyrsistent jsou použity (vyvážené) RRB-stromy, které mají v každém listu uloženo jednorozměrné pole o délce 32 prvků. V případě, že se pracuje s kratším vektorem, je pro jeho uložení použit strom pouze s jedním listem a tudíž je vektor skutečně reprezentován jednorozměrným polem (ve skutečnosti se vedle vlastního stromu používá ještě pomocné pole tail, pro jednoduchost však jeho roli v tomto textu poněkud zanedbáme).

U delších vektorů se v 32prvkovém poli uloženém v kořenu stromu nenachází přímo prvky vektoru, ale reference na další listy, z nichž každý opět obsahuje 32prvkové pole. To znamená, že vektor s až 1024 prvky může být uložen ve stromu o výšce 1, ve stromu o výšce 2 je celkový (možný) počet prvků vektoru roven 32768 (1024 listů á 32 prvků) atd. Operace vrácení n-tého prvku má tedy složitost O(log₃₂N), což sice není konstantní složitost O(1), ale pro vektory běžných délek můžeme tuto složitost taktéž považovat prakticky za konstantní. Předností vektorů je tedy rychlejší přístup k jeho prvkům, ale nesmíme zapomenout ani na paměťové nároky – vektory interně potřebují mnohem méně referencí, než je tomu u lineárně vázaných seznamů, tudíž i paměťové nároky budou nižší, a to zejména na 64bitových systémech.

7. Základní operace s vektory

Vektor se vytváří s využitím konstruktoru nazvaného jednoduše v. V dalším příkladu je vektor vytvořen, následně je zobrazen jeho obsah a pro jistotu je vypsán i jeho typ:

from pyrsistent import v
 
vector1 = v(1, 2, 3)
print(vector1)
print(type(vector1))

Po spuštění tohoto demonstračního příkladu dostaneme na standardním výstupu dva řádky:

pvector([1, 2, 3])
<class 'pvectorc.PVector'>

Jak je v Pythonu zvykem, nemusí být všechny prvky vektoru stejného typu (ovšem na rozdíl od NumPy, kde je naopak typ všech prvků vektoru/matice stejný). Toto chování je zachováno i u vektorů, což je patrné i z následujícího demonstračního příkladu:

from pyrsistent import v
 
vector1 = v(1, "foo", (1, 2, 3), None)
print(vector1)
print(type(vector1))

Podívejme se nyní na získané výsledky, které skutečně ukazují vektor s prvky různého typu:

pvector([1, 'foo', (1, 2, 3), None])
<class 'pvectorc.PVector'>

8. Persistence kontejneru vs. neměnnost hodnot v něm uložených

Víme již, že samotný vektor (tj. jeden typ kontejneru) je persistentní, tj. po konstrukci už do něj není možné prvky ani přidávat ani odebírat. Operace „přidání nového prvku“ sice existuje a je realizována metodou nazvanou append, ovšem výsledkem bude nový vektor, přičemž vektor původní bude nezměněn. Využívá se zde již výše zmíněné sdílení struktury (structural sharing), takže se ve skutečnosti nemusí obsah původního vektoru kopírovat do vektoru nového:

from pyrsistent import v
 
vector1 = v(1, "foo", (1, 2, 3), None)
print(vector1)
print(type(vector1))
 
vector2 = vector1.append("Five!")
print(vector1)
print(type(vector1))
 
print(vector2)
print(type(vector2))

Z výsledků je patrné, že původní vektor vector1 se skutečně nezměnil:

pvector([1, 'foo', (1, 2, 3), None])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), None])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), None, 'Five!'])
<class 'pvectorc.PVector'>

Nyní se pokusme do vektoru uložit seznam (zpočátku prázdný) a následně změnit původní proměnnou l takovým způsobem, aby obsahovala (resp. přesněji řečeno ukazovala) na nový seznam:

from pyrsistent import v
 
l = []
 
vector1 = v(1, "foo", (1, 2, 3), l)
print(vector1)
print(type(vector1))
 
l = [1, 2, 3]
print(vector1)
print(type(vector1))

V tomto případě zůstane vektor nezměněný, protože do něho není uložena přímo proměnná l, ale reference uložená v této proměnné (a původní reference se novým přiřazením nezmění):

pvector([1, 'foo', (1, 2, 3), []])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), []])
<class 'pvectorc.PVector'>

9. Persistence kontejneru vs. neměnnost hodnot v něm uložených

Z předchozí trojice demonstračních příkladů by se mohlo zdát, že vektory jsou nejenom persistentní, ale i neměnné (immutable) v původním slova smyslu – tj. že vektor je chápán jako jediná v čase neměnná hodnota. To však ve skutečnosti není pravda ve chvíli, kdy do vektoru uložíme měnitelný prvek. Hodnotu takového vektoru lze změnit nepřímo, a to právě modifikací tohoto prvku.

Vyzkoušejme si to na seznamu vloženého do vektoru, do něhož posléze přidáme nové prvky metodou append (ta se chová zcela odlišně, než je tomu u vektorů):

from pyrsistent import v
 
l = []
 
vector1 = v(1, "foo", (1, 2, 3), l)
print(vector1)
print(type(vector1))
 
l.append(1)
print(vector1)
print(type(vector1))
 
l.append(2)
print(vector1)
print(type(vector1))
 
l = []
print(vector1)
print(type(vector1))

Z výsledků je nyní patrné, že se obsah vektoru skutečně změnil:

pvector([1, 'foo', (1, 2, 3), []])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), [1]])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), [1, 2]])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), [1, 2]])
<class 'pvectorc.PVector'>

Totéž ovšem platí i pro další typickou měnitelnou datovou strukturu programovacího jazyka Python – pro mapy:

from pyrsistent import v
 
m = {}
 
vector1 = v(1, "foo", (1, 2, 3), m)
print(vector1)
print(type(vector1))
 
m["one"] = 1
print(vector1)
print(type(vector1))
 
m["two"] = 2
print(vector1)
print(type(vector1))
 
m = {"jedna": 1,
     "dva": 2}
print(vector1)
print(type(vector1))

S výsledky ukazujícími, že i mapa je potenciálně problematickým prvkem vektoru:

pvector([1, 'foo', (1, 2, 3), {}])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), {'one': 1}])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), {'one': 1, 'two': 2}])
<class 'pvectorc.PVector'>
pvector([1, 'foo', (1, 2, 3), {'one': 1, 'two': 2}])
<class 'pvectorc.PVector'>

10. Přístup k prvkům vektorů

K prvkům vektorů se přistupuje s využitím přetíženého operátoru []. Chování je přitom z pohledu uživatele totožné s chováním běžných seznamů nebo n-tic – prvky se indexují od nuly, nezáporné indexy se používají pro přístup k prvkům zleva (od začátku vektorů), zatímco indexy záporné lze využít pro přístup k prvkům zprava (tedy od konce vektorů):

from pyrsistent import v
 
vector1 = v(1, "foo", (1, 2, 3), None)
print(vector1)
print(type(vector1))
 
print(0, vector1[0])
print(3, vector1[3])
print(-1, vector1[-1])
print(-2, vector1[-2])

S výsledky:

pvector([1, 'foo', (1, 2, 3), None])
<class 'pvectorc.PVector'>
0 1
3 None
-1 None
-2 (1, 2, 3)

Časová složitost přístupu k prvku je „téměř konstantní“ – O(log₃₂N)

11. Slicing

Podle očekávání je podporován i slicing, tedy získání většího množství prvků vektoru současně:

from pyrsistent import v
 
vector1 = v(1, "foo", (1, 2, 3), None)
print(vector1)
print(type(vector1))
 
print(vector1[1:3])
print(vector1[1:])
print(vector1[:3])
print(vector1[:])

S výsledky:

pvector([1, 'foo', (1, 2, 3), None])
<class 'pvectorc.PVector'>
0 1
3 None
-1 None
-2 (1, 2, 3)

Použít lze i krok – rozdíl mezi indexy vybíraných prvků:

from pyrsistent import v
 
vector1 = v(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
print(vector1)
print(type(vector1))
 
print(vector1[3:7:2])
print(vector1[3::2])
print(vector1[:7:2])
print(vector1[::2])

Tentokrát s výsledky:

pvector([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
<class 'pvectorc.PVector'>
pvector([4, 6])
pvector([4, 6, 8, 10])
pvector([1, 3, 5, 7])
pvector([1, 3, 5, 7, 9])

12. Persistentní mapy a množiny

Nesmíme však zapomenout ani na zbylé strukturované datové typy – kontejnery. Jedná se především o mapy (maps) a množiny (sets). Především mapy jsou velmi důležité v mnoha aplikacích naprogramovaných v Pythonu, neboť se s jejich využitím mohou vytvářet struktury/záznamy (structs/records), hodnotové objekty atd. (primárně se ovšem pro tyto účely používají třídy, což s sebou přináší další problémy). Navíc jsou mapy zajímavé i z hlediska jejich implementace.

13. Persistentní množiny

Nejprve se budeme zabývat persistentními množinami – PSet. Interně se jedná o hierarchickou datovou strukturu používanou ve chvíli, kdy nás zajímají především hodnoty (a někdy jen pouhá existence) prvků a nikoli jejich vzájemné uspořádání. Prvky tedy nejsou přístupné přes svůj index, ovšem můžeme zjišťovat, zda prvek s danou hodnotou v množině existuje či nikoli. Podporovány jsou i základní množinové operace, přičemž výsledkem bude nová množina (stávající množiny jsou pochopitelně persistentní).

Mezi podporované operace patří:

1. Přidání prvku do nové množiny, která sdílí strukturu s množinou původní
2. Odebrání prvku z nové množiny, která sdílí strukturu s množinou původní
3. Všechny základní množinové operace: sjednocení, průnik, diference, symetrická diference
4. Test, zda množina obsahuje daný prvek
5. Test, zda je jedna množina podmnožinou jiné množiny
6. Získání hodnoty všech prvků uložených v množině

14. Konstrukce persistentních množin

Zatímco persistentní vektory se vytváří konstruktorem v, jsou persistentní množiny vytvářeny konstruktorem nazvaným jednoduše s, kterému se předají všechny prvky, které mají být do množiny vloženy:

from pyrsistent import s
 
set1 = s(1,2,3)
 
print(set1)
print(type(set1))

Po spuštění tohoto skriptu by se měla zobrazit množina se třemi prvky a současně i její typ (persistent._pset.PSet):

pset([1, 2, 3])
<class 'pyrsistent._pset.PSet'>

15. Operace add a remove

Persistentní množiny nabízí dvě metody add a remove určené pro „přidání“ a „odebrání“ prvků z množiny. Ovšem vzhledem k tomu, že množiny jsou persistentní, není původní množina modifikována. Namísto toho je vytvořena množina nová s přidaným/ubraným prvkem. Opět se zde do velké míry využívá sdílení interní struktury:

from pyrsistent import s
 
set1 = s(1,2,3)
set2 = set1.add(4)
 
print(set1)
print(type(set1))
 
print(set2)
print(type(set2))

Přidáním prvku není původní množina změněna:

pset([1, 2, 3])
<class 'pyrsistent._pset.PSet'>
pset([1, 2, 3, 4])
<class 'pyrsistent._pset.PSet'>

a:

from pyrsistent import s
 
set1 = s(1,2,3)
set2 = set1.remove(1)
 
print(set1)
print(type(set1))
 
print(set2)
print(type(set2))

Opět platí, že odebráním prvku není původní množina změněna:

pset([1, 2, 3])
<class 'pyrsistent._pset.PSet'>
pset([2, 3])
<class 'pyrsistent._pset.PSet'>

16. Množinové operace

Mezi základní množinové operace patří sjednocení (union), průnik (intersection), rozdíl množin (difference) a symetrická diference. Pro provedení prvních tří operací slouží přetížené operátory |, & a -, přičemž jejich výsledkem je vždy nová persistentní množina. U těchto operací však není zaručeno, že dochází ke sdílení struktury (structural sharing):

from pyrsistent import s
 
set1 = s(1,2,3)
set2 = s(2,3,4)
 
print(set1)
print(set2)
 
print("sjednoceni", set1 | set2)
print("prunik", set1 & set2)
print("rozdil", set1 - set2)
print("rozdil", set2 - set1)

Povšimněte si, že výsledkem množinových operací nad persistentními množinami je skutečně vždy nová persistentní množina:

pset([1, 2, 3])
pset([2, 3, 4])
sjednoceni pset([1, 2, 3, 4])
prunik pset([2, 3])
rozdil pset([1])
rozdil pset([4])

17. Test na existenci prvku v množině

Poslední množinovou operací, s níž se v dnešním článku setkáme, je test, zda je určitý prvek (hodnota) prvkem dané množiny či nikoli. Pro tento účel se používá přetížený operátor in, jehož časová složitost je v případě persistentních množin O(log₃₂N), tedy jak již víme „prakticky konstantní“.

V demonstračním příkladu postupně testujeme, jestli množina {1, 2, 3} obsahuje prvky 0, 1, 2, 3 a 4:

from pyrsistent import s
 
set1 = s(1,2,3)
 
for i in range(0, 5):
    print(i, i in set1)

Výsledky zobrazené na standardním výstupu:

0 False
1 True
2 True
3 True
4 False

18. Obsah druhé části článku

Ve druhé části článku o knihovně pyrsistent se zaměříme na popis zbývajících persistentních datových struktur, které tato knihovna vývojářům nabízí. Jednat se bude zejména o persistentní mapy, ale i o persistentní obousměrné fronty. To však není ani zdaleka vše, protože v knihovně pyrsistent nalezneme i podporu pro persistentní objekty popř. pro takzvané záznamy (records).

19. Repositář s demonstračními příklady

Zdrojové kódy všech prozatím popsaných demonstračních příkladů určených pro programovací jazyk Python 3 a knihovnu pyrsistent byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/most-popular-python-libs. V případě, že nebudete chtít klonovat celý repositář (ten je ovšem stále velmi malý, dnes má velikost zhruba několik desítek kilobajtů), můžete namísto toho použít odkazy na jednotlivé příklady, které naleznete v následující tabulce:

20. Odkazy na Internetu

1. Persistent data structure
   https://en.wikipedia.org/wi­ki/Persistent_data_structu­re
2. Collections (Python)
   https://docs.python.org/3/li­brary/collections.abc.html
3. Immutable object
   https://en.wikipedia.org/wi­ki/Immutable_object
4. pyrsistent na PyPi
   https://pypi.org/project/pyrsistent/
5. pyrsistent na GitHubu
   https://github.com/tobgu/pyrsistent
6. Dokumentace knihovny pyrsistent
   https://pyrsistent.readthe­docs.io/en/latest/index.html
7. pyrthon na GitHubu
   https://github.com/tobgu/pyrthon/
8. Mori na GitHubu
   https://github.com/swannodette/mori
9. Mori: popis API (dokumentace)
   http://swannodette.github.io/mori/
10. Mori: Benchmarking
    https://github.com/swanno­dette/mori/wiki/Benchmarking
11. Functional data structures in JavaScript with Mori
    http://sitr.us/2013/11/04/functional-data-structures.html
12. Immutable.js
    https://facebook.github.io/immutable-js/
13. Understanding Clojure's Persistent Vectors, pt. 1
    http://hypirion.com/musin­gs/understanding-persistent-vector-pt-1
14. Hash array mapped trie (Wikipedia)
    https://en.wikipedia.org/wi­ki/Hash_array_mapped_trie
15. Java theory and practice: To mutate or not to mutate?
    http://www.ibm.com/develo­perworks/java/library/j-jtp02183/index.html
16. Efficient persistent (immutable) data structures
    https://persistent.codeplex.com/
17. Clojure (Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
18. Clojure (Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure