矩阵迭代优化的解释

Question

我正在为期末考试复习一些优化技巧。出于某种原因，关于这个特定示例的信息不多，我也不明白，所以也许我可以获得一些帮助。

在Powerpoint幻灯片中，有这个强度降低的例子。

c1 = f();
for ( int i = 0; i < n; i++ ) {
  c2 = c1 + g(i);
  int ri = n * i;
  for ( int j = 0; j < n; j++ )
    a[ ri + j ] = c2 + h(j);
}

可以转化为

c1 = f();
*p = a;
for ( int i = 0; i < n; i++ ){
  c2 = c1 + g(i);
  for ( int j = 0; j < n; j++ )
    *p++ = c2 + h(j);
}

这怎么是同一个代码？我不明白，因为递增指针只会将其向上移动一个元素，而对于每个 i 值，原始指针向上移动的幅度远远超过 1。有什么错误还是我遗漏了什么？

Answer 1

代码遍历 n*n 个元素的数组。在第一个中，它是按行和列索引的，分别计算然后加在一起。但是由于数据在一个数组中，没有间隙，所以顺序访问不需要这样计算索引。

如果你想到第一个indexer：i*n + j，意思是i上1后，indexer上n。在第二个中，指针在每个元素后向前移动一个位置，因此当 j 循环从 0 到 n-1 时， i 变为 1 并且指针 p 移动了 n元素向前。所以它指向a[1*n+0]，相当于这个位置的i*n+j。并且一直持续到最后。

Answer 2

如果你忽略所有的计算，只看循环计数器…

for ( int i = 0; i < n; i++ ) {
  for ( int j = 0; j < n; j++ )
    printf("%d\n", n * i + j);
}

您会看到 ri + j，即 n * i + j，从 0（含）到 n²（不含）递增。因此，a[ri + j] 一次只是沿着数组走一个元素。您可以使用 p++.

进行相同的步行

矩阵迭代优化的解释

Explanation of matrix iteration optimization

c

iteration

optimization

loops

matrix