0

我是操作系统的初学者，我正在尝试理解一些代码片段。您能向我解释一下这些代码片段之间的区别吗？

int sum_array_rows(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
  }

和

int sum_array_col(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
  }

不同的部分是双重For 属性其中一个应该比另一个更快吗？如果是这样，你能解释一下为什么，因为我不明白。

4

3 回答 3

2

正如其他人所说，如果数组维度不同，第二个代码片段可能会导致溢出错误，因此需要修复此问题。

然而，由于多维数组的元素如何存储在内存中以及现代 CPU 的缓存架构，在最内层循环中循环最后一个数组维度可能会比其他方式更快。

此处要搜索的术语是“缓存位置”和“数组步长”

于 2018-06-04T08:17:29.310 回答
1

在第一个示例中：

i将获得值 0, 1, 2, ..., M-1

j将获得值 0, 1, 2, ..., N-1

所以sum计算为

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][N-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][N-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][N-1] +
      ...
      ...
      a[M-1][0] + a[M-1][1] + a[M-1][2] + ... + a[M-1][N-1]

在第二个示例中，这已被切换，以便

i将获得值 0, 1, 2, ..., N-1

j将获得值 0, 1, 2, ..., M-1

所以现在

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][M-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][M-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][M-1] +
      ...
      ...
      a[N-1][0] + a[N-1][1] + a[N-1][2] + ... + a[N-1][M-1]

请注意，第二个版本是错误的，因为参数是int a[M][N]，即合法的第一个索引是0..M-1合法的第二个索引是0..N-1换句话说，如果 N 和 M 不同，则第二个版本访问数组越界。

使第二个示例正确。这条线现在sum+=a[i][j];应该是sum+=a[j][i];这样sum的：

sum = a[0][0] + a[1][0] + a[2][0] + ... + a[M-1][0] +
      a[0][1] + a[1][1] + a[2][1] + ... + a[M-1][1] +
      a[0][2] + a[1][2] + a[2][2] + ... + a[M-1][2] +
      ...
      ...
      a[0][N-1] + a[1][N-1] + a[2][N-1] + ... + a[M-1][N-1]

通过该更改，两个版本在功能上是相同的，即产生相同的结果。它们仅在添加元素的顺序上有所不同。

由于二维数组的内存布局和缓存系统的工作方式，第一个版本的性能可能比第二个更好。另一方面，编译器可能会优化这两个版本以使其性能相同。

于 2018-06-04T08:15:50.993 回答
0

仅当两个代码块不同时，两个代码才相似M，N否则equal两个代码块都不同。

Case-1 :-查看下面的代码块

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
}

这是一个由行和列a组成的数组，您正在对每个行列元素进行求和。这是一个很好的代码，因为外循环旋转等于行数，内循环旋转等于列数。MNsum+=a[i][j]

Case-2 :- 现在看第二个代码块，它会导致溢出。

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
}

这里也是一个行和列a的数组。您的第一个外部 for 循环从to旋转，但您只有行。当你这样做时，如果&不一样，它会产生一个大问题。例如， is和is即它的 like 和外循环从to迭代，你继续做MN0NMsum+=a[i][..]MNM2N5int a[2][5]05

  • sum+=a[0][j]然后

  • sum+=a[1][j]直到这很好（bcz M = 2），但是什么时候可以

  • sum+=a[2][j]等等sum+=a[3][j]然后有一个问题，因为没有a[2][j]或a[3][j]退出所以你试图访问导致未定义行为的边界。

所以以上两个代码块只有当M和相同时才N相同，否则两者不同。

首先第二个代码块是错误的，但你可以通过做sum+=a[j][i]而不是更正它sum+=a[i][j]as

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[j][i];
    return sum;
}

正如其他人所说，由于 2D 数组的内存布局和缓存系统的工作方式，第一个版本可能比第二个版本执行得更好。另一方面，编译器可能会优化这两个版本以使其性能相同。

于 2018-06-04T08:16:35.807 回答