Browsed by
Category: Snippety

Datová struktura trie (prefixový strom) v Pythonu

Datová struktura trie (prefixový strom) v Pythonu

Trie neboli prefixový strom je datová struktura sloužící k uložení asociativního pole. K jeho prvkům se přistupuje pomocí klíče, který je ve většině případů tvořen textovým řetězcem. Díky své vnitřní struktuře umožňuje trie rychlé vyhledání s lineární časovou složitostí. Trie bývá často využívána pro uložení slovníků, kde se kromě rychlosti vyhledání využívá ještě relativně příznivých nároků na paměť v případě, že se ve slovníku nachází velké množství slov se stejným prefixem.
Oproti hashovací tabulce má trie výhodu v tom, že odpadá potřeba hledání optimální hashovací funkce a současně v případě rozdílných klíčů není třeba řešit kolize. Trie je ideální pro případy, kdy je třeba nad určitou množinou slov hledat všechna slova začínající určitým prefixem.

Konkurentní server v C++

Konkurentní server v C++

Konkurentní server dokáže obsloužit více klientů zároveň. V mém kódu je tohoto požadavku dosaženo použitím systémového volání fork, které slouží k vytvoření nového procesu. Stejné funkčnosti se dá docílit i pomocí jiných metod, mimo jiné použitím vláken, či funkcí select() a poll() z knihovny pro práci se sockety.