Knihovna pro stromy v C

[Martin `MJ' Mares]

Ahoj!

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

Ja mel na mysli nafukovaci hashovaci tabulku -- pokud je nafukovani
navrzene rozumne a jeste lepe pokud se pocatecni velikost odhadne podle
velikosti souboru, nafukovani stoji malicko.

B-stromy navrzene tak, aby se kazdy vrchol vesel do jednoho radku cache,
by ale take mohly dopadnout docela hezky (jen si nemyslim, ze takovehle
optimalizace nejaka existujici B-stromova knihovna dela). Do 64 bytu
se vejde vrchol stupne 7 (pripadne pokud je to list, muze rovnou
obsahovat 16 klicu), takze pri optimalnim zaplneni pro 2^24 hodnot
bude mit strom hloubku 9.

To by v obecnem pripade bylo vyrazne horsi nez hashovaci tabulka,
ale pokud Tvuj vstup obsahuje podobne hodnoty u sebe, muze to dopadnout
hodne dobre. Ale to, jak uz jsi sam zpozoroval, asi dopadne i daleko
primitvnejsi struktura.

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

Pardon, to byl hodne rychly snapshot. V -pre2 (prave uploadnuto)
to uz je opraveno.

				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
Ctrl and Alt keys stuck -- press Del to continue.