Knihovna pro stromy v C

[Jan Kasprzak]

	Zdravim,

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

Delsi verze:

Mam na vstupu nejaku cisla (24-bitova nebo mozna 32-bitova, rikejme jim klice),
potrebuju ty klice nacist a vratit ke kazdemu z nich pocet vyskytu ve vstupu,
nejlepe setrideny podle toho klice (ale asi je to jedno). Jednotlive
vstupy maji rekneme 100 - 1_000_000 polozek, pricemz jeste by se dalo vyuzit,
ze ten vstup obsahuje klice v usecich radove stovek klicu, kde klice
v ramci toho useku jsou vzestupne setridene.

No a ted je otazka, jak toto v C naprogramovat. Pro 24 bitu v zasade
staci mit pole delky 2^24, na zacatku naplnit nulami, pak pricitat
jednicky podle vstupu a na konci jednim pruchodem vypsat ty nenulove.
Bohuzel i tohle mi v profileru vylezlo nahoru jako nejvic narocne,
takze se to snazim zoptimalizovat (a zaroven umoznit i 32-bitove klice,
kde pole velikosti 2^32 * sizeof(int) uz se mi do pameti nevejde).

Podstatne taky muze byt, ze z datove struktury se nikdy nebudou rusit
jednotlive klice - vzdy az po vypoctu cela struktura.

Dalsi podstatne muze byt vyhledavani - tady vzdycky pujde o to, ze kdyz
uz neco neuspesne vyhledam, tak vzdycky na to misto chci tento nenalezeny
klic vlozit jako novy.

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

A posledni problem je - kdyz uz stromy, tak jakou implementaci? Libilo by se
mi neco co by umelo mit sva data zapouzdrena do uzivatelskych dat
(neco jako seznamy v kernelu Linuxu - struct list_head a container_of())
abych nemusel na kazdy uzel zvlast malloc()ovat 24 bitu na klic a nejakych
16 nebo 32 bitu na pocet vyskytu, a vedle by se mi jeste malloc()ovala
data pro rezii stromu.

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

-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 /.          **