Home > Uncategorized > Tx: Succinct Trie Data Structure

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が気になり出す。

Similar Posts:

Comments:0

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://kzk9.net/blog/2007/05/tx_succinct_trie_data_structur.html/trackback
Listed below are links to weblogs that reference
Tx: Succinct Trie Data Structure from moratorium

Home > Uncategorized > Tx: Succinct Trie Data Structure

お薦め本
広告
Archives
Categories

Return to page top