tamaño - recorrer arreglo bidimensional java

Java: matriz multidimensional vs. unidimensional

Question

Por ejemplo:

• a) int [x][y][z]

  vs

• b) int[x*y*z]

Inicialmente pensé que iría con a) por simplicidad

Sé que Java no almacena matrices de forma lineal en la memoria como C lo hace. Pero, ¿qué implicaciones tiene esto para mi programa?

Answer 1

En las CPU actuales, el acceso a la memoria no almacenada en caché es cientos de veces más lento que la aritmética (consulte esta presentación y lea Lo que todo programador debería saber sobre la memoria ). La opción a) dará como resultado aproximadamente 3 búsquedas de memoria mientras que la opción b) dará como resultado aproximadamente 1 búsqueda de memoria. Además, los algoritmos de captación previa de la CPU podrían no funcionar tan bien. Entonces la opción b) puede ser más rápida en algunas situaciones (es un punto caliente y la matriz no cabe en la memoria caché de la CPU). ¿Cuanto más rápido? - Eso dependerá de la aplicación.

Personalmente, primero utilizaría la opción a), porque resultará en un código más simple. Si un perfilador muestra que el acceso a la matriz es un cuello de botella, entonces lo convertiría en la opción b), de modo que haya un par de métodos auxiliares para leer y escribir valores de matriz (de ese modo, el código desordenado se limitará a esos dos métodos).

Hice un punto de referencia para comparar arrays en 3 tridimensionales (columna "Multi") con los arrays int en formato 1idimensional (columna "Single"). El código está here y prueba here . Lo ejecuté en 64 bits jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 a 3.0 GHz, 4 GB DDR2, usando las opciones de JVM -server -Xmx3G -verbose:gc -XX:+PrintCompilation (he eliminado el depurar salida de los siguientes resultados). Los resultados fueron:

Out of 20 repeats, the minimum time in milliseconds is reported.

Array dimensions: 100x100x100 (1000000)
            Multi   Single
Seq Write   1       1
Seq Read    1       1
Random Read 99      90    (of which generating random numbers 59 ms)

Array dimensions: 200x200x200 (8000000)
            Multi   Single
Seq Write   14      13
Seq Read    11      8
Random Read 1482    1239    (of which generating random numbers 474 ms)

Array dimensions: 300x300x300 (27000000)
            Multi   Single
Seq Write   53      46
Seq Read    34      24
Random Read 5915    4418    (of which generating random numbers 1557 ms)

Array dimensions: 400x400x400 (64000000)
            Multi   Single
Seq Write   123     111
Seq Read    71      55
Random Read 16326   11144    (of which generating random numbers 3693 ms)

Esto muestra que la matriz de 1 dimensión es más rápida. Aunque las diferencias son tan pequeñas, eso para el 99% de las aplicaciones no será notorio.

También hice algunas mediciones para estimar la sobrecarga de generar los números aleatorios en el punto de referencia de lectura aleatoria al reemplazar preventOptimizingAway += array.get(x, y, z); con preventOptimizingAway += x * y * z; y agregó las medidas a la tabla de resultados anterior a mano. Generar los números aleatorios toma 1/3 o menos del tiempo total del punto de referencia de lectura aleatoria, por lo que el acceso a memoria domina el punto de referencia como se esperaba. Sería interesante repetir este punto de referencia con matrices de 4 y más dimensiones. Probablemente aumentaría la diferencia de velocidad, porque los niveles superiores de la matriz multidimensional encajarán en la memoria caché de la CPU, y solo los otros niveles requerirán una búsqueda de memoria.

Answer 2

Por lo general, lo mejor que se puede hacer cuando se buscan respuestas para tales preguntas es ver cómo se compilan las elecciones en el bytecode de JVM:

multi = new int[50][50];
single = new int[2500];

Esto se traduce en:

BIPUSH 50
BIPUSH 50
MULTIANEWARRAY int[][] 2
ASTORE 1
SIPUSH 2500
NEWARRAY T_INT
ASTORE 2

Entonces, como puede ver, la JVM ya sabe que estamos hablando de una matriz multidimensional.

Manteniéndolo más lejos:

for (int i = 0; i < 50; ++i)
    for (int j = 0; j < 50; ++j)
    {
        multi[i][j] = 20;
        single[i*50+j] = 20;
    }

