Supponiamo che tu abbia un array 2D int[][] a = new int[height][width]
, quindi per convenzione hai gli indici a[y][x]
. A seconda di come rappresentare i dati e come vi si accede, la prestazione varia in un fattore di 20:
Il codice:
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");
}
}
si può concludere che le prestazioni di accesso lineare dipende più nel modo in cui elabori l'array (righe e colonne o il contrario ?: performance gain = x10, molto dovuto alle cache della CPU) rispetto alla struttura stessa dell'array (1D vs 2D: guadagno di prestazioni = x2).
Se l'accesso casuale, le differenze di prestazioni dovrebbero essere molto inferiori, perché le cache della CPU hanno un effetto minore.
fonte
2017-06-04 12:40:27
Mi sento come se tu fossi micro ottimizzazione. La mappatura di un array 1d su un array 2d rimuove solo la ricerca di 1 array. Non posso immaginare che ti salverà molto/in qualsiasi momento. – jjnguy
Se hai bisogno di un po 'di prestazioni, potresti essere più adatto a usare C o C++. – helpermethod
In quali circostanze pensi che avere ogni fila di un array bidimensionale contiguo con il prossimo in memoria sia * significativamente * più efficiente del normale array di array di Java? –