2

大きなファイルを読み取ることで解決する問題があり、そのアプローチ方法については一般的な考えがありますが、もっと良い方法があるのではないかと考えています。

問題は次のとおりです。私はいくつかの巨大なディスクファイル（それぞれ）にそれぞれのレコード（合計レコードの周り64GB）でいっぱいになっています。各レコードには、他のフィールドの中でも、タイムスタンプと、タイムスタンプが有効かどうかを示すisValidフラグがあります。ユーザーがタイムスパンを入力すると、タイムスタンプが指定された範囲内にあるすべてのレコードを返す必要があります。2.5KB25,000,000

データのレイアウトは、「有効」とマークされたすべてのレコードについて、タイムスタンプが単調に増加するようになっています。無効なレコードはまったく考慮されるべきではありません。したがって、これはファイルが一般的にどのように見えるかです（範囲ははるかに大きいですが）：

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=13, IsValid = true };
a[3]  = { Time=401, IsValid = false }; // <-- should be ignored
a[4]  = { Time=570, IsValid = false }; // <-- should be ignored
a[5]  = { Time=16, IsValid = true }; 

a[6]  = { Time=23, IsValid = true };  // <-- time-to-index offset changed 
a[7]  = { Time=24, IsValid = true };
a[8]  = { Time=25, IsValid = true };
a[9]  = { Time=26, IsValid = true };

a[10] = { Time=40, IsValid = true };  // <-- time-to-index offset changed 
a[11] = { Time=41, IsValid = true };
a[12] = { Time=700, IsValid = false };  // <-- should be ignored 
a[13] = { Time=43, IsValid = true };

タイムスタンプとカウンターの間のオフセットが一定である場合、最初のレコードを探すことはO(1)操作になります（私は単にインデックスにジャンプします）。そうではないので、私はこの情報を（すばやく）見つけるための別の方法を探しています。

1つの方法は、修正された二分探索かもしれませんが、無効なレコードのより大きなブロックを処理する方法が完全にはわかりません。ルックアップを高速化するために「インデックス」を作成することもできると思いますが、このような大きなファイルが多数あり、抽出されたデータサイズはファイル全体よりもはるかに小さいため、これらの各ファイルをトラバースしたくありません。 、レコードごとに、インデックスを生成します。インデックスを作成する際に、バイナリ検索も役立つかどうかを考えています。

言うまでもなく、インデックスに最適な構造が何であるかはわかりません。平衡二分木？

4

4 に答える 4

2

修正された二分探索を使用できます。アイデアは、通常の二分探索を実行して下限と上限を計算し、有効なエントリ間の中間を返すことです。

変更は、現在のエントリが無効である場合の部分にあります。その場合、有効なエントリがある2つのエンドポイントを把握する必要があります。たとえば、中点が3の場合

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=401, IsValid = false };
a[3]  = { Time=570, IsValid = false }; // <-- Mid point.
a[4]  = { Time=571, IsValid = false };
a[5]  = { Time=16, IsValid = true }; 
a[6]  = { Time=23, IsValid = true };

上記の場合、アルゴリズムは2つのポイントa[1]とa[5]を返します。これで、algoは下半分または上半分を二分探索することを決定します。

于 2012-09-27T12:31:28.477 に答える
1

他の誰かのデータベースコードを使用することは良い考えのように見え始めるのはこのような時です、

とにかく、有効なデータの始まりを見つけるまでいじくり回してから、終わりに達するまで読む必要があります。

ポットショットを撮り、それに応じてマーカーを移動することから始めます。ただし、無効なレコードをヒットした場合を除いて、有効なレコードの検索を開始します。

無効なタイムスタンプを有効なタイムスタンプに置き換えるためにファイルに対してメンテナンスタスクを実行するか、外部インデックスを維持することはおそらく価値があります。

于 2012-09-27T12:00:37.330 に答える
1

二分探索にランダム性をもたらす可能性があります。実際には、ランダムアルゴリズムは、大規模なデータセットに対して適切に機能します。

于 2012-09-27T12:20:51.180 に答える
1

修正された二分探索が良い解決策になり得るように聞こえます。無効なレコードの大きなブロックが問題である場合は、指数関数的に増加するサイズのブロックをスキップすることでそれらを処理できます（例：1,2,4,8、...）。これにより現在のブラケットの終わりをオーバーシュートする場合は、ブラケットの終わりで、1、2、4、8、...のステップで後方にスキップして、中央にかなり近い有効なレコードを見つけます。

于 2012-09-27T12:31:38.237 に答える