粒子相互作用のシミュレーションに取り組んでいるときに、効率的な最近傍セル検索を提供すると見なされているMorton オーダー (Z オーダー) ( Wikipedia リンク)のグリッド インデックス付けに出くわしました。私が読んだ主な理由は、メモリ内の空間的に近いセルのほぼ連続した順序付けです。
最初の実装の途中であるため、特に基本的な均一グリッドと比較して、最近傍のアルゴリズムを効率的に実装する方法について頭を悩ませることはできません。
セル (x,y) が与えられた場合、8 つの隣接セル インデックスを取得し、それぞれの z インデックスを計算するのは簡単です。これにより、要素への一定のアクセス時間が提供されますが、z-index を計算するか、事前定義されたテーブルで検索する必要があります (軸ごとに分離し、OR を計算します)。どうすればこれがより効率的になるでしょうか? 配列 A の要素に A[0] -> A 1 -> A[3] -> A[4] -> ... という順序でアクセスすると、A[1023 の順序よりも効率的です。 ] -> A[12] -> A[456] -> A[56] -> ...?
Z オーダーで最近傍を見つけるためのより単純なアルゴリズムが存在することを期待していました。線に沿った何か: 隣接セルの最初のセルを見つけて、反復します。しかし、これは 2^4 サイズのブロック内でのみうまく機能するため、そうではありません。ただし、2 つの問題があります。セルが境界上にない場合、ブロックの最初のセルを簡単に特定してブロック内のセルを反復処理できますが、セルが最近傍セルであるかどうかを確認する必要があります。セルが境界上にある場合は、2^5 個のセルを考慮する必要がある場合よりも悪いことになります。ここで何が欠けていますか？私が必要とすることを行う比較的単純で効率的なアルゴリズムはありますか?
ポイント 1. の質問は簡単にテストできますが、記述されたアクセス パターンが生成する基本的な命令についてはあまり詳しくなく、舞台裏で何が起こっているのかを本当に理解したいと思っています。
ヘルプ、参考文献など、事前に感謝します...
編集：
ポイント1を明確にしていただきありがとうございます！ということで、Z-orderingを使うと隣接セルのキャッシュヒット率が平均的に上がるというのは興味深いですね。キャッシュのヒット/ミス率をプロファイリングする方法はありますか?
ポイント2に関して：インデックスi = f（x1、x2、...、xd）がビットごとのインターレースなどから取得されるR ^ dの点群のモートン順序配列を構築する方法を理解していることを追加する必要があります.私が理解しようとしているのは、次の単純な ansatz よりも、最近傍を取得するためのより良い方法があるかどうかです (ここでは d=2、「疑似コード」)。
// Get the z-indices of cells adjacent to the cell containing (x, y)
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2
point = (x, y)
zindex = f(x, y)
(zx, zy) = f^(-1)(zindex) // grid coordinates
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1), // neighbor grid
(zx , zy - 1), (zx, zy + 1), // coordinates
(zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]
ni= [f(x[0], x[1]) for x in nc] // neighbor indices