Оптимизация алгоритма вычисления расстояний между ячейками в частицах

Question

Оптимизация алгоритма вычисления расстояний между ячейками в частицах

Рейтинг: 3Ответов: 1Опубликовано: 07.03.2011

Есть вопрос оптимизации алгоритма.

alt text

Это своеобразное представление кристалической решётки. Прямоугольные параллелепипеды (частицы), состоящие из точек - ячеек (27 штук), образуют кристалличекую решётку. Задаются расстояния по x,y,z между частицами (a,b,c) и между ячейками(a',b',c') в частице. Необходимо раcсчитать расстояние между каждыми двумя ячейками, не входящими в одну частицу.

Реализовал расчёт расстояний через длину вектора, поскольку, поместив начало координат в какую-либо ячейку, можно вычислить координаты всех ячеек. Но расчёт расстояний по всем ячейкам занимает очень много времени для образца размером, например, 10*100*100 частиц. Просьба предложить алгоритм, позволяющий производить рассчёт более эффективно.

Кусок кода для рассчёта расстояний с учётом следующего алгоритма:

Расчёт расстояний внутри 1 слоя ZY
Расчёт расстояний от каждой ячейки внутри слоя до каждой ячейки в следующем слое ZY.
И так далее до последнего слоя.
Потом необходимо сделать комбинацию расстояний, чтобы вычисить полные расстояния.


// В плоскости YZ вычисляем энергию зваимодействия ячеек в одном слое
for (int i = 0; i < 27 * Y * Z; i++) {
    if (i % 27 == 0) {
        part_num++;
    }

for (int j = 0; j < (part_num - 1) * 27; j++) {
        distance =
            sqrt(pow((x_vect.at(i) - x_vect.at(j)), 2) +
            pow((y_vect.at(i) - y_vect.at(j)), 2) + 
            pow((z_vect.at(i) - z_vect.at(j)), 2));
    }

for (int j = (part_num) * 27; j < 27 * Y * Z; j++) {
        distance =
            sqrt(pow((x_vect.at(i) - x_vect.at(j)), 2) +
            pow((y_vect.at(i) - y_vect.at(j)), 2) + 
            pow((z_vect.at(i) - z_vect.at(j)), 2));
    }
}

// Выбираем слой
for (int layer = 1; layer < X; layer++) {
    // В плоскости YZ вычисляем энергию зваимодействия ячеек в разных слоях
    for (int i = 0; i < 27 * Y * Z; i++) {
        for (int j = 27 * Y * Z * layer; j < Z * Y * 27 * (layer + 1); j++) {
            distance =
                sqrt(pow((x_vect.at(i) - x_vect.at(j)), 2) +
                pow((y_vect.at(i) - y_vect.at(j)), 2) + 
                pow((z_vect.at(i) - z_vect.at(j)), 2));
        }
    }

cout << "Layer: " << layer << endl;
}

Прошу помочь с алгоритмом.

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2

Дистанция между двумя ячейками может быть представлена как

d(i,p,j,q,k,r) = 
    sqrt( (i*a+p*a')*(i*a+p*a') + (j*b+q*b')*(j*b+q*b') + (k*c+r*c')*(kc+rc')),

где

-n < i < n, -2<= p<= 2, -n < j < n, -2<= q<= 2, -n < k < n, -2<= r<= 2;
i, j, k - разность индексов двух частиц по x, y, z соответственно;
p, q, r - разность индексов ячеек двух частиц по x, y, z соответственно при условии совмещения центров частиц

При этом очевидно выполняются условия

d(i,p,j,q,k,r) = 
    d(i,p,k,r,j,q) = 
        d(j,q,i,p,k,r) = 
            d(j,q,k,r,i,p) =
                d(k,r,i,p,j,q) = 
                    d(k,r,j,q,i,p)

d(-i,p,j,q,k,r) = d(i,-p,j,q,k,r)
d(i,p,-j,q,k,r) = d(i,p,j,-q,k,r)
d(i,p,j,q,-k,r) = d(i,p,j,q,k,-r)

Последнее означает, что i, j, k можно всегда считать неотрицательными в диапазоне от 0 до n-1.

Таким образом, для случая решетки n*n*n частиц число всевозможных расстояний

d(i,p,j,q,k,r) = m*(m-1)*(m-2)/6 + m*(m-1) + m = m*(m*m +3*m +2)/6,

где m = 5*n. Если n=50 достаточно вычислить и сохранить 2635500 различных расстояний. И вместо расчёта расстояний просто в зависимости от разности индексов ячеек в переменных i, j, k, p, q, r брать нужное расстояние. Правда потребуется определенной порядок хранения d(i,p,j,q,k,r) и обращения к ним. Если же не заморачиваться с этим, то можно хранить все m*mm расстояний, т.е. при n=50 это 15625000 чисел, что также терпимо при современных объемах оперативной памяти.

Оптимизация алгоритма вычисления расстояний между ячейками в частицах

Ответы