处理二维数组的首选方法是什么？

Question

我不擅长java惯例和最佳实践.

我需要二维缓冲区来进行涉及动态编程的大型计算,并怀疑我是否应该使用一维数组并将两个坐标映射到单个,或者使用数组和索引链接访问.

在CI中更喜欢第一种方式,但Java不是C,并且可能具有重要的额外细节.

Answer 1

如果您需要最高速度,请务必使用单个数组(一维)并根据需要映射索引.正如我在你的问题下面的评论中链接的线程中看到的那样,人们似乎忽略了2d阵列对CPU缓存行的不良影响,并且只强调了内存查找的数量.

这里是一个考虑采取:如果你内心的阵列足够大(1K以上,说的),那么速度优势开始渐行渐远.如果内部数组很小(如10-50),那么差异应该是显而易见的.

编辑

正如所要求的,这是我的jmh基准:

@OutputTimeUnit(TimeUnit.SECONDS)
public class ArrayAccess
{
  static final int gapRowsize = 128, rowsize = 32, colsize = 10_000;
  static final int[][] twod = new int[colsize][],
      gap1 = new int[colsize][];
  static final int[] oned = new int[colsize*rowsize];
  static final Random r = new Random();
  static {
    for (int i = 0; i < colsize; i++) {
      twod[i] = new int[rowsize];
      gap1[i] = new int[gapRowsize];
    }
    for (int i = 0; i < rowsize*colsize; i++) oned[i] = r.nextInt();
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        twod[i][j] = r.nextInt();
  }

  @GenerateMicroBenchmark
  public int oned() {
    int sum = 0;
    for (int i = 0; i < rowsize*colsize; i++)
      sum += oned[i];
    return sum;
  }

  @GenerateMicroBenchmark
  public int onedIndexed() {
    int sum = 0;
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        sum += oned[ind(i,j)];
    return sum;
  }

  static int ind(int row, int col) { return rowsize*row+col; }

  @GenerateMicroBenchmark
  public int twod() {
    int sum = 0;
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        sum += twod[i][j];
    return sum;
  }

}

请注意间隙数组分配:这模拟了碎片堆的最坏情况.

我看到在rowsize= 32 处有超过5倍的优势,在1024处仍然非常明显(25%)的优势.我也发现高度依赖于间隙大小的优势,显示128是rowsize= 32 的最坏情况(两者都是更高和更低的值会降低优势),而512则是rowsize= 1024 的最坏情况.

rowsize = 32, gapRowsize = 128

Benchmark    Mean        Units
oned         8857.400    ops/sec
twod         1697.694    ops/sec


rowsize = 1024, gapRowsize = 512

Benchmark   Mean     Units
oned        147.192  ops/sec
twod        118.275  ops/sec