Esto se traduce (omitiendo los ciclos) en:

ALOAD 1: multi
ILOAD 3: i
AALOAD
ILOAD 4: j
BIPUSH 20
IASTORE

ALOAD 2: single
ILOAD 3: i
BIPUSH 50
IMUL
ILOAD 4: j
IADD
BIPUSH 20
IASTORE

Entonces, como puede ver, la matriz multidimensional se trata internamente en la VM, sin sobrecarga generada por instrucciones inútiles, mientras que el uso de una sola usa más instrucciones ya que la compensación se calcula a mano.

No creo que el rendimiento sea un problema.

EDITAR:

Hice algunos puntos de referencia simples para ver qué está pasando aquí. Elegí probar diferentes ejemplos: lectura lineal, escritura lineal y acceso aleatorio. Los tiempos se expresan en milisegundos (y se calculan usando System.nanoTime() . Estos son los resultados:

Escritura lineal

• Tamaño: 100x100 (10000) Multi: 5.786591 Individual: 6.131748
• Tamaño: 200x200 (40000) Multi: 1.216366 Individual: 0.782041
• Tamaño: 500x500 (250000) Multi: 7.177029 Individual: 3.667017
• Tamaño: 1000x1000 (1000000) Multi: 30.508131 Individual: 18.064592
• Tamaño: 2000x2000 (4000000) Multi: 185.3548 Individual: 155.590313
• Tamaño: 5000x5000 (25000000) Multi: 955.5299 Individual: 923.264417
• Tamaño: 10000x10000 (100000000) Multi: 4084.798753 Individual: 4015.448829

Lectura lineal

• Tamaño: 100x100 (10000) Multi: 5.241338 Individual: 5.135957
• Tamaño: 200x200 (40000) Multi: 0.080209 Individual: 0.044371
• Tamaño: 500x500 (250000) Multi: 0.088742 Individual: 0.084476
• Tamaño: 1000x1000 (1000000) Multi: 0.232095 Individual: 0.167671
• Tamaño: 2000x2000 (4000000) Multi: 0.481683 Individual: 0.33321
• Tamaño: 5000x5000 (25000000) Multi: 1.222339 Individual: 0.828118 Tamaño: 10000x10000 (100000000) Multi: 2.496302 Individual: 1.650691

Lectura aleatoria

• Tamaño: 100x100 (10000) Multi: 22.317393 Individual: 8.546134
• Tamaño: 200x200 (40000) Multi: 32.287669 Individual: 11.022383
• Tamaño: 500x500 (250000) Multi: 189.542751 Individual: 68.181343
• Tamaño: 1000x1000 (1000000) Multi: 1124.78609 Individual: 272.235584
• Tamaño: 2000x2000 (4000000) Multi: 6814.477101 Individual: 1091.998395
• Tamaño: 5000x5000 (25000000) Multi: 50051.306239 Individual: 7028.422262

El aleatorio es un poco engañoso ya que genera 2 números aleatorios para matriz multidimensional, mientras que solo uno para dimensión única (y los PNRG pueden consumir algo de CPU).

Tenga en cuenta que traté de dejar que JIT funcionara mediante la evaluación comparativa solo después de la 20ª ejecución del mismo ciclo. Para completar mi máquina virtual Java es la siguiente:

Java versión "1.6.0_17" Java (TM) SE Runtime Environment (compilación 1.6.0_17-b04) Java HotSpot (TM) 64-Bit Server VM (compilación 14.3-b01, modo mixto)

Answer 3

Si elige la última ruta, tendrá que realizar aritmética para cada acceso a la matriz. Eso va a ser doloroso y propenso a errores (a menos que lo envuelva en una clase que proporcione esta funcionalidad).

No creo que haya una optimización (significativa) en la elección de su matriz plana (especialmente teniendo en cuenta la aritmética tomada para indexar en ella). Como siempre con las optimizaciones, necesitarías realizar algunas mediciones y determinar si realmente vale la pena.

Answer 4

Utilice la primera variante (tridimensional) porque es más fácil de entender y hay menos posibilidades de cometer algún error lógico (especialmente si lo está utilizando para modelar espacio tridimensional)