問題タブ [z-order-curve]

3D モートン数を計算する高速な方法を探しています。このサイトには、2D モートン数に対してそれを行うためのマジック ナンバー ベースのトリックがありますが、それを 3D に拡張する方法は明らかではないようです。

したがって、基本的には、最小限の操作で単一の 30 ビット数値にインターリーブしたい 3 つの 10 ビット数値があります。

32ビット整数からビットをデインターリーブする最も効率的な方法は何ですか？この特定のケースでは、奇数ビットのみを気にしますが、両方のセットのソリューションを一般化するのは簡単だと確信しています。

たとえば、に変換0b01000101したい0b1011。最も速い方法は何ですか？

編集：

このアプリケーションでは、偶数ビットがすべてゼロであることを保証できます。その事実を利用して、速度を向上させたり、スペースを削減したりできますか？

粒子相互作用のシミュレーションに取り組んでいるときに、効率的な最近傍セル検索を提供すると見なされているMorton オーダー (Z オーダー) ( Wikipedia リンク)のグリッド インデックス付けに出くわしました。私が読んだ主な理由は、メモリ内の空間的に近いセルのほぼ連続した順序付けです。

最初の実装の途中であるため、特に基本的な均一グリッドと比較して、最近傍のアルゴリズムを効率的に実装する方法について頭を悩ませることはできません。

1. セル (x,y) が与えられた場合、8 つの隣接セル インデックスを取得し、それぞれの z インデックスを計算するのは簡単です。これにより、要素への一定のアクセス時間が提供されますが、z-index を計算するか、事前定義されたテーブルで検索する必要があります (軸ごとに分離し、OR を計算します)。どうすればこれがより効率的になるでしょうか? 配列 A の要素に A[0] -> A 1 -> A[3] -> A[4] -> ... という順序でアクセスすると、A[1023 の順序よりも効率的です。 ] -> A[12] -> A[456] -> A[56] -> ...?

2. Z オーダーで最近傍を見つけるためのより単純なアルゴリズムが存在することを期待していました。線に沿った何か: 隣接セルの最初のセルを見つけて、反復します。しかし、これは 2^4 サイズのブロック内でのみうまく機能するため、そうではありません。ただし、2 つの問題があります。セルが境界上にない場合、ブロックの最初のセルを簡単に特定してブロック内のセルを反復処理できますが、セルが最近傍セルであるかどうかを確認する必要があります。セルが境界上にある場合は、2^5 個のセルを考慮する必要がある場合よりも悪いことになります。ここで何が欠けていますか？私が必要とすることを行う比較的単純で効率的なアルゴリズムはありますか?

ポイント 1. の質問は簡単にテストできますが、記述されたアクセス パターンが生成する基本的な命令についてはあまり詳しくなく、舞台裏で何が起こっているのかを本当に理解したいと思っています。

ヘルプ、参考文献など、事前に感謝します...

---

編集：
ポイント1を明確にしていただきありがとうございます！ということで、Z-orderingを使うと隣接セルのキャッシュヒット率が平均的に上がるというのは興味深いですね。キャッシュのヒット/ミス率をプロファイリングする方法はありますか?

ポイント2に関して：インデックスi = f（x1、x2、...、xd）がビットごとのインターレースなどから取得されるR ^ dの点群のモートン順序配列を構築する方法を理解していることを追加する必要があります.私が理解しようとしているのは、次の単純な ansatz よりも、最近傍を取得するためのより良い方法があるかどうかです (ここでは d=2、「疑似コード」)。

この質問:ビットのインターリーブを解除する方法 (UnMortonizing?)には、モートン数の 2 つの半分 (奇数ビットのみ) の 1 つを抽出するための良い答えがありますが、両方の部分 (奇数ビットと偶数ビット) 可能な限り少ない操作で。

私の使用では、32ビットの整数を取り、2つの16ビットの整数を抽出する必要があります。1つは偶数ビットで、もう1つは1ビット右にシフトされた奇数ビットです。

モートン数 (つまりインターリーブビット) を生成するためのマジック ナンバーを使用したシフトとマスクを使用するソリューションはたくさんあるようです。 .

アップデート

完全なシャッフル/シャッフル解除に関する Hacker's Delight のセクションを読み直した後、次のように適応したいくつかの有用な例を見つけました。

これは、現在のスカラー形式でも SIMD を利用することでも改善できると思うので、より良い解決策 (スカラーまたは SIMD) にまだ興味があります。

キーが3Dのポイントであり、3つの符号付き64ビット整数で表されるデータセットがある場合。そして、（ソートされた）Key-Valueストアを使用してそれらを格納したいと思います。ここで、キーは単なるバイト配列です（ただし、コンパレーターを指定できます）。3Dモートン数の計算方法のように、Z /モートン順序で行われるように、ビットインターリーブを使用することで、これらすべてのポイントをバイト配列に変換できると思います。

モートンの順序付けなしでより簡単に実行できる個々のポイントをフェッチすることに加えて、軸に位置合わせされたボックス内を検索する範囲検索を実行したいと思います。AとBをそれぞれ、すべての座標が最も低いボックスコーナーと、すべての座標が最も高い反対側のコーナーとして定義します。

今私の質問は次のとおりです。

1. 論理的にAとBの間にある任意の点Cについて、Cのモートン数もAとBのモートン数の間にありますか？（それがモートンの秩序のポイントではありませんか？）

2. 1が「いいえ」の場合、AとBは、Cが含まれることを保証する値に「丸め」られますか？

3. 1または2が可能であると仮定すると、検索結果はそのボックスの外側も指しますか？これは「ポストフィルター」で除外する必要がありますか？その「エラーセット」はどのくらいの大きさですか（検索のサイズまたは位置によって異なりますか）。

4. 整数が符号付きであるという事実は問題を引き起こしますか？もしそうなら、回避策はありますか？

要約すると、モートン数を使用することは、実際の問題に対する1つの可能な解決策にすぎません。3Dポイントを1次元値にマッピングする必要がある場合に、3D整数空間で効率的に範囲検索する方法は？DBで単一の範囲選択を実行し、最小キーと最大キーを使用して、理想的にはボックスの外側のポイントをできるだけ少なくすることで、AとBの間のすべてのポイントを取得したいと思います。

32bit用、64bit用、128bit用のモートンキーを最適なコードで作りたい！解決策は何ですか？

モートン順序を使用して行列の転置を改善したいと考えています。

モートンオーダーに関する記事を見つけましたが、その使い方がわかりません。

特に、

と

この行列を逆にしたい A = [1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16] (リニアアドレス)

に

B = [1 2 5 6; 3 4 7 8; 9 10 13 14; 11 12 15 16;]。

そして転置。

でも解けない……。

この変換の原理を知っている人はいますか?

よろしくお願いします。

3D のポイントである現在の入力データについては、モートン コードを使用して、ポイント リストにアクセスする際のキャッシュの一貫性を改善しています。

他に 6D と 7D のデータがあります。モートン コードは、このような次元に対しても優れた手法ですか? それとも他のテクニックはありますか？他の空間充填曲線の手法は、3D 自体の Morton よりも計算が複雑でした。人々が 6D/7D またはそれ以上の代替手法を使用するかどうか疑問に思っています。