Hlavní navigace

Pyrsistent: persistentní datové struktury v Pythonu (dokončení)

19. 7. 2022
Doba čtení: 25 minut

Sdílet

 Autor: Depositphotos
Dnes se zaměříme na popis zbývajících persistentních datových struktur, které knihovna vývojářům nabízí. Jedná se především o persistentní mapy a obousměrné fronty. Nalezneme zde i persistentní objekty, popř. takzvané záznamy.

Obsah

1. Pyrsistent: persistentní datové struktury v Pythonu (dokončení)

2. Persistentní mapy

3. Konstrukce mapy

4. Klíče mapy s typem rozdílným od řetězce

5. „Modifikace“ mapy

6. Operace spojení dvou či více map

7. Konverze mezi mapami a dalšími typy kontejnerů

8. Kontejner typu „Bag“

9. Operace „freeze“ pro konstrukci vektorů

10. Operace „freeze“ pro konstrukci množin a map

11. Persistentní obousměrná fronta – deque

12. Atributy left a right

13. Přidání prvku do fronty zleva či zprava

14. Odstranění nejlevějšího či nejpravějšího prvku z fronty

15. Metody reverse a rotate

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

20. Odkazy na Internetu

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'>
Poznámka: pokud by nám nezáleželo na pořadí prvků v mapě, mohla by metoda items vracet množinu.

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'>
Poznámka: jak metody items a values, tak i standardní funkce list vrací datovou strukturu, přes kterou lze snadno iterovat s využitím standardních syntaktických prostředků Pythonu.

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'>
Poznámka: povšimněte si, že multimnožiny mohou skutečně obsahovat vícenásobné kopie stejných prvků.

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'])
Poznámka: opět si povšimněte toho, že druhá multimnožina obsahuje větší množství prvků se stejnou hodnotou.

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.

Poznámka: obousměrnou frontu je možné pochopitelně použít i ve funkci zásobníku (stack), zde konkrétně persistentního zásobníku. Z tohoto důvodu v Pyrsistent nenalezneme přímo kontejner stack, resp. pstack.

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.

Poznámka: tyto kontroly jsou prováděny za běhu (runtime), nikoli při analýze a překladu skriptů do bajtkódu.

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):

MIFtip2

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:

# Demonstrační příklad Stručný popis příkladu Cesta
1 list01.py standardní datový typ seznam https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/list01.py
2 list02.py přidání prvků do seznamu https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/list02.py
3 list03.py měnitelné prvky seznamu https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/list03.py
4 list04.py rekurzivní seznam https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/list04.py
       
5 tuple01.py standardní neměnný typ n-tice https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/tuple01.py
       
6 vectors01.py konstrukce vektoru se třemi prvky stejného typu https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors01.py
7 vectors02.py konstrukce vektoru se čtyřmi prvky rozdílného typu https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors02.py
8 vectors03.py metoda append vytvářející nový vektor https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors03.py
9 vectors04.py neměnná hodnota – reference na seznam https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors04.py
10 vectors05.py proměnná hodnota – vlastní obsah seznamu https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors05.py
11 vectors06.py proměnná hodnota – obsah mapy https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors06.py
12 vectors07.py přístup k prvkům vektoru https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors07.py
13 vectors08.py slicing https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors08.py
14 vectors09.py slicing se specifikací kroku https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/vectors09.py
       
15 sets01.py konstrukce persistentní množiny https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/sets01.py
16 sets02.py persistentní množina a operace add https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/sets02.py
17 sets03.py persistentní množina a operace remove https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/sets03.py
18 sets04.py množinové operace https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/sets04.py
19 sets05.py test na existenci prvku v množině https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/sets05.py
       
20 maps01.py konstrukce persistentní mapy konstruktorem m https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps01.py
21 maps02.py pokus o konstrukci mapy, jejímiž klíči jsou celá čísla https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps02.py
22 maps03.py konstrukce mapy konstruktorem pmap https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps03.py
23 maps04.py persistentní mapy a operace set a remove https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps04.py
24 maps05.py rozdíl mezi operacemi remove a discard https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps05.py
25 maps06.py spojení dvou persistentních map operátorem + https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps06.py
26 maps07.py spojení dvou persistentních map obsahujících prvky se stejnými klíči https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps07.py
27 maps08.py spojení dvou persistentních map obsahujících prvky se stejnými klíči https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps08.py
28 maps09.py získání prvků, popř. jen jejich hodnot z množiny https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps09.py
29 maps10.py převod prvků na seznam https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/maps10.py
       
30 bag01.py multimnožina https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/bag01.py
31 bag02.py multimnožina https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/bag02.py
       
32 freeze_maps.py operace „freeze“ provedená se slovníkem https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_maps.py
33 freeze_sets.py operace „freeze“ provedená s množinou https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_sets.py
34 freeze_vectors01.py operace „freeze“ provedená se seznamem https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_vectors01.py
35 freeze_vectors02.py operace „freeze“ provedená se seznamem https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_vectors02.py
36 freeze_vectors03.py operace „freeze“ provedená se seznamem https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_vectors03.py
37 freeze_vectors04.py operace „freeze“ provedená se seznamem https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/freeze_vectors04.py
       
38 deque01.py konstrukce obousměrné fronty konstruktorem dq https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque01.py
39 deque02.py konstrukce obousměrné fronty konstruktorem pdeque (seznam) https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque02.py
40 deque03.py konstrukce obousměrné fronty konstruktorem pdeque (n-tice) https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque03.py
41 deque04.py konstrukce obousměrné fronty konstruktorem pdeque (vektor) https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque04.py
42 deque05.py atributy left a right https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque05.py
43 deque06.py přidání prvku do fronty metodou append https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque06.py
44 deque07.py přidání prvku do fronty metodou appendleft https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque07.py
45 deque08.py odstranění prvku z fronty metodou pop https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque08.py
46 deque09.py odstranění prvku z fronty metodou popleft https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque09.py
47 deque10.py metody reverse a rotate https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/deque10.py
       
48 precord.py persistentní záznam – mapa s pevně zadanými klíči https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsistent/precord.py
       
49 checked_vector.py vektor s kontrolou typu a/nebo hodnoty ukládaných prvků https://github.com/tisnik/most-popular-python-libs/blob/master/pyrsisten­t/checked_vector.py

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

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.