优化阵列处理循环

我正在一个编程的难题，我有点困惑。问题是计算二维平面上磁盘的交点数。 x总是0，y是数组中的索引。该元素是存储在数组元素中的半径。性能很好，元素数量少，元素数量少，但拥有大量像10,000,000元这样的元素性能很差。我目前使用2嵌套循环来处理数组。优化阵列处理循环

我将不胜感激任何人可能会给的帮助。我受限于给予我的数据结构，无法更改它们。由于我正在处理整数和中心点在同一个y轴上，所以计算圆盘是否与另一个圆心相交。

下面是代码：

int number_of_intersections (int A[], int n) 
{ 
int base = 0; 
int inc = 0; 
int intersect = 0; 
int maxrad = 0; 
int x; 

if (n>1) 
{ 
    for (base=0;base<(n-1);base++) 
    { 
    inc = base+1; 
    do 
    { 
    if (inc - base <= (A[base] + A[inc])) 
    {          
    intersect ++; 
    if (!(intersect^10000000)) 
    { 
     return -1; 
    } 
    } 
    inC++; 
    } while (inc < n); 
    } 
} 

return intersect; 
}

谢谢您的时间

来源

2011-01-09 highlander

对于初学者来说，不要写``如果（（^相交1000000）！）。只要写'if（intersect == 10000000）`。它更清晰。另外，你能否在这里提供更多的上下文和例子？你有什么尝试？为什么它不工作？ – templatetypedef 2011-01-09 06:01:51

你的做法是O（n^2），因为你正在测试每对圆盘，因此坏的速度有大量的光盘。

我不能想办法让我的头顶部渐近更好的性能，但有一个优化，你可以做到的。

说你在元素p，其半径为m。显然，位于以p每一个光盘 - 米< = Y < = P + M具有其中心在y =米包括的光盘。因此，您只需要为远离光盘的碟片做任何工作。

来源

2011-01-09 06:12:17 Bwmat

正如评论中指出的那样，这实际上是一维问题。实际上，这是交叉区间的问题，区间[x，y]对应于磁盘x =中心 - 半径和y =中心+半径中的最低和最高x坐标。

想想从左到右沿x和y点移动。你可以通过保持两个指向磁盘的指针进行排序，一个用于x点，另一个指向y点。使用数据结构跟踪当前指针下的磁盘。当你看到一个x点时，识别点的磁盘和所有当前磁盘之间的交集，然后将其作为当前磁盘。当您看到一个y点时，从当前磁盘中删除该点的磁盘。

来源

2011-01-09 06:42:17 mcdowella

您的代码气味像过早优化。

摆脱外部if语句的，因为它不会帮助你多少反正（外环将不会有n < = 1执行）。

在那里卸下神奇常数（10000000）和（我想）位摆弄伎俩。这是难以阅读，不灵活在所有（至少应该是常量变量），并且逻辑通过使用XOR代替==表达差。

也许用易读的for-loop来交换你的do-while循环。

（由@Philip波特建议）现在，你的代码看起来更加清晰，而不是慢。也许你意识到现在你已经保存了一些代码行和一些括号，并且你可能会删除更多。

现在有了可读的代码，您终于可以打开之前隐藏的更大的优化了 - 请参阅其他文章。

注意：不要早做聪明的优化技巧。他们不会做你任何好。

编辑：为了使点清晰;-)

int number_of_intersections (int A[], int n) 
{ 
    int intersect = 0; 
    const int maxIntersections = 10000000;  

    for (int base = 0; base < n-1; base++) 
    { 
     for(int inc = base+1; inc < n; inc++) 
     { 
      if (inc - base <= A[base] + A[inc]) 
      {          
       intersect ++; 
       if (intersect == maxIntersections) return -1; 
      } 
     } 
    } 

    return intersect; 
}

来源

2011-01-09 08:42:51 Eiko

优化阵列处理循环

回答

相关问题