私の知る限りでは（thisなどの回答から）、Javaにはネイティブの多次元連続メモリ配列（unlike C#, for example）はありません。Javaで多次元配列を効率的に実装するには？
ギザギザの配列構文（配列の配列）はほとんどのアプリケーションにとっては良いかもしれませんが、連続メモリ配列の生の効率を必要とする場合（ベストプラクティスを知りたいと思います）
もちろん、2D配列にマップする1次元配列を使用できますが、私はもっと構造化されたものを好むでしょう。
連続したメモリ配列を持つ構造体を実際に作成するには、オブジェクトにラップします。
public class My2dArray<T> {
int sizeX;
private T[] items;
public My2dArray(int x, int y) {
sizeX = x;
items = new T[x*y];
}
public T elementAt(int x, int y) {
return items[x+y*sizeX];
}
}
あなたはおそらく既にそれを知っているでしょう。したがって、あなたが真実であると疑ったことのこの確認を考慮してください。
Javaでは、コードを整理するための特定の構造体しか提供されないため、最終的にはクラスまたはインタフェースに到達する必要があります。これには特定の操作も必要なので、クラスが必要です。
パフォーマンスへの影響には、アレイアクセスごとにJVMスタックフレームを作成することが含まれます。このようなことは避けるのが理想的です。ただし、JVMスタックフレームはです。 JVMがスコープを実装しています。コードの構成には適切なスコープが必要なので、私は想像することのできないパフォーマンスヒットを回避する方法はありません（「すべてが目的」という精神に反することなく）。
また、 "2D"を一般化して削除し、var-arg引数としてディメンションをコンストラクタに渡すこともできます（そして、 'elementAt'はインデックスに対してvar-argを取るようにしてください）。 – aioobe
真ですが、 。確かに、彼は特定の次元の配列を念頭に置いて良いです。 –
それは手動でそれを行うには難しいことではありません。
int[] matrix = new int[ROWS * COLS];
int x_i_j = matrix[ i*COLS + j ];
を今、それは本当にJavaのマルチ次元配列よりも速いのですか？
int x_i_j = matrix[i][j];
ランダムアクセス用です。おそらくは - matrix[i]は、レジスタキャッシュにないと、ほぼ確実にL1キャッシュに入ります。最適なシナリオでは、matrix[i][j]には1回の加算と1回のメモリ読み出しが必要です。 matrix[i*COLS + j]は2加算、1乗算、1メモリ読み出しのコストがかかる場合があります。誰が数えていますか？
しかし、1つの配列では、境界チェックは2回ではなく1回だけ行います。 –
最適化キャッシュmatrix [i]の場合は、バインドされていないチェックが少なくなります。 – irreputable
Cのコンストラクタなしでは使用できない場合は、常にJNIがあります。
多次元連続メモリ配列の構文を持つ独自のJava派生言語（およびVMと最適化JITコンパイラ）を開発することもできます。
コンパイラを使用しないサンプル実装。これは基本的に、多次元配列にアクセスするときにC/C++が背後で行うことです。実際の寸法が&以下に指定されている場合は、アクセサーの動作をさらに定義する必要があります。オーバーヘッドは最小限に抑えられ、さらに最適化される可能性がありますが、imhoをマイクロ最適化することは可能です。また、あなたが実際にJITキックの後にフードの下に行くかを知ることはありません。
class MultiDimentionalArray<T> {
//disclaimer: written within SO editor, might contain errors
private T[] data;
private int[] dimensions; //holds each dimensions' size
public MultiDimensionalArray(int... dims) {
dimensions = Arrays.copyOf(dims, dims.length);
int size = 1;
for(int dim : dims)
size *= dim;
data = new T[size];
}
public T access(int... dims) {
int idx = 1;
for(int i = 0; i < dims.length)
idx += dims[i] * dimensions[i]; //size * offset
return data[idx];
}
}
は、それはあなたのアクセスパターンに依存します。2Dは、マトリックスとして扱わ1D int[]アレイ上でマッピングされたとint[][]とを比較する、this simple program使用して、ネイティブJava 2D行列である：
すなわち：
// Case #1
for (y = 0; y < h; y++)
for (x = 0; x < w; x++)
// Access item[y][x]
// Case #2
for (x = 0; x < w; x++)
for (y = 0; y < h; y++)
// Access item[y][x]
1D
public int get(int x, int y) {
return this.m[y * width + x];
}
nice。 VMの最適化は私が思ったほどスマートではありません。 – irreputable
逆に、JITはメソッド呼び出しを単なるインライン化よりも最適化します。 get（x、y）メソッドを呼び出す方が、行列を外部から直接アクセスするよりも高速です。 – vz0
多次元配列を実装する最も効率的な方法は、1次元配列を多次元配列として利用することです。 2D配列を1D配列にマッピングする方法については、this answerを参照してください。
// 2D data structure as 1D array
int[] array = new int[width * height];
// access the array
array[x + y * width] = /*value*/;
私はもちろん、2D 1にマップの単一次元配列を使用することができますが、私は何かをより構造化好みます。
あなたはそれのためのクラスを作成し、より構造化された方法でarrayにアクセスする場合：
public class ArrayInt {
private final int[] array;
private final int width, height;
public ArrayInt(int width, int height) {
array = new int[width * height];
this.width = width;
this.height = height;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
public int get(int x, int y) {
return array[x + y * width];
}
public void set(int x, int y, int value) {
array[x + y * width] = value;
}
}
あなたがオブジェクトの配列を望んでいた場合は、ジェネリックを使用し、TがあるクラスArray<T>を、定義することができ配列に格納されているオブジェクト
パフォーマンス面では、ほとんどの場合、これはJavaの多次元配列より高速です。理由はin the answers to this questionです。
2D配列int[][] a = new int[height][width]があるとしましょう。慣例により、インデックスはa[y][x]です。あなたはデータを表し、あなたがそれらにアクセスする方法方法に応じて、パフォーマンスが20倍に変化：
コード：
public class ObjectArrayPerformance {
public int width;
public int height;
public int m[];
public ObjectArrayPerformance(int w, int h) {
this.width = w;
this.height = h;
this.m = new int[w * h];
}
public int get(int x, int y) {
return this.m[y * width + x];
}
public void set(int x, int y, int value) {
this.m[y * width + x] = value;
}
public static void main (String[] args) {
int w = 1000, h = 2000, passes = 400;
int matrix[][] = new int[h][];
for (int i = 0; i < h; ++i) {
matrix[i] = new int[w];
}
long start;
long duration;
System.out.println("duration[ms]\tmethod");
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
matrix[y][x] = matrix[y][x] + 1;
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\t2D array, loop on x then y");
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int x = 0; x < w; x++) {
for (int y = 0; y < h; y++) {
matrix[y][x] = matrix[y][x] + 1;
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\t2D array, loop on y then x");
//
ObjectArrayPerformance mt = new ObjectArrayPerformance(w, h);
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int x = 0; x < w; x++) {
for (int y = 0; y < h; y++) {
mt.set(x, y, mt.get(x, y) + 1);
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\tmapped 1D array, access trough getter/setter");
//
ObjectArrayPerformance mt2 = new ObjectArrayPerformance(w, h);
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int x = 0; x < w; x++) {
for (int y = 0; y < h; y++) {
mt2.m[y * w + x] = mt2.m[y * w + x] + 1;
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop y then x");
ObjectArrayPerformance mt3 = new ObjectArrayPerformance(w, h);
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
mt3.m[y * w + x] = mt3.m[y * w + x] + 1;
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop x then y");
ObjectArrayPerformance mt4 = new ObjectArrayPerformance(w, h);
start = System.currentTimeMillis();
for (int z = 0; z < passes; z++) {
for (int y = 0; y < h; y++) {
int yIndex = y * w;
for (int x = 0; x < w; x++) {
mt4.m[yIndex + x] = mt4.m[yIndex + x] + 1;
}
}
}
duration = System.currentTimeMillis() - start;
System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop x then y, yIndex optimized");
}
}
私たちは、線形アクセス性能がより多くを依存していることを結論付けることができます（1D対2D：パフォーマンス・ゲイン= x2）よりも、配列（行数、列数、または逆数：パフォーマンス・ゲイン= x10、CPUキャッシュに起因する）を処理する方法について説明します。
ランダムアクセスの場合、CPUキャッシュの影響が少ないため、パフォーマンスの差ははるかに小さくなるはずです。
私はあなたがマイクロ最適化しているように感じます。 1d配列を2次元配列にマッピングすると、1つの配列参照のみが削除されます。私はそれがあなた/多くの時間を節約するだろうと想像することはできません。 – jjnguy
すべてのパフォーマンスが必要な場合は、CまたはC++を使用する方が適しています。 – helpermethod
どのような状況では、2次元配列の各行をメモリ内の次の配列と連続させると、Javaの通常の配列配列よりも大幅に*効率が上がると思いますか？ –