c++ - C ++でファイルを一度にメモリに読み込まずにバイナリ検索を実行する方法

Question

バイナリ検索を使用して、ファイル内の特定の場所からデータを読み取る方法が必要です。

Answer 1

ファイル全体をメモリに読み込まずに目的を達成するには、2 つの方法があります。最初の (そしておそらく最も堅牢で移植性の高い) 方法は、ポジショニング API を使用することです。

• std::ifstream::tellg()
• std::ifstream::seekg()

クラスの上記の 2 つのメソッドを使用すると、std::ifstreamコンテンツ全体をメモリに読み込まずにファイルを「ナビゲート」できます。

mmap()2 番目の方法は、たとえば" " を使用してファイルをメモリに単純に "マップ" することです。OS (およびそのファイルシステム ドライバー) は、ページングとデータの読み取りを処理します。アプリケーションの観点からは、ファイル全体がメモリに読み込まれたように見えます。

残りは、ファイルに含まれるデータの種類と、バイナリ検索の実装方法によって異なります。

Answer 2

これは、ファイル内のデータ形式に大きく依存します。ファイル内でバイナリ検索を実行するには、いくつかの条件が満たされている必要があります。

• データ レコードは、ディスク ファイル内でソートされている必要があります。
• ファイル内のレコードを選択するには、O(1) 手段が必要です。

これらが両方とも当てはまる場合、ディスク上のバイナリ検索は他のバイナリ検索とまったく同じように機能します。相違点は、比較のためにレコードをフェッチする場合、レコードのディスク ファイル内の適切な場所を検索し、ディスクからレコードをロードして、ロードしたレコードに基づいて比較することによってレコードをフェッチすることです。

このアプローチを取る場合は、パフォーマンスに非常に注意する必要があります。ディスクからのシークと読み取りは、メモリ内での操作に比べてはるかに時間がかかります。ディスク キャッシュはかなり役立ちますが、ディスクを移動するたびに、何桁ものパフォーマンスが失われます。