0

我有以下嵌套循环计算：

int aY=a*Y,aX=a*X;
for(int i=0; i<aY; i+=a)
{
    for(int j=0; j<aX; j+=a)
    {
        xInd=i-j+offX;
        yInd=i+j+offY;
        if ((xInd>=0) && (xInd<X) &&
            (yInd>=0) && (yInd<Y) )
            {
             z=yInd*X+xInd;
            //use z
            }
     }
}

我想尽可能地失去对i,j和xInd的依赖yInd。换句话说，我想“遍历”在循环中运行时接收到的所有值，z但不涉及帮助变量i、j和- 或者至少涉及最少数量的计算（最重要的是没有乘法）。我怎样才能做到这一点？欢迎提供其他使循环更高效的可能方法的提示。谢谢！xIndyInd

4

2 回答 2

0

如果我们假设 offX 和 offY 为 0，并用 '<=' 替换你的 '<'，我们可以通过这样做去掉 i 和 j：

for (yInd = 0; yInd <= aX + aY; ++yInd)
    for (xInd = max(-yInd, -aX); xInd <= min(yInd, aY); ++xInd)
于 2013-01-12T14:49:59.833 回答
0

如果我们将问题解读为如何最小化循环周围的迭代次数，我们可以采用以下方法。

约束：

(xInd>=0) && (xInd<X)
(yInd>=0) && (yInd<Y)

允许使用来收紧 for 循环的边界。扩展xInd并yInd给出：

0 <= i - j + offX <= X
0 <= i + j + offY <= Y

修复i允许我们将第二个循环边界重写为：

for(int i=0; i<aY; i+=a) {
    int lower = (max(i + offX - X, -i - offY) / a) * a; //factored out for clarity.
    int upper = min(i + offX, Y - i -offY);
    for(int j=lower; j<=upper; j+=a) {

offX如果您对、offY、的可能值有更多了解，则可能a会进一步减少。XY

请注意，实际上您可能不想在没有先进行分析的情况下盲目地应用这种类型的优化（它可能会阻止编译器为您执行此操作，例如gcc 石墨）。

用作索引

如果该值z=yInd*X+xInd用于索引内存，则通过确保内存访问是连续的以确保良好的缓存行为来获得更大的胜利。

当前yInd每次迭代都会发生变化，因此可能会导致缓存性能不佳。

这个问题的解决方案是首先计算和存储所有索引，然后使用这些索引在第二遍中执行所有内存操作。

int indicies[Y * X];
int index = 0;
for(...){
    for(...){
        ...
        indicies[index++] = z;
    }
}
// sort indicies
for(int idx = 0; idx < index; idx++){
    z = indicies[idx];
    //do stuff with z
}
于 2013-01-12T15:02:54.580 回答