Por ejemplo:Java: matriz multi-dimensional vs. unidimensional
una)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?
Por lo general, lo mejor que hacer en la búsqueda anwers para este tipo de preguntas es ver cómo las decisiones son compiladas en bytecode 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.
Manteniendo aún más:
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 (se pierden 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
Así, como se puede ver, la matriz multidimensional es tratada internamente en la VM, sin gastos indirectos generados por instrucciones inútiles, mientras usa uno solo usa más instrucciones ya que el desplazamiento se calcula a mano.
No creo que el rendimiento sea un problema.
EDIT:
hice algunos puntos de referencia simples para ver lo que 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(). Éstos son los resultados:
lineal escribir
lineal leer
de lectura aleatoria
El azar 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).
Ten en cuenta que traté de dejar que JIT funcione mediante la evaluación comparativa solo después de la 20ª ejecución del mismo ciclo. Para completar mi máquina virtual de Java es la siguiente:
java version "1.6.0_17" Java (TM) SE Runtime Environment (build 1.6.0_17-b04) Java HotSpot (TM) de 64 bits del servidor VM (construir 14.3-b01, modo mixto)
Siempre es agradable ver a alguien mirar la realidad bajo el capó en lugar de solo hacer suposiciones. Te daría +100 si pudiera. –
Para cuando se juntó el código, el número de instrucciones JVM es irrelevante. Lo que importa es la cantidad de tiempo real que tarda el código en ejecutarse, lo que dependerá de cosas como la localidad, la desreferenciación y el uso de la memoria. – Gabe
Actualice la referencia de lectura aleatoria para que genere 2 números aleatorios para ambas versiones. Probablemente, la versión de matriz única sea incluso más rápida, ya que requiere menos búsquedas de memoria (la lectura aleatoria producirá la mayoría de las fallas de caché), pero nunca se puede estar seguro antes de medirla. –
Si elige la última ruta, entonces 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.
Ok, gracias. Solo voy a usar una matriz tridimensional, y si tengo problemas de rendimiento con ella hago una comparación. – Mikolan
Si usa una matriz multidimensional, tendrá que realizar varios accesos de memoria para cada acceso a la matriz, lo que me podría * buch * más lento que una pequeña aritmética. Pero sí, con este tipo de cosas que realmente necesitas medir antes de actuar. –
Uso primera variante (3 dimensiones) porque es más fácil de entender y hay menos posibilidades de cometer un error lógico (especialmente si usted lo está utilizando para modelar el espacio de 3 dimensiones)
En las CPUs actuales, el acceso sin almacenamiento en caché de memoria es cientos de veces más lenta que la aritmética (véase this presentation y leer What every programmer should know about memory). 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), ya que 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 arreglos int tridimensionales (columna "Multi") con los arreglos int 1idimensionales equivalentes (columna "Single"). El código es 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, utilizando las opciones de JVM -server -Xmx3G -verbose:gc -XX:+PrintCompilation (eliminé la salida de depuración 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 el conjunto unidimensional es más rápido. Aunque las diferencias son tan pequeñas, eso para el 99% de las aplicaciones no será notorio.
También realicé algunas mediciones para estimar la sobrecarga de generar los números aleatorios en la prueba comparativa de lectura aleatoria al reemplazar preventOptimizingAway += array.get(x, y, z); con preventOptimizingAway += x * y * z; y agregué las mediciones 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.
Ver también: http://stackoverflow.com/questions/2368761/performance-comparison-of-array-of-arrays-vs-multidimensional-arrays – polygenelubricants