Konstantni slovnik v C (Judy nebo neco jineho?)

[Jan Kasprzak]

	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

-- 
| 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/ |
Please don't top post and in particular don't attach entire digests to your
mail or we'll all soon be using bittorrent to read the list.     --Alan Cox