Knihovna pro stromy v C

[Martin `MJ' Mares]

Ahoj!

> Kratka verze dotazu: vite o nejake dobre knihovne pro implementaci
> stromu v C?

Ano, jednu takovou mame v libucw :-)

Viz treba http://mj.ucw.cz/tmp/holmes-libs-3.12-pre1.tar.gz, konkretne
lib/redblack.h (pripadne tam jsou take docela hezke hashovaci tabulky
v lib/hashtable.h).

> Podle me je hashovaci tabulka nepouzitelna - nevyuziva lokality dat
> a ruznych klicu je fakt hodne. Asi spis bude treba pouzit nejake
> stromy. Ale ted jake? Jedna moznost je red-black tree, druha asi
> B-stromy s velikosti uzlu optimalizovanou na velikost cache line (64 bajtu)?

Ja myslim, ze hashovaci tabulka by fungovala daleko lepe nez stromy --
u takhle velkych datovych struktur uz je totiz nejdulezitejsi meritko
frekvence cache-missu a slusne navrzena hashovaci tabulka bude mit
v prumeru konstantni pocet cache-missu na pristup, kdezto u stromu
bude logaritmicky.

Pokud je ruznych hodnot pomerne hodne, prekvapive dobre funguje setridit
si je radix-sortem (ten je opet velice pratelsky k cachim, pokud se zvoli
spravny pocet prihradek -- zrovna ted si s tim hraji a v nove verzi libucw
bude dabelsky rychly multi-threaded radix-sort).

> 	Co byste doporucili (krome: zkus si sam naimplementovat vice moznosti
> a zprofiluj si to :-) ?

Doporucil bych vyzkouset jak stromy, tak hashovaci tabulky z libucw
a zprofilovat si to :-)

				Have a nice fortnight
-- 
Martin `MJ' Mares                          <mj na ucw.cz>   http://mj.ucw.cz/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
May the Source be with you...