2

我有 2 个 100s*100s 的大型二维数组。它有一个大循环可以多次执行操作。里面有3个循环；第一个循环存储在arr1每个单元格的总和arr2乘以数字，第二个循环将 2 个数组流式传输到一个文件，第三个循环存储在arr2两个数组的总和除以数字。

代码解释得更好：

for(int i=1;i<x+1;i++) {//initialize
    for(int j=1;j<y+1;j++) {
        arr1[i][j]=i*j*5.5;
        arr2[i][j]=0.;
    }
}

for (int i=0;i<x+2;i++) {//padding
    vi[i][0]=5;
    vi[i][y+1]=-5;
}

for (int j=0;j<y+2;j++) {//padding
    vi[0][j]=10.;
    vi[x+1][j]=-10.;
}

for(int t=0;t<times;++t) {
    for(int i=1;i<x+1;++i) {
        for(int j=1;j<y+1;j++) {
            arr2[i][j]=(arr1[i+1][j]+arr1[i-1][j]+arr1[i][j-1]+arr1[i][j+1])*1.5;
        }
    }

    arr2[1][1]=arr2[1][y]=arr2[x][1]=arr2[x][y]=0.;

    for(int i=1;i<x+1;++i) {
        for(int j=1;j<y+1;j++) {
            arr1[i][j]=(arr1[i][j]+arr2[i][j])*0.5;

            if(arr2[i][j]+arr1[i][j]>5.)
                cout<<"\n"<<t<<"  "<<i-1<<" "<<j-1<<" "<<arr1[i][j]<<" "<<arr2[i][j];
        }
    }
}

整个代码的工作时间超过 14 秒。我应该如何优化代码以尽可能快地工作。

4

2 回答 2

1

注意：响应有关填充等的评论，OP 的代码发生了巨大变化。原始代码实际上没有任何问题——这就是我基于这个答案的原因。

假设您的 2D 数组以行为主索引（第一个索引是行，第二个索引是列），您的内存访问已经按照正确的顺序进行，以获得最佳缓存利用率（您正在访问附近的元素） . 您的最新代码对这个假设提出了质疑，因为您似乎已将“maxi”重命名为“x”，这表明您正在索引一个以列为主的二维数组（这对于 C/C++ 来说是非常非标准的）。

没有指定您如何声明 2D 数组，这可能会有所不同，但是通过将您的实现转换为使用 raw pointers ，我得到了很大的改进。我还通过组合操作并为每次迭代交替方向来消除第二个循环（来自您的原始帖子）。我更改了加权系数，使它们加起来为 1.0，以便我可以更轻松地测试它（通过生成图像输出）。

typedef std::vector< std::vector<double> > Array2D;

void run( int x, Array2D & arr2 )
{

   Array2D temp = arr2; // easy way to create temporary array of the correct size

   int maxi=arr2.size(), maxj=arr2[0].size();

   for (int n=0;n<x;n++)
   {
      Array2D const & src = (n&1)?temp:arr2; // alternate direction
      Array2D & dst = (n&1)?arr2:temp;
      for (int i=1;i<maxi-1;i++)
      {
         double const * sp0=&src[i-1][1], * sp1=&src[i][1], * sp2=&src[i+1][1];
         double * dp=&dst[i][1];
         for (int j=1;j<maxj-1;j++)
         {
            dp[0]=(sp0[0]+sp1[-1]+4*sp1[0]+sp1[+1]+sp2[0])*0.125;
            dp++, sp0++, sp1++, sp2++;
         }
      }
   }

   if ( (x&1) ) arr2=temp; // copy the result back if the iteration count was odd
} /**/

您可以查看的其他内容（有点依赖于平台）：

  • restrict指针关键字（非标准 C++）
  • 预取请求——一种减少内存访问延迟的编译器/处理器特定的方法
  • 确保在编译时启用了优化
  • 根据数组的大小，您可能会发现对算法进行列化以更好地利用可用缓存是有利的

利用可用的计算资源（非常依赖于平台）：

  • 创建基于SIMD的实现
  • 充分利用您的多核 CPU——OpenMP
  • 充分利用您的 GPU——OpenCL
于 2013-04-28T03:44:51.757 回答
1

您可以使用第三个数组临时存储 arr2 的数组值以供下次运行。第一个循环完成后，您使用临时数组覆盖 arr2 - 像这样您不需要第二个循环。您将节省一半的时间。

for (n=0;n<x;n++)
{
   for (i=0;i<maxi;i++)
   {
      for (j=0;j<maxj;j++)
      {
         arr1[i][j]=(arr2[i+1][j]+arr2[i-1][j]+arr2[i][j+1]+arr2[i][j-1])*1.5;
         arr_tmp[i][j] = (arr1[i][j]+arr2[i][j])*0.5;
      }
   }
   arr2 = arr_tmp;
}
于 2013-04-28T01:46:11.390 回答