Jednoduchost programovacího jazyka
Na konferenci EuroPython mě nejvíc obohatily dvě přednášky Raymonda Hettingera týkající se vnitřností Pythonu.
Kontejnery
V přednášce Core Python Containers jsem se dozvěděl, jakým způsobem jsou implementovány složené datové struktury v Pythonu:
list
Seznamy jsou v Pythonu implementovány jako pole ukazatelů pevné délky. Když se do seznamu přidá prvek, tak se toto pole přealokuje. Protože je přealokování paměti drahá operace, tak se při přidání prvku rovnou zabere o něco víc místa. Konkrétně na 0, 4, 8, 16, 25, 35, 46, … prvků (pro velké hodnoty maximálně 12,5 % navíc). Tím se amortizovaná složitost přidání jednoho prvku dostane na O(1), tedy konstantní čas. Odebírání prvku z konce seznamu je rychlá operace, protože k realokaci dojde až při uvolnění poloviny místa. Navíc i v tomto případě se paměť pouze označí jako uvolněná, takže nedojde ke kopírování. Přidávání a odebírání prvků jinam než na konec seznamu je naopak drahá operace, protože ke kopírování ukazatelů dojde vždy. Pokud je velikost seznamu předem známa (např. proto, že se jedná o výsledek volání funkce range), tak se alokuje přesná velikost, což šetří paměť.
deque
Jedná se o strukturu s podobnými vlastnostmi jako list, která navíc dovoluje rychlé přidávání a odebírání prvku na začátku seznamu.
set
Množiny jsou v Pythonu realizovány pomocí hash-tabulky, která se inicializuje na 8 prvků. Pokud je tato tabulka ze 2/3 zaplněna (takže častěji dochází ke kolizím), tak se její velikost zčtyřnásobí, díky čemuž se vyhledání prvku v množině povede průměrně na 1,5 pokusu. Průměrná rychlost přidání záznamu je stejně jako u seznamů O(1). Porovnání dvou prvků v množině je také rychlá operace – jejich hodnota se porovnává pouze v případě, kdy neukazují na stejné místo v paměti a mají stejný hash. Python navíc ručí za to, že se hash nebude počítat opakovaně (v tabulce je uložen spolu s prvkem). Při odebrání záznamů z množiny nedochází ke zmenšení tabulky – ta se případně zmenší až při dalším přidání prvku.
dict
Slovník je implementován stejně jako množina, jen ke každému prvku přidává ještě hodnotu.
Deskriptory
Přednáška Descriptor Tutorial pojednávala o deskriptorech. Deskriptor v Pythonu je objekt, který definuje metody __get__, __set__ nebo __delete__. Tyto metody se zavolají v okamžiku, kdy pomocí tečky přistoupíme k vlastnosti objektu, která obsahuje deskriptor.
class Desc(object):
def __get__(self, obj, objtype):
return obj.x+10
class A(object):
def __init__(self, x):
self.x = x
plus_ten = Desc()
>>> a = A(5)
>>> a.x
5
>>> a.plus_ten
15
Při přístupu k vlastnosti přes a.__dict__['plus_ten'] se deskriptor nezavolá. Příčina je ta, že a.plus_ten se ve skutečnosti vyhodnotí jako object.__getattribute__(a, 'plus_ten'). Metoda __getattribute__ zkontroluje, zda je prvek deskriptorem – pokud ano, tak zavolá deskriptor, jinak vrátí samotnou hodnotu. Její chování se dá nicméně také předefinovat.
Srovnání s PHP
V PHP existuje místo seznamu, množiny a slovníku jediná datová struktura – asociativní pole. Záleží jenom na tom, jak ho použiji: array($val), array($key => true) nebo array($key => $val). Seznam implementovaný jako pole ukazatelů je jistě rychlejší než hash-tabulka použitá u asociativních polí, vtip je ale v tom, že řádově probíhají operace ve stejném čase – O(1). Na to PHP sází a jazyk je díky tomu jednodušší jak na naučení, tak na pochopení.
Obdobná situace je i u přetěžování – v PHP je možné definovat metody __get, __set a podobné, pomocí kterých lze přístup k vlastnostem objektu přizpůsobit. V Pythonu to jde udělat na dvou úrovních – buď metodou __getattribute__ nebo pomocí deskriptorů. Definice a použití deskriptoru může být pohodlnější než definice přetěžovací funkce, PHP jde ale opět cestou jednoduchosti – místo dvou stupňů abstrakce nabízí jen jeden a je tedy opět jednodušší na naučení i pochopení.
Důsledek je ten, že Python nám v těchto dvou oblastech dává širší vyjadřovací možnosti, musíme jim ale správně rozumět.
Diskuze