Konstantni slovnik v C (Judy nebo neco jineho?)

[Dalibor Straka]

On Wed, Jul 29, 2009 at 04:07:36PM +0200, Jan Kasprzak wrote:
> 	Zdravim,
> 
> mam sadu dvojic <retezec, cislo> setridenou podle retezce lexikograficky,
> a cilem je toto ulozit na disk tak, aby se to dalo efektivne
> nacist do pameti (idealne mmap()), a pak rychle provadet operace
> "vrat cislo k zadanemu retezci".
> 
> 	Co byste pouzili za strukturu?

Zdravim,

nas ve skole ucili, ze v takovem pripade lze udelat perfektni hashovani,
kdy bude slozitost v nejhorsim pripade O(1).

> 	Co jsem tak nasel, tak vetsina clanku se zabyva datovymi strukturami,
> ve kterych je dulezite i umet efektivne vkladat a mazat (cili nejsou
> konstantni; obvykle to vede na hashovaci tabulky nebo B-stromy).
> Mam predstavu, ze pridanim omezeni na konstantnost te struktury by se
> neco dalo usetrit. Vyhodou by bylo neco co neni hash (mozna v tom nekdy
> budu chtit vyhledavat i podle prefixu/rozsahu). Cili ne treba Bernsteinovo
> cdb. A taky pokud mozno neco co by bylo cache-friendly.
> 
> 	Ja jsem prozatim data ulozil do souboru jako retezec\0slovo
> a v pameti to mam v Judy (JudySL). Coz jednak stoji nejaky cas
> pri nacitani (asi mi to tak moc nevadi), ale jednak to generuje
> nesdilitelnou pamet, a zabira vic nez bych chtel (pro 200 KB velky
> soubor mi po nacteni a pak uvolneni z pameti JSLFA() vratilo, ze Judy
> pole zabiralo asi 580 KB). Cast z toho urcite je, ze Judy ma jako hodnotu
> 64-bitove cislo, zatimco u me staci 32 bitu.

-- Dalibor Straka