- 2007-05-29 (Tue) 9:04
- Uncategorized
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:
- Newer: 係り受け解析: 実装
- Older: flock(2)はスレッドも排他するか？(2)
Comments:0
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
