Knihovna pro stromy v C

[Jan Kasprzak]

Martin `MJ' Mares wrote:
: 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.

	Tak u asymptotickych slozitosti samozrejme, ale praveze
bych rekl, ze stromy nebudou mit prils velkou hloubku (zvlaste B-stromy)
zatimco hashtabulka by budto musela byt nafukovaci (coz je IMHO zlo)
nebo prilis velka (pak by ale byl drahy pruchod pres vsechny sloty
pri zaverecnem vypisu vysledku). Koneckoncu staticke pole velikosti 2^24
je vlastne jistym zpusobem hashovaci tabulka :-)

: 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).

	Tak tohle nevim - tech hodnot prave muze byt velmi ruzne mnozstvi
- casto kolem stovky, ale casto taky k tomu milionu (to je asi horni hranice).
Prave proto mi stromy prijdou docela vhodne, ze se rozumne chovaji jak
pro male tak pro velke vstupy.

	Ale je pravda, ze _nejaka_ forma trideni by mohla zohlednit fakt,
ze vstup se sklada z nekolika posloupnosti, ktere jsou uvnitr rostouci.
Ale totez by (nejspis bez vetsiho efektu na rychlost) vlastne mohl udelat
i strom - ze bych dalsi prvek (v pripade ze by byl "rostouci") nehledal
znovu od korene stromu, ale od mista kde jsem skoncil naposledy.

: > 	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 :-)

	No, aspon se podivam jaky to ma interface. Zatim jsem zjistil
toto (README):

See doc/using-libs for description of the libraries.

(kde doc/using-libs neexistuje).

-Y.

-- 
| Jan "Yenya" Kasprzak  <kas at {fi.muni.cz - work | yenya.net - private}> |
| GPG: ID 1024/D3498839      Fingerprint 0D99A7FB206605D7 8B35FCDE05B18A5E |
| http://www.fi.muni.cz/~kas/    Journal: http://www.fi.muni.cz/~kas/blog/ |
**         Those who fail to understand communication protocols,          **
**         are doomed to repeat them over port 80.    -- from /.          **