たとえば、ファイル内の特定の単語または数字を検索したいとします。内容はソートされています（明らかに）。ファイルに対してバイナリ検索を実行したいので、ファイル全体を配列にコピーしてからバイナリ検索を実行するのは本当に時間の無駄のように思えます...私は効果的にそれを線形時間アルゴリズムにしました。検索を実行する前に、O(n) 時間かけて Darn ファイルをコピーする必要があります。
これを行うより速い方法はありますか？バイトではなく行で動作する lseek のようなものはありますか?
そうでない場合は、代わりに線形検索を実行したほうがよいでしょうか (プログラムの全期間で検索を1 回だけ実行すると仮定します) ?
行単位でシークすることはできません。それは一度考えてみれば明らかです。
ただし、テキスト ファイルに対して一種のバイナリ検索を行うことはできます。
あなたがすることは次のとおりです。
ディスクベースのバイナリ検索は、少なくとも最初は「ブロック対応」である必要があります。つまり、全体の 1 バイトを読み取っても、I/O コストは同じであるという事実を認識している必要があります。もう1つは、シーケンシャル読み取り操作と比較して、シーク操作のコストが相対的に高くなることです。
ディスク I/O の特性に関するこの認識を使用できるいくつかの方法:
ファイルが小さい場合 (数百キロバイト未満など)、ファイル全体をメモリに読み込む (または実質的にメモリ マップする) 方がほぼ確実に高速です。これは、シークと転送のために複数の i/o 操作を実行するオーバーヘッドが、ファイル全体を読み取るよりもはるかに悪いためです。これは、ほとんどのプログラムが実行し、ほとんどのオペレーティング システムが完了していると想定しています。
すべての行が同じ長さであるか、非常に予測可能な長さでない限り、行番号 n を探す簡単な方法はありません。しかし、バイナリ検索を実行するには、バイナリ検索でバイト オフセットを使用し、オフセットの前後で 100 バイト (単語の長さがすべて 100 文字未満の場合)、合計 200 バイトを読み取ります。次に、その途中の前後の改行をスキャンして、単語を抽出します。
はい、lseek はできますが、1 行あたりの各単語/数値のサイズが固定されていると役立ちます。そうでない場合は、ファイルのサイズで lseek し、最も近い単語の先頭を探す必要があります。バイナリ検索の典型的な O(log n) 時間の複雑さを達成するために。
ファイルコマンドには「行」の概念がないため、「lseek」機能はありません。この概念は、生のファイルコマンドとは異なる抽象化レイヤーに存在します。
高速かどうかは、ファイルのサイズ、ディスク ドライブの速度、使用可能な RAM の量など、さまざまな要因によって異なります。大きなファイルでない場合は、ファイル全体をメモリにロードした方が速いと思います。
ファイルが大きい場合は、バイナリ検索アルゴリズムを使用してファイルをより小さな範囲 (たとえば、数メガバイト) に絞り込んでから、そのブロック全体をロードします。
前述のように、ファイルはテキスト ファイルであるため、ファイル内の特定の行が始まるバイトを確実に予測することはできません。ersatz の二分探索のアイデアは非常に優れています。しかし、最近のシーケンシャル I/O の速さとランダム I/O の遅さを考えると、ファイルが巨大でない限り、実際には大きな節約にはなりません。
あなたが言及したように、それを読み込もうとする場合は、直線的に検索することもできます。そのため、修正した Boyer-Moore 検索を使用して読み込めば、かなりうまくいくでしょう。
ここには非常に多くのパフォーマンスのトレードオフがあるため、典型的なデータを測定するまで何が意味があるのかを知ることは不可能です.
このコードを保守する場合は、単純にする必要があります。 検索がまれであるか、ファイルが小さい場合は、線形検索を使用してください。コストが実際に問題になる場合は、いくつかの実験を行う必要があります。
線形検索の後に試みる 2 番目のことはmmap、ファイルを検索して改行をスキャンすることです。これには直線的な時間がかかりstrchrますが、非常に高速になる可能性があります。ファイルが改行で終わることを保証できると役立ちます。行の境界が決まったら、二分探索を行うことで比較の数を少なく保つことができます。
考慮すべきもう 1 つのオプションは、Boyer-Moore 文字列検索です。これは準線形時間検索であり、検索パターンのサイズによっては、対数バイナリ検索よりも高速になる場合があります。Boyer-Moore は、長い検索文字列に特に適しています。
最後に、バイナリ検索が非常に優れているが、行の識別がパフォーマンスのボトルネックであると判断した場合は、各行の開始位置を事前に計算し、これらの事前計算された位置をバイナリ形式で補助ファイルに保存できます。
readline()予測は 1 つだけでも構いません。 orのようなものを使用して一度に 1 行ずつ読むことは、ほぼ確実に避ける価値があります。この戦略では、常に行の内容を保持するためのfgets()呼び出しが必要になるからです。malloc()すべての回線で電話をかけるmalloc()コストは、検索や比較のコストを圧倒する可能性があります。