1

Java の規則やベスト プラクティスが苦手です。

動的プログラミングを含む大きな計算には 2 次元バッファーが必要で、1 次元配列を使用して 2 つの座標を単一にマップするか、配列の配列とインデックスによる連鎖アクセスを使用するかを疑っています。

CIでは最初の方法が好まれますが、JavaはCではなく、重要な追加の仕様がある場合があります。

4

1 に答える 1

6

最高速度が必要な場合は、必ず単一の配列 (1 次元) を使用し、必要に応じてインデックスをマップしてください。あなたの質問の下のコメントにリンクされているスレッドに見られるように、人々はCPUキャッシュラインに対する2次元配列の悪影響を無視し、メモリルックアップの数だけを強調しているようです.

考慮すべき点が1 つあります。内部配列が十分に大きい場合 (たとえば 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;
  }

}

ギャップ配列の割り当てに注意してください。これは、断片化されたヒープで最悪のシナリオをシミュレートします。

= 32では 5 倍以上のrowsize利点があり、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
于 2013-11-08T18:22:02.997 に答える