Obsah
1. Pyrsistent: persistentní datové struktury v Pythonu (dokončení)
4. Klíče mapy s typem rozdílným od řetězce
6. Operace spojení dvou či více map
7. Konverze mezi mapami a dalšími typy kontejnerů
9. Operace „freeze“ pro konstrukci vektorů
10. Operace „freeze“ pro konstrukci množin a map
11. Persistentní obousměrná fronta – deque
13. Přidání prvku do fronty zleva či zprava
14. Odstranění nejlevějšího či nejpravějšího prvku z fronty
16. Persistentní záznam – mapa s pevně zadanými klíči
17. Kontrola typu a/nebo hodnoty prvků v persistentních datových strukturách
18. Vektor s kontrolou typu a/nebo hodnoty ukládaných prvků
19. Repositář s demonstračními příklady
1. Pyrsistent: persistentní datové struktury v Pythonu (dokončení)
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 (maps), ale i o persistentní obousměrné fronty (deque) či o kontejner typu bag. To však není ani zdaleka vše, protože v knihovně pyrsistent nalezneme i podporu pro persistentní objekty (což je v Pythonu poměrně nový koncept), popř. pro takzvané záznamy (records). Nezapomeneme ani na podporu pro kolekce, u nichž je testována jejich konzistence a dokonce i typů, popř. hodnot prvků, které jsou v takových kolekcích uloženy. A popíšeme si i velmi užitečnou funkci freeze, která slouží pro konverzi mezi nepersistentními kontejnery Pythonu (vektory, množiny a mapy) do persistentní podoby (opačnou operaci provádí funkce nazvaná thaf).
2. Persistentní mapy
V úvodním článku o pythonovské knihovně Pyrsistent byly popsány dvě základní persistentní datové struktury, které se nazývají vektory a množiny. Na vektory i na množiny se můžeme dívat jako na pole s neměnitelnou strukturou (prvky nelze přidávat ani odebírat – tyto operace vedou k vytvoření nové struktury), ovšem zatímco u vektorů je zaručeno pořadí prvků a možnost výběru prvků na základě jejich celočíselných indexů, u množin se operace omezují na test existence prvku, popř. na přečtení hodnoty prvku. Ovšem s množinami jako celkem lze navíc provádět standardní množinové operace – sjednocení, průnik, diferenci, symetrickou diferenci a v neposlední řadě i test, jestli je nějaká množina podmnožinou množiny jiné. Množiny jsou tedy v mnoha ohledech velmi užitečné datové struktury, které jsou však mnohdy – poněkud neprávem – při vývoji přehlíženy.
Nyní se však zaměřme na další velmi užitečnou datovou strukturu neboli kontejner. Jedná se o mapy (maps), které jsou známé taktéž pod jménem asociativní pole. Prvky uložené v mapě jsou přístupné přes klíč a nikoli přes celočíselný index, což znamená, že se jedná o univerzálnější a interně i komplikovanější datovou strukturu. A vzhledem k tomu, že se v knihovně Pyrsistent pracuje s persistentními datovými strukturami, jsou i mapy persistentní, tj. do mapy není možné přidávat ani z nich odebírat prvky. Mapy po své konstrukci sice zdánlivě nabízí možnost s prvky mapy tímto způsobem manipulovat, ovšem každá manipulace vede k vytvoření (a vrácení) nové mapy. Využívá se zde již minule zmíněné sdílení interní struktury (structural sharing), což znamená, že nově vytvořená mapa ve skutečnosti sdílí prakticky celou vnitřní strukturu s mapou původní (až na nově vytvořené, smazané či modifikované prvky). Přístup k prvkům přes klíče je velmi rychlý – časová složitost přístupu je rovna časové složitosti přístupu u vektorů a množin, tedy O(log32n), kde n je počet prvků uložených v mapě.
3. Konstrukce mapy
Pro konstrukci mapy se používá konstruktor nazvaný jednoduše m, podobně jako pro vektor existuje konstruktor pojmenovaný v a pro množiny konstruktor se jménem s. Tomuto konstruktoru lze předat libovolné množství pojmenovaných parametrů, přičemž jméno parametru bude klíčem prvku v nově vytvářené mapě a hodnota parametru hodnotou prvku v mapě. Na mapy je navíc mj. možné aplikovat standardní funkci len a samozřejmě i zjistit její typ další standardní funkcí type:
from pyrsistent import m map1 = m(first=1, second=2, third=3) print(map1) print(type(map1)) print(len(map1))
Výsledkem bude persistentní mapa obsahující tři prvky:
pmap({'first': 1, 'third': 3, 'second': 2})
<class 'pyrsistent._pmap.PMap'>
3
4. Klíče mapy s typem rozdílným od řetězce
V předchozím demonstračním příkladu jsme vlastně měli „štěstí“, protože jsme potřebovali vytvořit mapu, jejíž prvky mají klíče typu řetězec (string). Jak se však může mapa zkonstruovat ve chvíli, kdy například potřebujeme namísto řetězců použít n-tice nebo například celá čísla? Problém spočívá v tom, že jména parametrů musí být platnými identifikátory Pythonu. Následující příklad tedy není zapsán korektně:
from pyrsistent import m map1 = m(1="first", 2="second", 3="third") print(map1) print(type(map1)) print(len(map1))
Jedná se o syntaktickou chybu, na kterou nás upozorní interpret Pythonu:
File "map02.py", line 3
map1 = m(1="first", 2="second", 3="third")
^
SyntaxError: expression cannot contain assignment, perhaps you meant "=="?
Řešení spočívá v použití konstruktoru pmap, jenž umožňuje vytvořit persistentní mapu z jiného typu kontejneru, typicky ze slovníku (dictionary):
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second", 3:"third"})
print(map1)
print(type(map1))
print(len(map1))
Tento skript je již bez chyby spustitelný:
pmap({1: 'first', 2: 'second', 3: 'third'})
<class 'pyrsistent._pmap.PMap'>
3
5. „Modifikace“ mapy
Do persistentních map nelze (z prostého důvodu jejich persistence) přidávat nové prvky ani z nich prvky odstraňovat. Přesto knihovna Pyrsistent programátorům při manipulacích s mapami nabízí podobné operace. Tyto operace však vrací novou mapu s přidaným/ubraným prvkem; původní mapa zůstane nezměněna. Tyto nové mapy sdílejí interní strukturu s původní mapou, takže i zdánlivě složité operace přidání/ubrání prvku jsou z časového i paměťového hlediska poměrně efektivní.
Přidání nového prvku či změnu existujícího prvku zajišťuje operace pojmenovaná set, odstranění prvku pak operace nazvaná remove. Výsledkem je vždy nová mapa; původní mapa zůstane, jak již víme, beze změn:
from pyrsistent import m
map1 = m(first=1, second=2, third=3)
print("Original map")
print(map1)
map2 = map1.set("fourth", 4)
print("\nAfter set")
print(map1)
print(map2)
map3 = map1.remove("first")
print("\nAfter remove")
print(map1)
print(map2)
print(map3)
Výsledky ukazují, že se původní mapa skutečně nezmění:
Original map
pmap({'second': 2, 'third': 3, 'first': 1})
After set
pmap({'second': 2, 'third': 3, 'first': 1})
pmap({'second': 2, 'fourth': 4, 'third': 3, 'first': 1})
After remove
pmap({'second': 2, 'third': 3, 'first': 1})
pmap({'second': 2, 'fourth': 4, 'third': 3, 'first': 1})
pmap({'second': 2, 'third': 3})
Ve skutečnosti je odstranění prvku z persistentní mapy realizováno dvěma operacemi nazvanými discard a remove. Ty se od sebe odlišují svým chováním ve chvíli, kdy prvek s daným klíčem neexistuje. Metoda discard v tomto případě vrátí původní mapu zatímco metoda remove vyhodí výjimku typu KeyError. Chování obou zmíněných operací si můžeme velmi snadno ověřit následujícím skriptem:
from pyrsistent import m
map1 = m(first=1, second=2, third=3)
print("Original map")
print(map1)
map2 = map1.set("fourth", 4)
print("\nAfter set")
print(map1)
print(map2)
map3 = map1.discard("first")
print("\nAfter remove")
print(map1)
print(map2)
print(map3)
map1.discard("nonexistentA")
map1.remove("nonexistentB")
Zatímco metoda discard proběhne bez chyby, v případě metody remove je vyhozena výjimka typu KeyError:
Original map
pmap({'first': 1, 'second': 2, 'third': 3})
After set
pmap({'first': 1, 'second': 2, 'third': 3})
pmap({'first': 1, 'second': 2, 'third': 3, 'fourth': 4})
After remove
pmap({'first': 1, 'second': 2, 'third': 3})
pmap({'first': 1, 'second': 2, 'third': 3, 'fourth': 4})
pmap({'second': 2, 'third': 3})
Traceback (most recent call last):
File "maps05.py", line 19, in <module>
map1.remove("nonexistentB")
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_pmap.py", line 192, in remove
return self.evolver().remove(key).persistent()
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_pmap.py", line 366, in remove
raise KeyError('{0}'.format(key))
KeyError: 'nonexistentB'
6. Operace spojení dvou či více map
Pro spojení dvou či více map slouží přetížený operátor +. Nejprve se podívejme na spojení dvou map v případě, že klíče prvků v obou mapách jsou unikátní a nedochází tedy k žádnému „překryvu“:
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second"})
map2 = pmap({3:"third", 4:"fourth"})
print(map1)
print(map2)
map3 = map1 + map2
print(map3)
Výsledkem spojení je nová mapa; mapy původní zůstanou beze změny:
pmap({1: 'first', 2: 'second'})
pmap({4: 'fourth', 3: 'third'})
pmap({4: 'fourth', 1: 'first', 2: 'second', 3: 'third'})
Alternativně je možné namísto přetíženého operátoru + použít metodu update. Tentokrát se však podívejme, co se stane ve chvíli, kdy nějaký prvek v první mapě má stejný klíč, jako prvek v mapě druhé:
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second", 3:"third"})
map2 = pmap({3:"3rd", 4:"4th"})
print(map1)
print(map2)
map3 = map1.update(map2)
print(map3)
Z výsledku je patrné, že spojením „vyhrál“ prvek z druhé mapy:
pmap({1: 'first', 2: 'second', 3: 'third'})
pmap({4: '4th', 3: '3rd'})
pmap({1: 'first', 2: 'second', 3: '3rd', 4: '4th'})
Naprosto stejný výsledek získáme po spojení map operátorem +:
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second", 3:"third"})
map2 = pmap({3:"3rd", 4:"4th"})
print(map1)
print(map2)
map3 = map1 + map2
print(map3)
Výsledek:
pmap({1: 'first', 2: 'second', 3: 'third'})
pmap({4: '4th', 3: '3rd'})
pmap({1: 'first', 2: 'second', 3: '3rd', 4: '4th'})
7. Konverze mezi mapami a dalšími typy kontejnerů
Persistentní mapy programátorům nabízí metody items a values. První z těchto metod vrací persistentní vektor s klíči i hodnotami (což jsou dvojice), druhá metoda vrací taktéž persistentní vektor, tentokrát však s hodnotami prvků:
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second", 3:"third"})
vector1 = map1.items()
print("Items:")
print(vector1)
print(type(vector1))
vector2 = map1.values()
print("\nValues:")
print(vector2)
print(type(vector2))
Po spuštění tohoto příkladu je patrné, jak obě výše zmíněné metody pracují:
Items: pvector([(1, 'first'), (2, 'second'), (3, 'third')]) <class 'pvectorc.PVector'> Values: pvector(['first', 'second', 'third']) <class 'pvectorc.PVector'>
Ještě snadnější je převod všech hodnot na běžný nepersistentní seznam, k čemuž slouží standardní funkce list:
from pyrsistent import pmap
map1 = pmap({1:"first", 2:"second", 3:"third"})
list1 = list(map1)
print("As list:")
print(list1)
print(type(list1))
Výsledky:
As list: [1, 2, 3] <class 'list'>
8. Kontejner typu „Bag“
V knihovně Pyrsistent nalezneme i persistentní kontejner, který je nazvaný Bag neboli multimnožina (multiset, mset). Jedná se o mix mezi vektory a množinami – bag ukládá prvky obecně bez zaručení pořadí (tedy stejně, jako je tomu u množin), ovšem umožňuje uložení většího množství kopií prvků se stejnou hodnotou (stejně, jako je tomu u vektorů). Pro konstrukci tohoto persistentního kontejneru slouží funkce/konstruktor nazvaný pbag, kterému se předává jiný kontejner (seznam, n-tice, persistentní vektor) s hodnotami prvků. Navíc jsou podporovány i operace add a remove, které vrací nový bag (tedy multimnožinu), jež podle očekávání sdílí svoji interní strukturu s množinou původní:
from pyrsistent import pbag
bag1 = pbag(["foo", "bar", "baz"])
print(bag1)
print(type(bag1))
bag2 = bag1.add("bar")
print(bag2)
print(type(bag2))
bag3 = bag2.remove("baz")
print(bag3)
print(type(bag3))
Po spuštění tohoto skriptu se vypíše obsah i typ všech tří postupně vytvořených multimnožin:
pbag(['baz', 'bar', 'foo']) <class 'pyrsistent._pbag.PBag'> pbag(['baz', 'bar', 'bar', 'foo']) <class 'pyrsistent._pbag.PBag'> pbag(['bar', 'bar', 'foo']) <class 'pyrsistent._pbag.PBag'>
Multimnožiny je možné spojit i s využitím přetíženého operátoru +, což je ukázáno v následujícím skriptu. Současně je zde ukázána možnost převodu multimnožiny na běžný pythonovský seznam:
from pyrsistent import pbag bag1 = pbag(["foo", "bar", "baz"]) print(bag1) l = list(bag1) print(l) bag2 = bag1 + pbag(["baz", "alpha", "omega"]) print(bag2)
S výsledkem:
pbag(['bar', 'foo', 'baz']) ['bar', 'foo', 'baz'] pbag(['bar', 'alpha', 'foo', 'omega', 'baz', 'baz'])
9. Operace „freeze“ pro konstrukci vektorů
Užitečná je i operace freeze použitá při konstrukci vektorů. V prvním příkladu vytvoříme persistentní vektor ze seznamu, jehož prvky jsou různého typu:
from pyrsistent import freeze
vector1 = freeze([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))
Výsledky ukazují, že se nově vytvořený vektor skutečně chová jako persistentní vektor:
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'>
Druhý příklad je odlišný, neboť ukazuje, že i seznam uvnitř seznamu (zvýrazněná část kódu) se převede na persistentní vektor:
from pyrsistent import freeze
vector1 = freeze([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))
Onen zmíněný vektor ve vektoru je ve výsledcích rovněž zvýrazněn:
pvector([1, 'foo', pvector([1, 2, 3]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, 2, 3]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, 2, 3]), None, 'Five!']) <class 'pvectorc.PVector'>
Vektor jako prvek převáděného seznamu ovšem můžeme specifikovat i explicitně:
from pyrsistent import freeze, v
vector1 = freeze([1, "foo", v(1, [2, 3]), None])
print(vector1)
print(type(vector1))
vector2 = vector1.append("Five!")
print(vector1)
print(type(vector1))
print(vector2)
print(type(vector2))
S výsledkem „vektor ve vektoru vektorů“:
pvector([1, 'foo', pvector([1, pvector([2, 3])]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, pvector([2, 3])]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, pvector([2, 3])]), None, 'Five!']) <class 'pvectorc.PVector'>
Tuto rekurzivní náhradu seznamů za persistentní vektory je možné v případě potřeby zakázat tím, že se funkci freeze předá nepovinný parametr se jménem strict a hodnotou False:
from pyrsistent import freeze, v
vector1 = freeze([1, "foo", v(1, [2, 3]), None], strict=False)
print(vector1)
print(type(vector1))
vector2 = vector1.append("Five!")
print(vector1)
print(type(vector1))
print(vector2)
print(type(vector2))
Výsledky nyní budou odlišné:
pvector([1, 'foo', pvector([1, [2, 3]]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, [2, 3]]), None]) <class 'pvectorc.PVector'> pvector([1, 'foo', pvector([1, [2, 3]]), None, 'Five!']) <class 'pvectorc.PVector'>
10. Operace „freeze“ pro konstrukci množin a map
Funkci freeze, kterou jsme si v souvislosti s vektory popsali v předchozí kapitole, lze použít i pro další dva typy kontejnerů Pythonu – konkrétně pro množiny a slovníky.
Nejprve se podívejme na konstrukci persistentní množiny z běžné (nepersistentní) Pythonovské množiny:
from pyrsistent import freeze
set1 = freeze({1,2,3})
print(set1)
print(type(set1))
print()
for i in range(0, 5):
print(i, i in set1)
S výsledkem:
pset([1, 2, 3]) <class 'pyrsistent._pset.PSet'> 0 False 1 True 2 True 3 True 4 False
Podobným způsobem můžeme sestrojit persistentní mapu z běžného Pythonovského slovníku, a to následovně:
from pyrsistent import freeze
map1 = freeze({1:"first", 2:"second", 3:"third"})
print(map1)
print(type(map1))
Výsledek získaný po spuštění bude vypadat takto:
pmap({1: 'first', 2: 'second', 3: 'third'})
<class 'pyrsistent._pmap.PMap'>
11. Persistentní obousměrná fronta – deque
Posledním „klasickým“ kontejnerem podporovaným v knihovně Pyrsistent, o němž se v dnešním článku zmíníme, je kontejner nazvaný deque, což je jedna z možných implementací obousměrné fronty (double ended queue). Jedná se tedy o kontejner, který podporuje operace připojení nového prvku k oběma koncům fronty, popř. naopak k získání (a odstranění) prvku z libovolného konce – jedná se ovšem pochopitelně o operace zachovávající persistenci a tedy vracející novou obousměrnou frontu s novým a/nebo odstraněným prvkem. Podporovány jsou ovšem i další dvě operace, které typicky u implementací obousměrných front nenajdeme. Jedná se o operaci určenou pro rotaci prvků uložených ve frontě a taktéž o operaci, která vede k otočení fronty, tj. ke změně pořadí všech prvků, které jsou ve frontě uloženy.
Frontu je možné zkonstruovat funkcí-konstruktorem nazvaným dq, kterému se předají všechny prvky, které se mají do obousměrné fronty uložit (v zadaném pořadí):
from pyrsistent import dq
deque = dq("foo", "bar", "baz")
print(deque)
print(type(deque))
S výsledkem:
pdeque(['foo', 'bar', 'baz']) <class 'pyrsistent._pdeque.PDeque'>
Alternativně je možné použít i konstruktor pojmenovaný pdeque, kterému se prvky předají v jediném parametru – kterým je typicky jiný kontejner, například klasický seznam:
from pyrsistent import pdeque deque = pdeque(["foo", "bar", "baz"]) print(deque) print(type(deque))
Výsledek je shodný s předchozím příkladem:
pdeque(['foo', 'bar', 'baz']) <class 'pyrsistent._pdeque.PDeque'>
Dtto pro n-tice:
from pyrsistent import pdeque
deque = pdeque(("foo", "bar", "baz"))
print(deque)
print(type(deque))
Opět dostaneme shodný výsledek:
pdeque(['foo', 'bar', 'baz']) <class 'pyrsistent._pdeque.PDeque'>
A persistentní frontu je možné zkonstruovat i z persistentního vektoru:
from pyrsistent import pdeque, v
vec = v("foo", "bar", "baz")
deque = pdeque(vec)
print(vec)
print(type(vec))
print()
print(deque)
print(type(deque))
Tento demonstrační příklad nejdříve vypíše obsah a typ persistentního vektoru a posléze i obsah a typ obousměrné fronty:
pvector(['foo', 'bar', 'baz']) <class 'pvectorc.PVector'> pdeque(['foo', 'bar', 'baz']) <class 'pyrsistent._pdeque.PDeque'>
12. Atributy left a right
V souvislosti s obousměrnými frontami je nutné nějakým způsobem označit, resp. pojmenovat oba konce fronty. V některých dokumentech nebo knihovnách se setkáme s označením „first“ a „last“, popř. „head“ a „tail“, což však může být matoucí. Namísto toho se v knihovně Pyrsistent setkáme s použitím slov „left“ a „right“, tj. jeden z konců fronty je „levý“ a druhý „pravý“.
K dispozici jsou i atributy se jmény left a right, které obsahují referencí na nejlevější nebo nejpravější prvek ve frontě (za předpokladu, že fronta obsahuje alespoň jeden prvek):
from pyrsistent import dq
deque = dq("foo", "bar", "baz")
print(deque)
print(type(deque))
print(deque.left)
print(deque.right)
Po spuštění tohoto skriptu se nejdříve vypíše celá fronta, následně její typ (což již známe) a nakonec hodnota jejích prvků na obou koncích – levém i pravém:
pdeque(['foo', 'bar', 'baz']) <class 'pyrsistent._pdeque.PDeque'> foo baz
13. Přidání prvku do fronty zleva či zprava
Pro přidání prvku do fronty zprava slouží metoda append (protože v jiných strukturách append přidává prvky na konec, tedy v naší kultuře doprava). Výsledkem je pochopitelně nová fronta:
from pyrsistent import pdeque, v
vec = v("foo")
deque1 = pdeque(vec)
print(deque1)
deque2 = deque1.append("bar")
print(deque2)
deque3 = deque2.append("baz")
print(deque3)
Tento skript vypíše tři fronty, které interně částečně sdílí svoji strukturu:
pdeque(['foo']) pdeque(['foo', 'bar']) pdeque(['foo', 'bar', 'baz'])
Pro přidání prvku na levý konec fronty je určena metoda pojmenovaná appendleft:
from pyrsistent import pdeque, v
vec = v("foo")
deque1 = pdeque(vec)
print(deque1)
deque2 = deque1.appendleft("bar")
print(deque2)
deque3 = deque2.appendleft("baz")
print(deque3)
Tři fronty, které postupně vzniknou, jsou odlišné od předchozího příkladu:
pdeque(['foo']) pdeque(['bar', 'foo']) pdeque(['baz', 'bar', 'foo'])
14. Odstranění nejlevějšího či nejpravějšího prvku z fronty
V předchozí kapitole jsme si ukázali, jak lze přidávat prvky do persistentní obousměrné fronty, tj. jak vznikne nová fronta s prvkem připojeným na její levý nebo pravý konec. Opakem této operace je odebrání prvku zleva nebo zprava. Tyto operace opět způsobí, že se vytvoří nová fronta, jejíž prvek na levém nebo pravém konci bude odstraněn. Neprovádí se však čtení hodnoty odstraňovaného prvku – k tomu slouží již výše zmíněné atributy left a right.
from pyrsistent import pdeque, v
vec = v("foo", "bar", "baz")
deque1 = pdeque(vec)
print(deque1)
deque2 = deque1.pop()
print(deque2)
deque3 = deque2.pop()
print(deque3)
Výsledky ukazují, jak se prvky skutečně odstraňují zprava (v nových frontách):
pdeque(['foo', 'bar', 'baz']) pdeque(['foo', 'bar']) pdeque(['foo'])
O odstranění prvků zleva se stará metoda pojmenovaná popleft:
from pyrsistent import pdeque, v
vec = v("foo", "bar", "baz")
deque1 = pdeque(vec)
print(deque1)
deque2 = deque1.popleft()
print(deque2)
deque3 = deque2.popleft()
print(deque3)
Povšimněte si rozdílů ve výsledcích oproti předchozímu skriptu:
pdeque(['foo', 'bar', 'baz']) pdeque(['bar', 'baz']) pdeque(['baz'])
15. Metody reverse a rotate
Poslední dvě metody, s nimiž se v souvislosti s persistentní obousměrnou frontou seznámíme, jsou metody vracející otočenou frontu a taktéž pro rotaci prvků ve frontě (jakoby se jednalo o kruhový buffer – ring buffer). Obě zmíněné metody vrací novou persistentní frontu a metodě rotate se navíc předává počet rotací prvků (ten může být i záporný):
from pyrsistent import pdeque, v
vec = v("foo", "bar", "baz")
deque1 = pdeque(vec)
deque2 = deque1.reverse()
print(deque2)
deque3 = deque1.rotate(1)
print(deque3)
Tento skript nejdříve vypíše obsah otočené fronty a následně obsah fronty, jejíž prvky jsou orotovány doprava o jeden prvek:
pdeque(['baz', 'bar', 'foo']) pdeque(['baz', 'foo', 'bar'])
16. Persistentní záznam – mapa s pevně zadanými klíči
Předposledním persistentním kontejnerem, s nímž se v dnešním článku seznámíme, je persistentní záznam, což je kontejner, který si můžeme představit jako persistentní mapu (se všemi metodami, které již známe), jejíž množina klíčů je pevně zadaná již v deklaraci. V následujícím demonstračním příkladu vytvoříme záznam, který může (ale nemusí!) obsahovat prvky s klíči „x“ a „y“, ovšem další klíče již nejsou povoleny:
from pyrsistent import PRecord, field
class XYRecord(PRecord):
x = field()
y = field()
record1 = XYRecord(x=1)
print(record1)
record2 = record1.set("y", 42)
print(record2)
record3 = record2.set("z", 0)
print(record3)
Při pokusu o použití klíče „z“ dojde k chybě – takové klíče nepodporujeme:
XYRecord(x=1)
XYRecord(y=42, x=1)
Traceback (most recent call last):
File "precord.py", line 14, in <module>
record3 = record2.set("z", 0)
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_precord.py", line 65, in set
return super(PRecord, self).set(args[0], args[1])
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_pmap.py", line 181, in set
return self.evolver().set(key, val).persistent()
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_precord.py", line 146, in set
raise AttributeError("'{0}' is not among the specified fields for {1}".format(key, self._destination_cls.__name__))
AttributeError: 'z' is not among the specified fields for XYRecord
17. Kontrola typu a/nebo hodnoty prvků v persistentních datových strukturách
Všechny typy persistentních kontejnerů, které jsme si až doposud popsali, umožňovaly uložení prvků jakýchkoli typů a hodnot. Toto chování ostatně vychází z filozofie Pythonu jakožto vysokoúrovňového dynamicky typovaného jazyka. Ovšem v některých situacích může být vhodné omezit možnosti kontejnerů – aby například umožňovaly uložení prvků určitého typu nebo dokonce prvků, jejichž hodnota splňuje nějakou programátorem zadanou podmínku – invariant. I tuto funkcionalitu knihovna Pyrsistent programátorům nabízí, protože ke každému již popsanému kontejneru existuje i jeho „checked“ (tedy kontrolovaná) varianta. Při použití kontrolované varianty kontejneru můžeme specifikovat jak povolené typy prvků, tak i (což je zajímavější) nějaké další kontrolované podmínky, například to, že prvky musí být kladné, musí se jednat o neprázdné řetězce, musí se jednat o datová razítka s časem ukazujícím pouze do budoucnosti (nebo naopak jen na poslední měsíc) atd.
18. Vektor s kontrolou typu a/nebo hodnoty ukládaných prvků
V dnešním posledním demonstračním příkladu je ukázáno, jak lze použít persistentní vektor, který může obsahovat hodnoty specifikovaného typu a současně odpovídající zadané podmínce. V příkladu je deklarována třída odpovídající persistentnímu vektoru pro celočíselné hodnoty, které současně musí být dělitelné dvěma. Následně se pokusíme o vytvoření dvou vektorů – prvního s prvky, které podmínku splňují a druhého, které podmínku naopak nesplňují (dva prvky jsou lichými čísly):
from pyrsistent import CheckedPVector
class Evens(CheckedPVector):
__type__ = (int,)
__invariant__ = lambda n: (n % 2 == 0, "Even")
vector1 = Evens([2, 4, 6])
print(vector1)
print(type(vector1))
vector2 = Evens([1, 2, 3])
print(vector2)
print(type(vector2))
Při spuštění skriptu bude první vektor bez problémů vytvořen zatímco při pokusu o konstrukci druhého vektoru dojde k vyhození výjimky typu InvariantException:
Evens([2, 4, 6])
<Class '__main__.Evens'>
Traceback (most recent call last):
File "checked_vector.py", line 12, in <module>
vector2 = Evens([1, 2, 3])
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_checked_types.py", line 292, in __new__
return CheckedPVector.Evolver(cls, python_pvector()).extend(initial).persistent()
File "/home/ptisnovs/.local/lib/python3.8/site-packages/pyrsistent/_checked_types.py", line 341, in persistent
raise InvariantException(error_codes=self._invariant_errors)
pyrsistent._checked_types.InvariantException: , invariant_errors=[Even, Even], missing_fields=[]
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
- Persistent data structure
https://en.wikipedia.org/wiki/Persistent_data_structure - Collections (Python)
https://docs.python.org/3/library/collections.abc.html - Immutable object
https://en.wikipedia.org/wiki/Immutable_object - pyrsistent na PyPi
https://pypi.org/project/pyrsistent/ - pyrsistent na GitHubu
https://github.com/tobgu/pyrsistent - Dokumentace knihovny pyrsistent
https://pyrsistent.readthedocs.io/en/latest/index.html - pyrthon na GitHubu
https://github.com/tobgu/pyrthon/ - Mori na GitHubu
https://github.com/swannodette/mori - Mori: popis API (dokumentace)
http://swannodette.github.io/mori/ - Mori: Benchmarking
https://github.com/swannodette/mori/wiki/Benchmarking - Functional data structures in JavaScript with Mori
http://sitr.us/2013/11/04/functional-data-structures.html - Immutable.js
https://facebook.github.io/immutable-js/ - Understanding Clojure's Persistent Vectors, pt. 1
http://hypirion.com/musings/understanding-persistent-vector-pt-1 - Hash array mapped trie (Wikipedia)
https://en.wikipedia.org/wiki/Hash_array_mapped_trie - Java theory and practice: To mutate or not to mutate?
http://www.ibm.com/developerworks/java/library/j-jtp02183/index.html - Efficient persistent (immutable) data structures
https://persistent.codeplex.com/ - Clojure (Wikipedia EN)
http://en.wikipedia.org/wiki/Clojure - Clojure (Wikipedia CS)
http://cs.wikipedia.org/wiki/Clojure
ČLÁNKY DO MAILU