0

我的这部分代码运行时间太长，我正在寻找一种优化它的方法。我认为查找表是最快的方法，但我可能是错的。我的程序有一个主 for 循环，对于主 for 循环中的每次迭代，一个嵌套循环会遍历1,233,487迭代，然后在满足条件时遍历 if 语句。主 for 循环经过898,281迭代，因此它必须经过898,281 * 1,233,487计算。我将如何创建一个查找表来优化这些计算/是否有更好的方法来优化我的代码。

for (int i = 0; i < all_neutrinos.size(); i++)
{ //all_neutrinos.size() = 898281
    int MC_count = 0;  //counts per window in the Monte Carlo simulation
    int count = 0; //count per window for real data

    if (cosmic_ray_events.size() == MC_cosmic_ray_events.size()) 
    {
        for (int j = 0; j < cosmic_ray_events.size(); j++) 
        { //cosmic_ray_events.size() = 1233487
            if ((MC_cosmic_ray_events[j][1] >= (all_neutrinos[i][3] - band_width))
             && (MC_cosmic_ray_events[j][1] <= (all_neutrinos[i][3] + band_width)))
            {
                if ((earth_radius * fabs(all_neutrinos[i][2] - MC_cosmic_ray_events[j][0]))
                     <= test_arc_length)
                {
                    MC_count++;
                }
            }   

            if ((cosmic_ray_events[j][7] >= (all_neutrinos[i][3] - band_width))
             && (cosmic_ray_events[j][7] <= (all_neutrinos[i][3] + band_width)))
            {
                if(earth_radius * fabs(all_neutrinos[i][2] - cosmic_ray_events[j][6])
                    <= test_arc_length)
                {
                    count++;
                }
            }
        }
        MCcount_out << i << "     " << MC_count << endl;
        count_out << i << "     " << count << endl;
    }
}
4

2 回答 2

4

首先cosmic_raw_events和MC_cosmic_ray_events完全无关。做两个循环。

MC_cosmic_ray_events按排序[1]。cosmic_ray_events按排序[7]。all_neutrinos按排序[3]。

这不一定是就地排序——如果需要，您可以将指针或索引数组排序到其中。

从将宇宙射线事件的高水位和低水位指数设置为 0 开始。

现在，走过去all_neutrinos。对于每一个，推进高水位直到 MC_cosmic_ray_events[highwater][1] > all_neutrinos[i][3] + band_width)。然后推进低水位直到MC_cosmic_ray_events[lowwater][1] >= all_neutrinos[i][3] - band_width)。

在半开范围内j = lowwater upto but not including highwater，运行：

if (
  (earth_radius * fabs(all_neutrinos[i][2] - MC_cosmic_ray_events[j][0]))
  <= test_arc_length
) {
  MC_count++;
}

现在重复直到i结束all_neutrinos。

然后重复这个过程，使用cosmic_ray_eventsand [7]。

您的代码需要O(NM)时间。这段代码需要O(N lg N + M lg M + N * (average bandwidth intersect rate)时间。如果通过带宽测试的人数相对较少，那么您的速度会快很多。

假设您平均每 0.5 个相交all_neutrinos，这将快 100000 倍。

于 2017-06-22T18:06:10.617 回答
-1

没有太多需要优化的地方。计数非常高，并且没有太多的硬计算正在进行。您可以进行一些明显的优化，例如在进入 j 循环之前将 (all_neutrinos[i][3] +/- bandwitdth) 存储在局部变量中。不过，您的编译器可能已经这样做了，但这肯定会提高调试模式下的性能。

您是否尝试过将 j-loop 的两半分开并有两个 j-loop？如：

   auto all_neutrinos_2 = all_neutrinos[i][2];
   //... precompute bandwidth limits
   for (int j = 0; j < cosmic_ray_events.size(); j++) 
    { //cosmic_ray_events.size() = 1233487
        auto MC_events = MC_cosmic_ray_events[j][1];
        if ((all_neutrinos_lower <= MC_events) &&(MC_cosmic_ray_events[j][1] <= all_neutrinos_higher))
        {
            if ((earth_radius * fabs(all_neutrinos_2 - MC_cosmic_ray_events[j][0]))
                 <= test_arc_length)
            {
                MC_count++;
            }
        }
    }


    for (int j = 0; j < cosmic_ray_events.size(); j++) 
    { //cosmic_ray_events.size() = 1233487
        auto events = cosmic_ray_events[j][7];
        if ((all_neutrinos_lower <= events) && (events  <= all_neutrinos_higher))
        {
            if(earth_radius * fabs(all_neutrinos_2 - cosmic_ray_events[j][6])
                <= test_arc_length)
            {
                count++;
            }
        }
    }

我觉得您可以通过这种方式从改进的内存缓存命中中获得一些改进。

除此之外的任何改进都将涉及打包输入数据以减少内存缓存未命中，并且将涉及修改生成 MC_cosmic_ray_events 和 cosmic_ray_events 数组的结构和代码

在不同线程上运行的几个较小的任务中分割计数也是我在这一点上会认真考虑的一条路线。数据访问是只读的，每个线程可以有自己的计数器，最后都可以求和。

于 2017-06-22T18:37:18.417 回答