c ++中的成对距离计算

Question

我正在计算c ++中大量(~1e5)粒子数的势能.为了做到这一点,我正在运行一个双循环,我在其中计算成对距离,并从这些距离计算系统的总势能.下面是代码的相关部分(它不是复制/粘贴准备好的,因为需要定义数据,有些东西不在上下文中;方法仍然有效,这就是我在这里要展示的内容) :

int colstart = 2;
int colend = 4;
double PE = 0;
double p_mass = 8.721e9 * 1.989e30; // mass of sim particle in kg
double mpc_to_m = 3.08567758e22; // meters per mpc
double G = 6.67384e-11; // grav. constant in mks units

// Calculating PE
for(int i = 0; i < data.size()-1; i++) // -1 is for empty line at the end of every file
  {
    //cout << i << " " << data[i].size() << endl;
    for(int j = 0; j < i; j++)
     {

       double x_i = (double)atof(data[i][2].c_str());
       double y_i = (double)atof(data[i][3].c_str());
       double z_i = (double)atof(data[i][4].c_str());

       double x_j = (double)atof(data[j][2].c_str());
       double y_j = (double)atof(data[j][3].c_str());
       double z_j = (double)atof(data[j][4].c_str());

       double dist_betw = sqrt(pow((x_i-x_j),2) + pow(y_i-y_j,2) + pow(z_i-z_j,2)) * mpc_to_m;

       PE += (-1 * G * pow(p_mass,2)) / (dist_betw);  

     }
  }

有没有更快的方法来进行这种类型的计算？我愿意接受有关近似的建议,即如果它将总势能返回到大约1%左右.

谢谢!

Answer 1

一些潜在的微观受害者:

• 乘法可能比使用pow()平方距离更快;
• 共同因素-1 * G * pow(p_mass,2) / mpc_to_m可以保持不变;
• 求和可能稍快一些1.0 / dist_betw,然后乘以最后的公因子.
• 您可能(或可能不)能够准确地近似平方根,快于sqrt().有很多近似值可供选择.
• 将每个坐标转换为double一次,将值存储在另一个数组中,而不是存储在内部循环的每次迭代中.

从算法上讲,您可以丢弃距当前点太远的粒子,从而对能量做出重大贡献.一个简单的修改可以在昂贵的平方根之前检查平方距离,如果它太大则继续前进.通过将粒子存储在空间感知的数据结构(如八叉树)或简单的网格中,您可以获得进一步的改进,这样您甚至不需要查看远点; 但如果粒子经常移动,这可能不实用.