！提高for循环速度

求助！！！提高for循环速度
我的程序由于for循环过多而导致速度很慢，求高手帮忙优化啊！
原代码比较复杂，我已经将其简化如下：
int width = 8000;
int cell[4][4], p[4][8000];//p中各个元素的值或为0或为1
int i, j, r = 2;
for(i=0; i<(4+1)/2; i++)
{
for(j=i; j<(4+1)/2; j++)
{
if ( ((i-r)*(i-r)+(j-r)*(j-r)) < (r+0.5)*(r+0.5) )
{
cell[i][j]= 1;
cell[i][4-1-j] = 1;
cell[j][i]= 1;
cell[j][4-1-i] = 1;
cell[4-1-i][j] = 1;
cell[4-1-i][4-1-j] = 1;
cell[4-1-j][i] = 1;
cell[4-1-j][4-1-i] = 1;
}
}
}
int n = 0;
for(int k = 0; k < 8000; k++)
{
n = 0;
for(i = 0; i < 4; i++)
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0 && p[i][k] != 0)
n++;
}
//后面还有类似的for循环,且会对cell的值做修改
}
性能优化
[解决办法]
1、用一维数组代替二维数组；
2、(i-r)*(i-r)+(j-r)*(j-r))<(r+0.5)*(r+0.5)这个关于(i,j)的条件可以直接建表，不要每次都去计算。
[解决办法]
貌似可以转化成整型运算，提高点速度。
  if ( ((i-r)*(i-r)+(j-r)*(j-r)) < (r+0.5)*(r+0.5) )

[解决办法]
如果不能改算法，就将能够提前算出的表达式用变量代替，并放到循环外。
[解决办法]
(i-r)*(i-r)+(j-r)*(j-r)) < (r+0.5)*(r+0.5)
------------------------------------
上面好多的童鞋看题不仔细，这不是关键啊，这个才循环几次，不影响的。

下面那个8000次的循环里面再2重循环才是问题所在。

我觉得从优化循环来说，不一定能提升多少的效率。
看起来似乎是大规模的矩阵运算，要从数学这方面入手，改进算法。
[解决办法]
把条件判断中if(cell[i][j] != 0 && p[i][k] != 0)一部分提到前面，可以减少内层循环的次数：

for(int k = 0; k < 8000; k++)
{
n = 0;
for(i = 0; i < 4; i++)
if( p[i][k] != 0)//先判断一下p[i][k]，不符合条件就不进行内层循环 
 
{
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0)
n++;
}
}
//后面还有类似的for循环,且会对cell的值做修改
}
  

[解决办法]

int n_values[8000] = {0};
for(i = 0; i < 4; i++)
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0)
for(int k = 0; k < 8000; k++)
{
if(p[i][k+j] != 0)
n_values[k]++;
}
}

[解决办法]

int cell[4][4], p[4][8000];//p中各个元素的值或为0或为1
for(int k = 0; k < 8000; k++)
{
  n = 0;
  for(i = 0; i < 4; i++)
  for(j = 0; j < 4; j++)
  {
    if(cell[i][j] != 0 && p[i][k] != 0)
/*

1.上面提到了p里面的元素都是0或者1，如此的话，可不可以不要用int型，用单字节的char型甚至一个bit来表示？
2.不等于操作是否可以用与操作来进行比较？
3.想了想可能还是数据结构的问题。如果cell[4][4]中的元素也是0或者1，那么cell数组是不需要的，用一个short型变量（刚好是16个bit）就足够了。
然后你的p变量当然也可以简化，简化完了之后做与操作就可以了。

*/
    n++;
  }

[解决办法]
分析一下思路，你这个问题是要对3维空间计算

for(i=0; i<(4+1)/2; i++)
{
for(j=i; j<(4+1)/2; j++)
{
if ( ((i-r)*(i-r)+(j-r)*(j-r)) < (r+0.5)*(r+0.5) )
{
cell[i][j] = 1;
cell[i][4-1-j] = 1;
cell[j][i] = 1;
cell[j][4-1-i] = 1;
cell[4-1-i][j] = 1;
cell[4-1-i][4-1-j] = 1;
cell[4-1-j][i] = 1;
cell[4-1-j][4-1-i] = 1;
}
}
}

到这里，你是想以（2，2）为中心点，找出半径在2。5之内的所有点，并设置为1。
这里有个疑问，为什么是Cell(4,4),而不是Cell（5，5）

for(int k = 0; k < 8000; k++)
{
n = 0;
for(i = 0; i < 4; i++)
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0 && p[i][k] != 0)
n++;
}

}

x，y平面上每个元素对应Z轴8000个点。
现在你想计算在整个空间内所有值为1的点的个数。
你这个空间有个特点，对于相同的x，也就是i，在z轴的值是相同的。换句话说，把空间值表示为v=f（i，j，k），无论j如何变化v‘=f’（i，k）的值是固定的。

