Implementación eficiente de matrices multidimensionales en Java?

Question

Por lo que tengo entendido (de respuestas como this), Java no tiene matrices de memoria continuas multidimensionales nativas (unlike C#, for example).

Si bien la sintaxis de matriz dentada (matrices de matrices) puede ser buena para la mayoría de las aplicaciones, me gustaría saber cuál es la mejor práctica si desea la eficiencia sin procesar de una matriz de memoria continua (evitando lecturas de memoria innecesarias)

Por supuesto, podría usar una matriz unidimensional que se asigna a una 2D, pero prefiero algo más estructurado.

Answer 1

Si realmente quiere más estructura con una matriz de memoria continua, envuélvala en un objeto.

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

} 

No es una solución perfecta, y probablemente ya la conozcas. Así que considere esta confirmación de lo que sospechaba que era cierto.

Java solo proporciona ciertas construcciones para organizar el código, por lo que eventualmente tendrá que buscar una clase o interfaz. Como esto también requiere operaciones específicas, necesitas una clase.

Los impactos en el rendimiento incluyen la creación de un marco de pila JVM para cada acceso a la matriz, y sería ideal evitar tal cosa; sin embargo, un marco de pila JVM es cómo la JVM implementa su alcance. La organización del código requiere un alcance adecuado, por lo que no hay una forma de evitar ese golpe de rendimiento que pueda imaginar (sin violar el espíritu de "todo es un objeto").

Answer 2

no es difícil hacerlo de forma manual:

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

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

ahora, ¿es realmente más rápido que la matriz de dimensión múltiple de java?

int x_i_j = matrix[i][j]; 

para acceso aleatorio, tal vez. para el acceso continuo, probablemente no - matrix[i] es casi seguro en la caché L1, si no en la caché de registro. en el mejor de los casos, matrix[i][j] requiere una adición y una lectura de memoria; mientras que matrix[i*COLS + j] puede costar 2 adiciones, una multiplicación, una lectura de memoria. pero, ¿quién está contando?

Answer 3

Si no puede vivir sin construcciones C, siempre hay JNI.

O podría desarrollar su propio lenguaje derivado de Java (y VM y optimizando el compilador JIT) que tiene una sintaxis para matrices multidimensionales de memoria continua.

Answer 4

Implementación de muestra, sin compilador. Esto es básicamente lo que hace C/C++ detrás de escena cuando accede a arreglos multidimensionales. Tendrá que definir aún más el comportamiento del acceso cuando se especifiquen menos de las dimensiones reales &, etc. La sobrecarga será mínima y podría optimizarse aún más, pero eso es microoptimizar el yo. Además, en realidad nunca se sabe lo que sucede debajo del capó después de que se activa 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]; 
    } 
} 

Answer 5

Depende de su patrón de acceso.Usando this simple program, comparando una int[][] con un 2D mapeada sobre una 1D int[] matriz tratada como una matriz, una matriz de Java 2D nativa es:

1. 25% más rápido cuando la fila está en la memoria caché, es decir: el acceso por filas:
2. 100% más lento cuando la fila no está en la caché, es decir: Acceso por columnas:

es decir:

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

el 1D matriz se calcula como:

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

Answer 6

El método más eficaz de la aplicación de matrices multidimensionales es mediante la utilización de matrices unidimensionales como matrices multidimensionales. Consulte this answer sobre el mapeo de una matriz 2D en una matriz 1D.

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

Podría, por supuesto, utilizar una sola dimensión de matriz que se asigna a una 2D uno, pero yo preferiría algo más estructurado.

Si desea acceder array de una manera más estructurada, crear una clase para ello:

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

} 

Si quería matrices de objetos, puede utilizar los genéricos y definir la clase Array<T>, donde T es el objeto almacenado en la matriz.

En cuanto a rendimiento, esto, en la mayoría de los casos, será más rápido que una matriz multidimensional en Java. Los motivos se pueden encontrar in the answers to this question.

Answer 7

Digamos que tiene una matriz 2D int[][] a = new int[height][width], por lo tanto, por convención, tiene los índices a[y][x]. Dependiendo de cómo se representan los datos y cómo se accede a ellos, el rendimiento varía en un factor de 20:

El código:

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

se puede concluir que el rendimiento de acceso lineal depende más en el camino procesa la matriz (líneas, columnas o el reverso ?: ganancia de rendimiento = x10, mucho debido a cachés de CPU) que la estructura de la matriz en sí (1D frente a 2D: ganancia de rendimiento = x2).

Si el acceso es aleatorio, las diferencias de rendimiento deberían ser mucho menores, ya que las memorias caché de la CPU tienen menos efecto.