Knihovna pro stromy v C

Dalibor Straka dast na panelnet.cz
Úterý Září 11 16:08:17 CEST 2007


Ahoj,

On Tue, Sep 11, 2007 at 01:58:43PM +0200, Jan Kasprzak wrote:
> 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.
> 
Mam docela peknou libavl, kterou jsem delal jako zapoctak ;-). Odladena
a rychla. Otazka jake operace budou nejcastejsi? Todle je idealni na
jedno postaveni a pak uz jen a jen hledat ;-).

> 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).
> 
A coz udelat hash. S tabuli 2^24 (8MB) budete mit malo kolizi, pripadne
si to muzete zprofilovat pro velikosti 2^20 az 2^28. Klidne za pivo
naprogramuju.

> 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.
> 
Rozumne stromy maji v uzlu pointer na uzivatelska data, nekdy i metodu
pro porovnani klicu a klic samotny. Urcite by pointer na uzivatelska
data sel premluvit na counter <g>.

-- Dalibor Straka



Další informace o konferenci Linux