我的思路是这样。对于每个i，计算出对应k的值为1的个数m，接下来计算对应于该i的y的值为1的个数n，然后计算m*n,得到一个平面内的总个数。然后迭代i，计算 sigma（m×n）
------解决方案--------------------

（i=0，？）。这样的时间复杂度为 O（i） × O（k+j），伪代码如下（未验证）.

count = 0;
for(int i = 0; k < 4; i++)
{
m=0;
n=0;
for(k = 0; k < 4; k++){
if( p[i][k] != 0)
m++;
}
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0 )
n++;
count += m*n;
}

[解决办法]

int cell[4][4],  p[4][8000], cellToByte[4], src[4][1000], res[4][1000];
int tmp = 0;

for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 1000; ++j)
{
tmp = 0;
for (int m = 0; m < 8; ++m)
{
tmp = tmp << 4;
if (p[i][j * 8 + m] != 0)
tmp += 15;// 1111B
}
res[i][j] = tmp;
}
}

for (int i = 0; i < 4; ++i)
{
tmp = 0;
for (int j = 0; j < 4; ++j)
{
tmp = tmp << 1;
if (cell[i][j] != 0)
tmp += 1;
}

cellToByte[i] = 0;
for (int m = 0; m < 8; ++m)
{
cellToByte[i] = cellToByte[i] << 4;
cellToByte[i] += tmp;
}
}

for (int i = 0; i < 1000; ++i)
{
for (int j = 0; j < 4; ++j)
res[j][i] = cellToByte[j] & src[j][i];
}

就是用bitmap算法，应该好点吧，就像25L说的直接用bit 前面的cell和p数组储存的时候直接以bit方式储存
[解决办法]
1.二维数组在访问，尽量顺序访问，换言之尽量别跨行，一行一行来！比如：a[0][j]->顺序访问各个j值后，再是a[1][j]，如果中间来个来回跨行访问，效率会很低喽！因为数组都是行优先存储的。访问顺序与效率的关系具体细节不多言！

2.内部循环可以展开的，展开效率更好！当然这样会增加代码量，不过这是次要的！记住一点，只要能让程序顺序执行跑到最长化

22 for(int k = 0; k < 8000; k++)
 23 {
 24         n = 0;
 25                 for(j = 0; j < 4; j++)
 26                 { 
 
 27                         if(cell[0][j] != 0 && p[0][k] != 0)
 28                                 n++;
 29                 }               
 30                 for(j = 0; j < 4; j++)
 31                 {
 32                         if(cell[1][j] != 0 && p[1][k] != 0)
 33                                 n++;
 34                 }
 35                 for(j = 0; j < 4; j++)
 36                 {
 37                         if(cell[2][j] != 0 && p[3][k] != 0)
 38                                 n++;
 39                 }
 40                 for(j = 0; j < 4; j++)
 41                 {
 42                         if(cell[3][j] != 0 && p[3][k] != 0)
 43                                 n++; 
 
 44                 }
 45 }               

或者全部展开


[解决办法]

int n = 0;
for(int k = 0; k < 8000; k++)
{
n = 0;//A）这个有用吗
for(i = 0; i < 4; i++)
for(j = 0; j < 4; j++)
{
if(cell[i][j] != 0 && p[i][k] != 0)
n++;
}
//后面还有类似的for循环,且会对cell的值做修改
}

如果
1）//A）无用

//改成

int n = 0;

for(i = 0; i < 4; i++)//短的循环放在外面，
for(j = 0; j < 4; j++)//
if(cell[i][j]) //公共操作从循环内提出到循环外部，这是循环优化的一种方法
for(int k = 0; k < 8000; k++)//长的循环放在内部，这是循环优化的另一种方法，
      //不知道是否所有编译器都自动这样做
{
     if(p[i][k])n++;//有跳转
     //或如果p[i][k]只是0或1； n+= p[i][k];无跳转,
}
//后面还有类似的for循环,且会对cell的值做修改
}

2）如果A）的赋值有用,改成

int n = 0;
for(int k = 0; k < 8000; k++)
{
n = 0;//A）这个有用吗，如果有用的话，下面这样做：
for(i = 0; i < 4; i++)
if(p[i][k])//公共操作从循环内提出到循环外部，这是循环优化的一种方法
for(j = 0; j < 4; j++){
if(cell[i][j] )n++;//可以改为 n+=cell[i][j];如果cell[i][j只有0,1两个值
                   //直接计算可能比比较后计算快，因为不存在跳转，程序可以直接执行
                   //会打乱流水线。
}
//后面还有类似的for循环,且会对cell的值做修改
}

这个估计也就是这样了，如果还不能加快的话，调整下程序吧，也许数据结构有问题呢。

查看更多 下一篇