Category Archives: DS

Od pohledu dobrý, aneb jak najít skoro stejné obrázky mezi dvěma miliony souborů za méně než deset minut

A tenhle znáte: „Proč je Pentium rychlejší než 486? 486 počítá, ale Pentium jen odhaduje.“ Přestože jde o nejapný vtip o chybě v prvních Pentiích z počítačového pravěku, má v sobě zrnko pravdy: Odhad může být mnohem rychlejší než přesný výpočet. Odhad, pokud chci, aby byl k něčemu … Continue reading 

Posted in Algo, DS | Leave a comment

Persistentní datové struktury

Funkcionální programování je horké téma posledních let. Co to je, proč je to dobré, co to přináší a proč o tom všichni mluví právě teď? Odpovědi na tyto otázky jsou následující: Programování s referenčně transparentními funkcemi6, zlepšuje to možnosti kompozice, porozumění programům, … Continue reading 

Posted in DS, Funkcionální programování | 2 Comments

Kolize hashů pro mírně pokročilé

Hash tabulka je jedna ze základních datových struktur, byla vynalezena roku 1953 a všichni, kdo programování viděli aspoň z rychlíku, ji velice dobře znají. Hash tabulky (někdy také hashmapy nebo slovníky/dicti­onary) umí vyhledat, přidat nebo smazat hodnotu asociovanou s určitým klíčem v konstantním čase. … Continue reading 

Posted in DS, Hashování, Java, PHP | 1 Comment

Střeva databází

Tenhle článek je mojí skromnou snahou si udělat pořádek v některých technikách a datových strukturách, které se používají uvnitř databází. Nejde o nijak kompletní nebo hluboký výčet, protože realita je vždycky mnohem komplikovanější a zdánlivé detaily (jako třeba konzistence) hrají vždycky větší … Continue reading 

Posted in DB, DS | Leave a comment

Jaccardovo tajemství – jak počítat podobnost množin pomalu, jak ji počítat rychle a jak při výpočtu podvádět

Jaccardův index podobnosti je jednoduchá funkce, která udává míru podobnosti mezi dvěma množinami. Je definována jako velikost průniku vydělená velikostí sjednocení dvou množin. J(A, B) = |A ∩ B| / |A ∪ B| Funkce je to jednoduchá. Otázka je, jak … Continue reading 

Posted in Algo, DS, Scala | 3 Comments