1

私は、人々が興味深いと思うかもしれない問題に取り組んできました (そして、おそらく誰かが既存の解決策を知っています)。

オブジェクトへのポインターのペアの長いリストで構成される大きなデータセットがあります。次のようなものです。

[
  (a8576, b3295), 
  (a7856, b2365), 
  (a3566, b5464),
  ...
]

一度にメモリに保持するにはオブジェクトが多すぎるため (数百ギガバイトになる可能性があります)、ディスクに格納する必要がありますが、メモリにキャッシュすることができます (おそらく LRU キャッシュを使用)。

すべてのペアを処理するこのリストを実行する必要があります。これには、ペアの両方のオブジェクトをメモリにロードする必要があります (まだキャッシュされていない場合)。

では、質問: リスト内のペアを並べ替えて、メモリ内キャッシュの効果を最大化する (つまり、キャッシュ ミスの数を最小化する) 方法はありますか?

ノート

  1. 明らかに、並べ替えアルゴリズムは可能な限り高速である必要があり、リスト全体を一度にメモリに保持できることに依存するべきではありません (そのための十分な RAM がないため)。必要に応じて数回リストします。

  2. ペアではなく個々のオブジェクトを扱っている場合、簡単な答えはそれらをソートすることです。ペアの両方の要素を考慮する必要があるため、これは明らかにこの状況では機能しません。

  3. 問題は最小グラフカットを見つけることに関連している可能性がありますが、問題が同等であっても、最小カットを満たす解決策はないと思います

  4. 私の仮定では、ヒューリスティックはデータをディスクからストリーミングし、より良い順序でチャンクに書き戻すというものです。これを数回繰り返す必要があるかもしれません。

  5. 実際にはペアだけでなく、トリプレット、クアッドレット、またはそれ以上の場合もあります。ペアに対してこれを行うアルゴリズムが簡単に一般化できることを願っています。

4

4 に答える 4

1

まず、リストをmmapできます。これは、メモリではなく十分なアドレス空間がある場合に機能します。たとえば、64 ビット CPU などです。これにより、要素に順番にアクセスしやすくなります。

両方の要素を考慮するキャッシュ内の最小距離に従ってそのリストを並べ替えることができます。これは、オブジェクトが連続したスペースにある場合にうまく機能します。並べ替え関数は、(a, b) を (c, d) と比較 = (a - c) + (b - d) (ハミング距離のように見えます) のようなものになります。次に、オブジェクト ストアのスライスを取得し、リストに従って処理します。

編集：距離の間違いを修正しました。

于 2009-01-31T21:35:55.737 に答える
1

このリストをソートするだけではありませんが、多方向マージソートの一般的なパターンが適用できる場合があります。つまり、メモリ内で個別に処理できる小さなセットにセットを (おそらく再帰的に) 分割することを検討してください。次に、以前に処理されたセットの小さなチャンクをすべて組み合わせることができる第 2 フェーズ。ペアで何をしているかの特定の性質を知らなくても、ソートされたデータを扱っていると、多くのアルゴリズムの問​​題がはるかに簡単になると言っても過言ではありません (グラフの問題を含む。手をここに）。

于 2009-01-31T21:48:12.000 に答える
1

あなたの問題は、コンピュータ グラフィックス ハードウェアの同様の問題に関連しています。

三角形メッシュでインデックス付きの頂点をレンダリングする場合、通常、ハードウェアには最近変換された頂点のキャッシュがあります (前回は最大 128 でしたが、最近はその数が大きくなっていると思われます)。キャッシュされていない頂点の計算には、比較的コストのかかる変換操作が必要です。三角形のメッシュを再構築してキャッシュの使用を最適化する「メッシュの最適化」は、以前はかなりホットな研究トピックでした。頂点キャッシュの最適化 (または最適化 :^) をグーグルで検索すると、問題に関連する興味深い資料が見つかるかもしれません。他のポスターが示唆しているように、これを効果的に行うには、データに固有の一貫性を活用する必要があると思います。

心に留めておくべきもう 1 つのこと: LRU キャッシュが過負荷になると、(パスごとにキャッシュ全体を切り替えるのではなく) 少なくともいくつかのアイテムをメモリに保持するために、MRU 置換戦略に変更する価値がある場合があります。John Carmack が、Direct3D テクスチャ キャッシング戦略に関連して、このテーマに関する優れた資料を書いたことを覚えているようです。

于 2009-02-01T10:30:33.117 に答える
0

この質問に対する答えは、オブジェクトのペアのアクセス パターンに大きく依存すると思います。あなたが言ったように、単純でペアになっていない場合は、ポインターを並べ替えるだけが最適です。より複雑なケースでは、これらの値の局所性がより重要なパターンである場合 (たとえば、これらがキーと値のペアであり、多くの検索では、キーの局所性は値よりもはるかに重要です)。

つまり、私の答えは、この質問には一般的なケースでは答えられないということです。

構造を保存するために、実際に必要なのはおそらくB-treeです。これらは、あなたが話していることのために設計されています-すべてをメモリに保持したくない（または保持できない）大規模なコレクションを追跡します。

于 2009-01-31T21:29:24.393 に答える