Оптимизация трехмерной задачи, где я перебираю все элементы и рассматриваю расстояния до всех остальных элементов. - PullRequest
Новая
       14

Оптимизация трехмерной задачи, где я перебираю все элементы и рассматриваю расстояния до всех остальных элементов.

0 голосов
/ 30 октября 2018

Я должен рассмотреть трехмерное пространство, где элементы распределены равномерно. Каждый элемент описан тремя координатами, x, y и z. Я должен рассчитать расстояние между каждым из них, чтобы все остальные, таким образом: 

float distance = 0;
for(int ix = 0; ix<n; ix++) {
    for(int iy = 0; iy<n; iy++) {
        for(int iz = 0; iz<n; iz++) {

            for(int jx = 0; jx<n; jx++) {
                for(int jy = 0; jy<n; jy++) {
                    for(int jz = 0; jz<n; jz++) {
                        distance = distance + calcDistance(ix, iy, iz, jx, jy, jz) / 2
                    }
                }
            }

        }
    }
}

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

В одном измерении это легко. Один цикл от 0 до n, а другой от i до n, и я рассматриваю каждое расстояние только один раз. Но я не могу сделать то же самое здесь. Есть ли способ оптимизировать это?

1 Ответ

0 голосов
/ 30 октября 2018

Чит. Обмануть много.

Скажем, точка "слева, сверху, спереди" - point[0][0][0], и это единственное, что нас волнует. Точка справа от нее находится на расстоянии 1, следующая точка справа - на расстоянии 2 ... То же «тривиальное сложение» работает и для двух других осей. Вам нужно только рассчитать расстояния для диагоналей (от point[0][0][0] до любой другой точки, которая не находится в идеальном направлении вправо / вниз / назад).

Как только вы получите все расстояния между point[0][0][0] и всеми другими точками, вы можете повернуть их вспять, чтобы найти все расстояния от всех других точек до point[0][0][0].

Теперь ... Расстояние от point[x1][y1][z1] до point[x2][y2][z2] будет точно таким же, как расстояние от point[x1][y1][z1] до point[x2][y2][z2]; и оба они будут точно такими же, как расстояние от point[0][0][0] до point[x2-x1][y2-y2][z2-z1]. Это означает, что вы можете использовать «расстояния от point[0][0][0]», которые у вас уже есть (сверху), в качестве справочной таблицы, чтобы найти все другие расстояния между всеми остальными точками; без выполнения (предположительно гораздо более дорогого) sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1) ) ); расчета для любого из них.

Конечно, если вы используете «расстояния от point[0][0][0]», которые у вас уже есть (сверху), в качестве справочной таблицы, вероятно, нет смысла хранить эти расстояния вообще. Вы можете просто использовать значения из справочной таблицы, когда вам это нужно (без сохранения в другом месте).

Другими словами; Я бы хотел такую ​​функцию (в C): 

static double getDistance( int x1, int y1, int z1, int x2, int y2, int z2) {
    int dx = abs(x1-x2);
    int dy = abs(y1-y2);
    int dz = abs(z1-z2);
    return distanceTable[dx][dy][dz];
}

В этом случае вам придется предварительно рассчитать таблицу расстояний (которая является «расстояниями от point[0][0][0] до любой другой точки» выше).

Однако, если вы хотите быть ленивым, возможно, было бы веселее сделать что-то вроде этого: 

static double getDistance( int x1, int y1, int z1, int x2, int y2, int z2) {
    int dx = abs(x1-x2);
    int dy = abs(y1-y2);
    int dz = abs(z1-z2);
    if(dx+dy+dz == 0) return 0.0;

    double distance = distanceTable[dx][dy][dz];
    if(distance == 0.0) {
        distance = sqrt(dx*dx + dy*dy + dz*dz);
        distanceTable[dx][dy][dz] = distance;
    }
    return distance;
}
...