8

こぼれる可能性のあるデータ構造、つまりキューに関する優れたリソースや書籍はありますか？

大きなオブジェクトを格納すると、すべてのメモリがいっぱいになる可能性がありますが、たとえば、そのキュー構造の最も使用されているアイテムをメモリに保持し、残りをディスクに保持できる場合（ページングのようなもの）。

同様に、この質問は、リンクリスト、配列、ハッシュテーブルなどの他の構造にも当てはまります。

4

3 に答える 3

10

バッファ ツリーがあります(PDF、0.6 MB):

「...効率的な外部プライオリティ キューを開発し、(1 次元) レンジ ツリーとセグメント ツリーの動的バージョンをバッチ処理しました。」

と

「...アルゴリズムのすべてのI/O固有の部分がデータ構造に隠されるように、既知の内部アルゴリズムから効率的な外部メモリアルゴリズムを簡単な方法で設計できるようにします。」

これは、 Jeffrey Scott Vitter による無料で入手できるオンライン ブック「Algorithms and Data Structures for External Memory (外部メモリのアルゴリズムとデータ構造)」(PDF、1 MB) で、主題のより広範な取り扱いの一部として言及されています。

于 2009-10-03T03:53:36.620 に答える
1

あなたが探しているのは、I/O 効率の良いアルゴリズムのトピックかもしれません。Google で検索しても本は見つかりませんでしたが、このコース ページには、関連する記事と関連しない記事のリストが含まれています。

B-treesのWikiPedia ページ、特にファイルシステムの B-treesに関するセクションも参照してください。

于 2009-10-03T04:10:20.723 に答える
0

基本的な RAM ベースのデータ構造 (たとえば、リンク リスト、スタック、キュー、プライオリティ キューなど) に効率的なディスク ベースの類似物を見つけるということですか? もしそうなら、以下の答えは役に立つかもしれませんし、役に立たないかもしれません.

あなたが何をしようとしているのか完全にはわかりません。キューとは、FIFO (先入れ先出し) キューまたはプライオリティ キューのことですか?

FIFO キューとログを処理するために、おそらくリング バッファとログ ローテーションを調べることができます。

ディスク アクセスを最小限に抑えるために RAM にデータをキャッシュする処理については、オペレーティング システムに任せたほうがよい場合もあれば、そうでない場合もあります。Windows アプリケーションを開発している場合を除き、オペレーティング システムは読み取りと書き込みのキャッシュを十分に実行する必要があるため、単純な方法でファイルの読み取りと書き込みを行う方がよい場合があります。しかし、私が知る限り、Windows の読み取り/書き込みキャッシュはひどいものです (私が間違っているかもしれません)。

おそらく、Linux の VFS サブシステムを見てhttp://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txtを調べると役立つでしょう。キャッシング。

私はキューとキャッシングの専門家ではありませんが、いくつかのことは知っています。あなたがやろうとしていることについてもっと詳しく教えていただければ、誰かがあなたが正しい解決策を見つけるのを手伝ってくれるかもしれません.

于 2009-10-03T03:53:55.607 に答える