1億を超えるレコードを持つ優先キューを持つアプリケーションを実装する必要があります。私の問題は、このすべてのデータをメモリに保持できないため、ディスクに保存する必要があることです。このすべての情報をディスクに保存できるキャッシュソリューションはありますか？
1297 次
1 に答える
1
これは、B ツリーを少し変更して使用することで解決できると思います。
B ツリーは、要素を見つけるために必要なディスク読み取りの回数を最小限に抑える方法で、並べ替えられた要素をディスクに格納するように特別に設計されています。それらは要素をソートされた順序で格納するため、通常どおり挿入を実行し、ツリーの左端の要素 (つまり、左端のリーフ ノードの最初の要素) を取得して最小要素を見つけることにより、それらを優先キューとして使用できます。
次数 d の B ツリーでは、O(log d n) 回のディスク読み取りと書き込みを使用して最小要素を見つけることができます。ここで、n は要素の総数です。また、挿入と削除に必要なのは、O(log d n) ディスクの読み取りと書き込みだけです。
ただし、B ツリーの左端のリーフ ノードへのポインターを格納することで、これを大幅に高速化できます。このノードは、最小キーと最小に近い他のキーを格納します。このポインターがあれば、ノードの最初の要素を取得することで、1 回のディスク読み取りで最小値を調べることができます。これにより、extract-min 操作も高速化されます。キーを検索することなく、そのノードからキーを直接削除できます。これを機能させるには、いくつかの B ツリーの再調整操作が必要になる場合がありますが、これらの操作が頻繁に行われないため、削除を行うための償却作業が O(1) しかないことを示すことができます。
つまり、一番左のリーフへのポインターで B ツリーを使用すると、ディスクの読み取りと書き込みに関して次のような時間の複雑さが生じます。
- 検索分: O(1)
- 挿入: O(log d n)
- 抽出分: O(1)償却
お役に立てれば！
于 2014-05-31T18:54:13.150 に答える