C++ プログラムで 2D 関数のサンプルを計算して格納する効率的な方法を探しています。
具体的にするために、簡単な 1 次元の問題から始めて、それを 2D に一般化できない理由を説明します。
1-D バージョンは次のとおりです。関数 z = f(x) のサンプルを次の方法で計算します。入力からデータを読み取り、各入力に対応して x と z = g(x) の値を計算します。これで、(x,z = g(x)) ペアのテーブルができました。任意の x に対してエントリが 1 つしか存在しない場合、f(x) = z となります。それ以外の場合、f(x) = z1 + z2 + ... (ここで、z1、z2、... は特定の x に対応する z エントリです)。
上記の手順は、 を使用して簡単に実装できますstd::multimap。つまり、最初の段階では、結果をマップに保存するだけです (xキーとして)。最後に、マップを反復処理し、隣接する 2 つの要素が十分に近い場合は、対応する値を追加してそれらをマージします。x と z = g(x) の計算の複雑さが一定であると仮定すると、O(N log N) 時間の複雑さで N 個のサンプルを計算できます。
ここで、アルゴリズムを 2 次元に一般化したいと思います。つまり、最初に入力から (x,y,z=g(x,y)) ペアを計算し、次に f(x,y) = z1 + z2 + ... を設定します (固定 (x,y) ペアの場合) 、z1、z2、... は、(x,y) で始まるテーブル エントリの対応する z フィールドです。
前の解決策は、2D 平面での順序付けを定義できないという単純な理由により、一般化できません (実際に使用できますが、キーが に先行するstd::multimap<std::pair<double,double>,double>かどうかを確認するための意味のある比較はありません)。ただし、2D 平面には近さの概念があることに注意してください。2 つの点 (x1,y1) と (x2,y2) が与えられた場合、それらを出力でマージする必要があるかどうかを正確に判断できます。x1,y1x2,y2
まあ、非常に素朴な解決策は、隣接関係のより良い表記法がある2Dリンクリスト（各次元で個別にソートされた）を実装することです。しかし、これは少なくとも挿入には非常に非効率的であり、(他の多くの問題に加えて) 手順は O(M^2) 時間かかります (ここで、M = N * N は、計算したい 2D 平面上のサンプルの数です)。
問題をより効率的に解決できる方法 (より正確にはデータ構造) があるのだろうか?
非常に冗長でかなり曖昧で申し訳ありません。