外部検索アルゴリズム

Question

外部ストレージに格納されている非常に大きなソートリストを持っている場合。このリストを内部メモリに持ち込むことができないと仮定すると、このリストのキーを擬似コードで探す良い検索アルゴリズムは何でしょうか？時間の複雑さはどうなるでしょうか？また、このアルゴリズムを設計する際に考慮すべき重要な要素は何ですか？

Answer 1

あなたの外部記憶装置はファイルに保存された固定サイズのレコードの単なる配列であり、プログラミング言語はmemory map the fileであると仮定すると、通常はbinary search algorithmを使用できます。

Cで言う、++あなた

1. mmapファイルが
2. 、始まりと のmmap-EDファイルの末尾にvoid *型のポインタを取るには、あなたのレコードタイプ
3. へのポインタをキャストし、標準バイナリ検索の実装の1つであるstd::lower_bound()を使用してレコードを検索します。

ファイルをメモリにマップしても、ファイル全体が内部メモリにロードされるわけではなく、キャッシュされたサイズを保持するスマートポリシーを使用して、ファイルから読み込まれたページのキャッシュに自動的にロードされます利用可能なメモリ範囲内のページ。

これはソートされたファイルを検索するための標準的な方法であり、それを再設計する理由はありません（私の知る限り）。外部メモリのバイナリ検索アルゴリズムの複雑さは、外部ストレージモデル、バッファリング/ページング戦略などに依存しますが、ハードドライブの場合は通常のO（log N）であると見なすことができます。 out-of-core algorithmsとデータ構造のチュートリアルとライブラリを検索することをお勧めします。