計算アルゴリズム【Ⅱ】
at TECH
[
2ch
|
▼Menu
]
■コピペモード
□
スレを通常表示
□
オプションモード
□このｽﾚｯﾄﾞのURL
■項目テキスト
850:デフォルトの名無しさん 08/12/12 02:43:00 とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう) 間違いがあるかもしれませんが。。。 ----------------------------------------------------------- HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造 Nikolas Askitis Ranjan Sinha School of Computer Science and Information Technology, RMIT University, Melbourne 3001, Australia. Email: {naskitis,rsinha}@cs.rmit.edu.au 概要 トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。 burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。 しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは 不十分なパフォーマンスにつながり得る。 この論文では、既存の手法とうまく組み合せたキャッシュを考慮した トライベースのデータ構造であるHAT-trieを提案する。 いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。 ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの 実行時間とメモリ使用量の改善が見られた。 HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。
次ページ
最新レス表示
スレッドの検索
類似スレ一覧
話題のニュース
おまかせリスト
▼オプションを表示
レスジャンプ
mixiチェック！
Twitterに投稿
オプション
しおりを挟む
スレッドに書込
スレッドの一覧
暇つぶし2ch
4770日前に更新/251 KB
担当:undef