計算アルゴリズム【Ⅱ】at TECH計算アルゴリズム【Ⅱ】 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞの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はソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch