2011-02-10 19 views
5

Per quanto ho capito (da risposte come this), java non ha matrici di memoria continua multi-dimensionale native (unlike C#, for example).Implementazione efficiente di array multidimensionali in Java?

Mentre la sintassi di array frastagliata (array di matrici) potrebbe essere buona per la maggior parte delle applicazioni, mi piacerebbe comunque sapere qual è la procedura migliore se si desidera l'efficienza raw di una matrice di memoria continua (evitando letture di memoria non necessarie)

Ovviamente potrei usare una matrice monodimensionale che si associa a una 2D, ma preferisco qualcosa di più strutturato.

+4

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

+0

Se hai bisogno di un po 'di prestazioni, potresti essere più adatto a usare C o C++. – helpermethod

+0

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? –

risposta

3

Se vuoi davvero più struttura con una matrice di memoria continua, avvolgila in un oggetto.

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]; 
    } 

} 

Non è una soluzione perfetta, e probabilmente lo sai già. Quindi considera questa conferma di ciò che sospetti di essere vero.

Java fornisce solo determinati costrutti per l'organizzazione del codice, quindi alla fine dovrete raggiungere una classe o un'interfaccia. Poiché ciò richiede anche operazioni specifiche, è necessario un corso.

Gli impatti delle prestazioni includono la creazione di un frame stack JVM per ciascun accesso di array e sarebbe ideale evitare una cosa del genere; tuttavia, un frame dello stack JVM è in cui la JVM implementa il suo ambito. L'organizzazione del codice richiede un ambito appropriato, quindi non c'è un modo per aggirare quel successo di prestazioni che posso immaginare (senza violare lo spirito di "tutto è un oggetto").

+2

Puoi anche generalizzare e rilasciare il "2D" e inserire le dimensioni come argomento var-arg per il costruttore (e lasciare che 'elementAt' prenda un var-arg per gli indici) – aioobe

+1

True, ma l'esempio dimostra l'idea chiave . Le probabilità sono buone, ha in mente una matrice dimensionale specifica. –

5

non è difficile farlo manualmente:

int[] matrix = new int[ROWS * COLS]; 

int x_i_j = matrix[ i*COLS + j ]; 

ora, è davvero più veloce di serie dimensione a più di Java?

int x_i_j = matrix[i][j]; 

per accesso casuale, forse. per l'accesso continuo, probabilmente no - matrix[i] è quasi certamente nella cache L1, se non nella cache del registro. nello scenario migliore, matrix[i][j] richiede un'aggiunta e una lettura di memoria; mentre matrix[i*COLS + j] può costare 2 aggiunte, una moltiplicazione, una lettura di memoria. ma chi sta contando?

+1

Con un singolo array, tuttavia, eseguirai solo il controllo dei limiti una volta anziché due. –

+0

se l'ottimizzazione memorizza nella cache la matrice [i], è un controllo meno vincolato. – irreputable

-1

Se non puoi vivere senza costrutti C, c'è sempre JNI.

Oppure è possibile sviluppare il proprio linguaggio derivato da Java (e VM e ottimizzando il compilatore JIT) che ha una sintassi per array di memoria continua multidimensionale.

1

Implementazione di esempio, senza un compilatore. Questo è fondamentalmente ciò che C/C++ fa dietro le quinte quando si accede a matrici multidimensionali. Dovrai definire ulteriormente il comportamento di accesso quando vengono specificate meno delle dimensioni effettive & così via. L'overhead sarà minimo e potrebbe essere ulteriormente ottimizzato, ma questo è il microottimismo. Inoltre, non sai mai cosa succede sotto la cappa dopo che JIT ha preso il via.

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]; 
    } 
} 
4

Dipende dal tuo modello di accesso.Utilizzando this simple program, confrontando un int[][] con un 2D mappata su una 1D int[] matrice trattata come una matrice, una matrice nativa Java 2D è:

  1. 25% più velocemente quando la riga è sulla cache, ossia: accesso per righe:
  2. 100% più lento quando la riga non è presente nella cache, ossia: accedendo da colonne:

cioè:

// 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] 

il 1D matrice viene calcolata come:

public int get(int x, int y) { 
    return this.m[y * width + x]; 
} 
+0

bello. quindi l'ottimizzazione di vm non è così intelligente come pensavo. – irreputable

+0

Al contrario, JIT ottimizza le chiamate ai metodi più che semplicemente li incorpora. Chiamare il metodo get (x, y) è più veloce che accedere direttamente alla matrice dall'esterno. – vz0

0

Il metodo più efficace per implementare array multidimensionali è utilizzando matrici unidimensionali come array multidimensionali. Vedere this answer sulla mappatura di un array 2D in un array 1D.

// 2D data structure as 1D array 
int[] array = new int[width * height]; 
// access the array 
array[x + y * width] = /*value*/; 

potrei naturalmente utilizzare un array monodimensionale associato a un 2D, ma preferisco qualcosa di più strutturato.

Se si desidera accedere array in modo più strutturato, creare una classe per esso:

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; 
    } 

} 

Se si voleva array di oggetti, è possibile utilizzare farmaci generici e definire classe Array<T>, dove T è l'oggetto memorizzato nell'array.

Per quanto riguarda le prestazioni, nella maggior parte dei casi questo sarà più veloce di un array multidimensionale in Java. I motivi possono essere trovati in the answers to this question.

0

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:

comparison of 2D array access

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.

Problemi correlati