2007年05月29日
Tx: Succinct Trie Data Structure
Tx: Succinct Trie Data Structure
数千万件の要素(URL)のmapを作りたかったので、Txを試してみた。C++のstd::mapは元データの数倍ものメモリを食ったのに対して、Txは元データの40.5%程のメモリしか必要としなかった。元データの量は大体数Gだったので、十分メモリに保持できてしまう。
検索時間はstd::map等に比べて落ちはするようだが、10msで終わるなら十分すぎるほどなので採用決定。
もっと馬鹿でかいデータを入れたりしても落ちたり、データが壊れたりする事も無かったので安心して使えそう。他のアプリケーションにも色々適用できそうなので、書いてみた。
1億件とかそれ以上になると、ディスクを併用しないと無理臭いなぁ。となると流石に処理速度のほうが気になる。そうなって来ると、STXXL: Standard Template Library for Extra Large Data Setsが気になり出す。
- by
- at 09:04
comments