検索の高速化

ウィキペディア小見出し辞書

検索の高速化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/18 23:50 UTC 版)

「NT File System」の記事における「検索の高速化」の解説

ファイルの管理はB+木で行われ、大量のファイルが存在していても、検索やアクセス速度の低下が少ない。

検索の高速化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)

「連結リスト」の記事における「検索の高速化」の解説

連結リストで特定の要素を探す場合、たとえそれがソート済みであっても一般に O(n) の時間を要する（線型探索）。これは連結リストの重大な欠点である。これを改善するいくつかの方法が存在する。 ソートされていないリストでは、平均検索時間を短縮する単純なヒューリスティックとして "Move To Front" と呼ばれる手法がある。これは、1度検索して見つかったノードをリストの先頭に移動させるという方式である。これは一種の簡単なキャッシュ構成法であり、最も後に検索したノードを再度検索する場合に高速化される。 もう1つの一般的な手法は、より効率的な外部のデータ構造を使ってノードにインデックスを付けるというものである。例えば、赤黒木やハッシュテーブルを構築し、その要素が連結リストの各ノードへの参照を持つようにする。1つのリストに対して、そのようなインデックスを複数構築できる。この手法の欠点は、ノードの追加や削除の度にインデックス側の更新が必要となる点である。少なくともインデックスを再利用する前に更新が必要である。