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

Question

我不擅长 Java 约定和最佳实践。

我需要二维缓冲区来进行一些涉及动态规划的大型计算，并且怀疑我是否应该使用一维数组并将两个坐标映射到单个坐标，或者使用数组的数组并通过索引进行链式访问。

在 C 中，我更喜欢第一种方式，但 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