Když jsem se učil programovat, seznamy v jazyce Python mi připadaly naprosto kouzelné. Představoval jsem si, že jsou implementovány nějakou magickou datovou strukturou, která je zčásti spojovým seznamem a zčásti polem a která je dokonalá pro všechno.

Jak jsem rostl jako inženýr, došlo mi, že to není pravděpodobné. Odhadoval jsem (správně), že spíše než nějaká magická implementace je to prostě podpořeno měnitelným polem. Rozhodl jsem se přečíst si kód a zjistit to.

Jednou z příjemných věcí na CPythonu je čitelná implementace. Ačkoli příslušný soubor má přes 2000 řádků jazyka C, jedná se převážně o algoritmus třídění a kotelní šablonu, aby byly funkce volatelné z kódu Pythonu.1 Základní operace se seznamy jsou krátké a přímočaré.

Tady je několik zajímavých věcí, které jsem při čtení implementace našel. Níže uvedené úryvky kódu pocházejí ze zdrojového kódu CPythonu s mnou přidanými vysvětlujícími komentáři.

Změna velikosti seznamu

Pokud připojujete k seznamu v Pythonu a podkladové pole není dostatečně velké, musí se podkladové pole rozšířit. Pokud k tomu dojde, zvětší se zálohovací pole přibližně o 12 %. Osobně jsem předpokládal, že tento růstový faktor je mnohem větší. V Javě se ArrayList při expanzi zvětší o 50 %2 a v Ruby se Array zvětší o 100 %.3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

odkaz na realokační kód CPythonu

Provedl jsem několik výkonnostních experimentů – zdá se, že předalokování polí pomocí konstrukcí jako *500 nepřináší žádný znatelný rozdíl. V mém nevědeckém benchmarku 100milionového vkládání do seznamu byl Python 3 mnohem pomalejší než Python 2, který byl mnohem pomalejší než Ruby, nicméně k určení vlivu (pokud vůbec nějakého) růstového faktoru na výkon vkládání je potřeba mnohem více výzkumu.

Vkládání na začátek seznamu

Vkládání na začátek seznamu trvá lineární čas – to není vzhledem ke zbytku implementace až tak překvapivé, ale je dobré vědět, že some_list.insert(0,value) je málokdy dobrý nápad. Uživatel Redditu mi připomněl Deques, které vyměňují vkládání a odebírání z obou konců za indexování v konstantním čase.

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;

odkaz na kód vkládání v CPythonu

Vytváření řezů seznamu

Vytvoření řezu seznamu např. some_listje také lineární časová operace v závislosti na velikosti plátku, takže opět žádná magie. Mohli byste si představit optimalizaci pomocí nějaké sémantiky copy-on-write, ale kód CPythonu dává přednost jednoduchosti:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}

odkaz na kód slice CPythonu

Přiřazení slice

Můžete přiřadit slice! Mezi profesionálními vývojáři Pythonu je to jistě všeobecně známé, ale já jsem se s tím za několik let programování v Pythonu nikdy nesetkal, zjistil jsem to, až když jsem v kódu narazil na funkci list_ass_slice(...). Pozor však na velké seznamy – je třeba zkopírovat všechny položky odstraněné z původního seznamu, což krátkodobě zdvojnásobí spotřebu paměti.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Třídění

Pole v Pythonu se třídí pomocí algoritmu známého jako “timsort”. Je to divoce komplikované a podrobně popsané ve vedlejším dokumentu ve stromu zdrojů. Zhruba jde o to, že sestavuje delší a delší řady sekvenčních položek a slučuje je. Na rozdíl od běžného slučovacího třídění začíná hledáním úseků seznamu, které jsou již seřazeny (runs v kódu). To mu umožňuje využít vstupní data, která jsou již částečně setříděná. zajímavá zajímavost: Pro třídění malých polí (nebo malých úseků většího pole) do 64 prvků4 používá timsort “binární třídění”. Jedná se v podstatě o vkládací třídění, ale k vložení prvku na správné místo se používá binární vyhledávání. Je to vlastně algoritmus s rychlostí O(n^2)! Zajímavý příklad vítězství reálného výkonu nad složitostí algoritmu v praxi. link

Přehlédl jsem něco skvělého na seznamech v CPythonu? Dejte mi vědět v komentářích.

Děkuji Leah Alpert za poskytnutí návrhů k tomuto příspěvku.

Chcete dostávat e-maily o nových příspěvcích na blogu?

Píšu zhruba jednou za několik týdnů o tématech, jako jsou databáze, vnitřnosti jazyků a algoritmy a v poslední době také hluboké učení. chcete mě zaměstnat? Jsem k dispozici pro angažmá od 1 týdne do několika měsíců. Najměte si mě!