2

レコードが時間でソートされている大きなログファイルがあります。各行には時間があります。時間T1と時間T2（T1 <= T2）の間のすべてのレコードを見つける必要があります。ファイル全体を1行ずつスキャンして、T1の開始行を見つけ、それをバッファーにコピーして、終了時刻T2に達するまで次の行をスキャンできます。これは機能しますが、あまり効率的ではありません。

二分探索を使用して、時間T1とT2の行を見つけることができるかどうか疑問に思います。しかし、私は以下を決定する方法がわかりません：

  1. ファイルの中央行
  2. 渡す必要のあるオフセットを決定する方法はlseek()？

ファイルに対してバイナリ検索を使用することは可能ですか？

4

4 に答える 4

1

十分なアドレス空間がある場合は、メモリマップトファイルの使用を検討してください。これらは、これを行うための最も簡単で効率的な方法の1つである傾向があります。移植性のためにboost::iostreams::mapped_fileを使用してください。

于 2012-08-27T18:50:11.243 に答える
1

あなたの行はすべて平均の長さに近い合理的であると仮定しましょう（つまり、ログの半分程度を占める行がないことを意味します）。これにより、二分探索が可能になります。

次に、次の機能があることも前提としています。

//find the first start of a new log line after (or including) position start
//return the last position of the file if no start could be found
streampos findNextLineStart(ifstream &file, streampos start);
//extract the data as a timestamp from a line
int extractDate(ifstream &file, streampos lineStart);

これらの関数を使用して、次を実装できます。

//find the position of the first line whose date is bigger than the given
streampos lower_bound(ifstream &file, int date)
{
  file.seekg(0, ios::end);
  streampos begin = 0, 
            end = file.tellg();
  while(begin < end)
  {
     streampos cur = (begin + end) / 2;
     streampos start = findNextLineStart(file, cur);
     //was a line start found?
     if(start < end)
     {
        int lineDate = extractDate(file, start);
        if(lineDate < date)
          begin = start;
        else
          end = start;
     }
     else
       //narrow the bound as no line was found
       end = cur;
  }
  return begin;
}

これが（すべてのコーナーケースで）機能することを保証するものではありませんが、全体的な実装をスケッチしています。別の関数upper_boundを使用すると、範囲内の行の開始と終了を取得できます。

于 2012-08-27T19:15:34.217 に答える
1

まず、範囲内の最後のレコードを見つけるためにバイナリ検索を実行したくない場合があります。T1を見つけたら、とにかく目的の範囲外のレコードが見つかるまでレコードを直線的に読み取ります。したがって、実際には、範囲内の最初のレコードを見つけるだけで済みます。

また、正確なn/2番目のレコードを見つけることによってバイナリ検索を実装する必要はありません。現在の2つの境界の中間のバイトを検索し、次の完全なレコードを見つけて、そこから境界を更新するだけであれば、問題ありません。

于 2012-08-27T19:16:38.107 に答える
0

真ん中の線は必要ありません。代わりに、真ん中の文字を取得してから、改行が見つかるまで一度に1文字ずつ後方に移動できます。次に、現在の行の開始があることがわかります。その行のタイムスタンプが遠すぎる場合は、その行とそれ以降のすべてを破棄できます。タイムスタンプが過去に遠すぎる場合は、そのタイムスタンプとその前のすべてを破棄します。必要な行が見つかるまで、これを繰り返すことができます。

これは標準の二分探索アルゴリズムです。二分探索では実際には真ん中の線は必要ありません-ほぼ真ん中の何かがあれば十分です。一部の回線が他の回線よりもはるかに長い極端な場合には遅くなる可能性がありますが、通常は十分に高速です。

于 2012-08-27T19:10:41.720 に答える