4

非常に大きなテキストファイル（10GBの場合もあります）でバイナリ検索を実行するために使用できるライブラリはありますか？

このファイルは一種のログファイルです。すべての行は日付と時刻で始まります。したがって、行は順序付けられます。

4

6 に答える 6

4

行の長さが同じであるとは限らないため、キャリッジ リターンやライン フィードなどの認識可能な行区切り記号が必要になります。

二分探索パターンは、ほとんど従来のアルゴリズムになります。ファイルの「中間」を (長さで) シークし、たまたま着地した行の先頭まで (バイトごとに) シークし、行区切りシーケンスで識別され、そのレコードを読み取り、比較を行います。比較に応じて、上または下 (バイト単位) の途中までシークし、繰り返します。

レコードの開始インデックスを特定するときは、最後のシークと同じかどうかを確認してください。目的のレコードにダイヤルインするときに、途中で移動しても別のレコードに移動しないことに気付く場合があります。たとえば、それぞれ 100 バイトと 50 バイトのレコードが隣接しているため、75 バイトでジャンプすると常に最初のレコードの先頭に戻ります。その場合は、比較を行う前に次のレコードを読んでください。

かなり早く目標に到達できることがわかるはずです。

于 2010-04-13T16:23:10.260 に答える
4

私はそれを行う方法について疑似コードを書き始めましたが、見下すように見えるかもしれないのであきらめました。二分探索の書き方はおそらく知っているでしょう。実際には複雑ではありません。

次の 2 つの理由から、図書館にはありません。

  1. これは実際には「バイナリ検索」ではありません。行のサイズが異なるため、アルゴリズムを調整する必要があります (たとえば、ファイルの中央を探し、次の「改行」を探し、それを「中央」と見なします)。
  2. あなたの日時ログ形式はおそらく非標準です（わかりました、「標準」に見えるかもしれませんが、少し考えてみてください....おそらく「[]」などを使用して、ログメッセージから日付を分離します。[10 /02/2001 10:35:02] 私のメッセージ)。

要約すると、あなたの必要性はあまりにも具体的で単純すぎて、誰かがライブラリを書くのに苦労するカスタムコードに実装できないと思います:)

于 2010-04-13T16:40:57.030 に答える
2

ファイルをストリーミングできる必要がありますが、ランダムアクセスも必要になります。ファイルの各行に同じバイト数が含まれているという保証がないため、これをどのように達成するかはわかりません。それがあれば、オブジェクトのStreamを取得し、Seekメソッドを使用してファイル内を移動し、そこから1行を構成するバイト数を読み取ることでバイナリ検索を実行できます。ただし、これも、行が同じバイト数の場合にのみ有効です。そうしないと、行の途中に飛び込んだり飛び出したりします。

何かのようなもの

byte[] buffer = new byte[lineLength];
stream.Seek(lineLength * searchPosition, SeekOrigin.Begin);
stream.Read(buffer, 0, lineLength);
string line = Encoding.Default.GetString(buffer);
于 2010-04-13T15:36:14.043 に答える
0

これは、ファイル内の改行ごとに Int64 をメモリに保持するという制約の下では、それほど悪くはありません。これは、1 行あたり 1000 バイト (10,000,000,000 / 1000 * 4) = 40mb を見ているとすると、テキスト行の平均の長さに大きく依存します。非常に大きいですが、可能です。

だからこれを試してください：

  1. ファイルをスキャンし、各改行の序数オフセットをリストに保存します
  2. ファイルオフセットをスキャンしてデータを読み取るカスタム比較子を使用して、リストをバイナリ検索します。
于 2010-04-13T16:23:58.073 に答える
-2

Listオブジェクトには、バイナリ検索メソッドがあります。

http://msdn.microsoft.com/en-us/library/w4e7fxsh%28VS.80%29.aspx

于 2010-04-13T15:29:08.830 に答える