在c中取消切换while循环优化

Question

我很难通过 循环取消切换 来优化以下 while 循环。我已经尝试应用 wiki 中的示例，但是我很难将它应用到 while 循环。我有以下代码：

int n = 5,
    m = 5,
    i = 0,
    val = 0;

while (i < n ) {
  j = 0;

  while (j < m ) {
    if (i < j ) {
      val = val + i ;
    }
    else if ( j == i ) {
      val = val - 1;
    }
    else {
      val = val + j ;
    }

    j = j + 1;
  }

  i = i + 1;
}

并尝试通过以下方式取消切换：

while (i < n ) {
  j = 0;

  if (i < j ) {
    while (j < m ) {
      val = val + i;
      j = j + 1;
    }
  }

  if ( j == i ) {
    while (j < m) {
      val = val - 1;
      j = j + 1;
    }
  }

  if (i > j) {
    while (j < m) {
      val = val + j;
      j = j + 1;
    }
  }

  i = i + 1;
}

我哪里做错了。

Answer 1

Loop unswitching according to wikipedia 是一个编译器优化，所以我有点困惑为什么你需要自己做这个，但我认为这在分解 for 方面已经很好了。 .ifs

for (i = 0; i < n; ++i) {
  // j < i
  for (j = 0; j < i; ++j) {
    val = val + j;
  }

  // j == i
  val = val - 1;

  // j > i
  for (j = i + 1; j < m; ++j) {
    val = val + i;
  }
}

这不是传统上可以取消切换的循环，因为这里的条件变量是循环变量。

Answer 2

最好在铅笔和纸的帮助下展开这样的环。您想要以下网格的总和：

           0   1   2   3   4  |   5   n

    0     -1   0   0   0   0  |   0   0
    1      0  -1   1   1   1  |   1   1
    2      0   1  -1   2   2  |   2   2
    3      0   1   2  -1   3  |   3   3
    m      0   1   2   3  -1  |   4   4

网格可以细分为三个部分：对角线、正方形部分中对角线旁边的上下三角形和n与m不同时的矩形块。

让我们用方形部分 k² 和矩形部分 k·r:

来表示网格的维度

    k = min(n, m)
    r = max(m, n) - k

现在您可以看到这三个部分贡献了哪些总和：

    val = 2·∑(k - i - 1)·i       # two triangles
        + r·∑(i)                 # rectangle
        - k                      # diagonal

（来自 i = 0; i < n; i++ 的所有总和运行。）这个总和可以重新排列为：

    val = 2·(k - 1)·∑(i) - 2*∑(i²) + r·(i) - k
        = (2·k + r - 2)·∑(i) - 2*∑(i²) - k

这将您的两个嵌套循环减少为两个两个独立的循环来计算自然数及其平方的总和。幸运的是，这些总和可以用简单的关系表示：

    ∑(i) = (n - 1)·n / 2
   ∑(i²) = (2·n - 1)·(n - 1)·n / 6

你现在有一个常数时间公式来计算你的总和：

    int val(int n, int m)
    {
        int k = (n < m) ? n : m;
        int r = ((n > m) ? n : m) - k;

        return (2*k + r - 2) * (k - 1) * k / 2
              - (2*k - 1) * k * (k - 1) / 3 - k;
    }

当然，所有这些都与循环展开没有任何关系。

在c中取消切换while循环优化

unswitch while loop optimization in c

c

optimization

loops

compiler-optimization