Какой метод индексации я могу использовать для хранения расстояний между векторами X^2 в массиве без избыточности?

Question

Я работаю над демонстрацией, которая требует много векторной математики, и в профилировании я обнаружил, что она тратит больше всего времени на поиск расстояний между заданными векторами.

Прямо сейчас он просматривает массив векторов X^2 и находит расстояние между ними, то есть выполняет функцию расстояния X^4 раза, хотя (я думаю) есть только (X^2)/2 уникальных расстояния.

Это работает примерно так: (псевдо с)

#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 без избыточности, а затем ссылаться на этот массив, когда он мне наконец понадобится. Тем не менее, я рисую бланк о том, как индексировать этот массив таким образом, чтобы это работало. Хэш-таблица сделает это, но я думаю, что она слишком сложна и медленна для проблемы, которая, кажется, может быть решена с помощью умного метода индексации.

РЕДАКТИРОВАТЬ: Это для моделирования стека.

Answer 1

Идеи производительности: а) если возможно, работать с квадратом расстояния, чтобы избежать вычисления корня б) никогда не использовать pow для постоянных целочисленных степеней - вместо этого используйте xd*xd

Я бы подумал об изменении вашего алгоритма - O(n^4) действительно плохо. Имея дело с взаимодействиями в физике (также O (n ^ 4) для расстояний в 2d поле), можно было бы реализовать b-деревья и т. Д. И пренебрегать взаимодействиями частиц с небольшим воздействием. Но это будет зависеть от того, что на самом деле делает "больше кода, использующего расстояние...".

Просто сделал несколько соображений: количество уникальных расстояний составляет 0,5*n*n(+1) при n = w*h. Если вы запишите, когда происходят уникальные расстояния, вы увидите, что оба внутренних цикла можно уменьшить, начиная с i и j.

Кроме того, если вам нужен только доступ к этим расстояниям через матричный индекс, вы можете настроить матрицу 4D-расстояний.

Если память ограничена, мы можем сэкономить почти 50%, как упоминалось выше, с помощью функции поиска, которая будет обращаться к матрице триангулара, как сказал Code-Guru. Мы бы, вероятно, пересчитали индекс строки, чтобы избежать суммирования по доступу

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]];
}