0

私は多くのベクトル計算を必要とするデモに取り組んでおり、プロファイリングでは、与えられたベクトル間の距離を見つけるのに最も時間がかかることがわかりました。

現在、X ^ 2ベクトルの配列をループし、それぞれの間の距離を見つけます。つまり、（X ^ 2）/ 2の一意のベクトルしかない場合でも、距離関数をX^4回実行します。距離。

これは次のように機能します:(疑似c）

#define MATRIX_WIDTH 8

typedef float vec2_t[2];
vec2_t matrix[MATRIX_WIDTH * MATRIX_WIDTH];

...

for(int i = 0; i < MATRIX_WIDTH; i++)
{
    for(int j = 0; j < MATRIX_WIDTH; j++)
    {
        float xd, yd;
        float distance;

        for(int k = 0; k < MATRIX_WIDTH; k++)
        {
            for(int l = 0; l < MATRIX_WIDTH; l++)
            {
                int index_a = (i * MATRIX_LENGTH) + j;
                int index_b = (k * MATRIX_LENGTH) + l;

                xd = matrix[index_a][0] - matrix[index_b][0];
                yd = matrix[index_a][1] - matrix[index_b][1];

                distance = sqrtf(powf(xd, 2) + powf(yd, 2));
            }
        }

        // More code that uses the distances between each vector
    }
}

私がやりたいのは、冗長性のない（X ^ 2）/ 2距離の配列を作成して入力し、最終的に必要になったときにその配列を参照することです。ただし、この配列に適切な方法でインデックスを付ける方法については空白を描いています。ハッシュテーブルで十分ですが、巧妙なインデックス作成方法で解決できると思われる問題には、複雑すぎて時間がかかると思います。

編集：これは群れのシミュレーション用です。

4

1 に答える 1

2

パフォーマンスのアイデア：a）可能であれば、ルート計算を回避するために、距離の2乗で作業します。b）定数の整数乗にpowを使用しないでください。代わりに、xd*xdを使用してください。

アルゴリズムを変更することを検討します-O（n ^ 4）は本当に悪いです。物理学の相互作用（2dフィールドの距離の場合もO（n ^ 4））を扱う場合、bツリーなどを実装し、影響の少ない粒子の相互作用を無視します。しかし、それは「距離を使用するより多くのコード...」が実際に何をするかに依存します。

いくつかの考慮事項を実行しました。一意の距離の数は0.5*n * n（+1）で、n = w*hです。一意の距離が発生したときに書き留めると、iとjから開始することで、両方の内部ループを減らすことができることがわかります。

さらに、マトリックスインデックスを介してこれらの距離にアクセスするだけでよい場合は、4D距離マトリックスを設定できます。

コードの達人が言ったように、メモリが制限されている場合は、前述のように、三角形の行列にアクセスするルックアップ関数を使用して、ほぼ50％節約できます。アクセス時に合計されないように、おそらくラインインデックスを事前に計算します

float distanceArray[(H*W+1)*H*W/2];
int lineIndices[H];

searchDistance(int i, int j)
{
    return i<j?distanceArray[i+lineIndices[j]]:distanceArray[j+lineIndices[i]];
}
于 2013-03-18T00:18:47.310 に答える