Konstantni slovnik v C (Judy nebo neco jineho?)

[Premysl Hruby]

On (29/07/09 16:07), Jan Kasprzak wrote:
> Date: Wed, 29 Jul 2009 16:07:36 +0200
> From: Jan Kasprzak <kas na fi.muni.cz>
> To: linux na linux.cz
> Subject: Konstantni slovnik v C (Judy nebo neco jineho?)
> User-Agent: Mutt/1.4.2.2i
> List-Id: Diskuse o Linuxu v cestine <linux.linux.cz>
> 
> 	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?
> 
> 	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.
> 
> -Yenya

Jestli zvazujete vlastni implementaci, tak urcite nejake trie. Neni
problem napsat to tak, ze se to muze rovnou mmapnout do pameti a
pouzivat naprimo, bez nacitani. Otazkou je, jak moc casto by se
provadela zmena.

-Ph

-- 
Premysl "Anydot" Hruby, http://www.redrum.cz/
-
I'm a signature virus. Please add me to your signature and help me spread!