representación de una matriz 2D como una matriz 1D

Question

posibles duplicados:
Implementing a matrix, which is more efficient - using an Array of Arrays (2D) or a 1D array?
Performance of 2-dimensional array vs 1-dimensional array

que estaba buscando en una de dinámica molecular de My Buddy código bases el otro día y que había representado a algunos Datos 2D como una matriz 1D. Entonces, en lugar de tener que usar dos índices, solo tiene que hacer un seguimiento de uno, pero se hace un poco de matemática para determinar en qué posición estaría si fuera 2D. Así, en el caso de esta matriz 2D:

two_D = [[0, 1, 2], 
     [3, 4, 5]] 

Sería puede representar como:

one_D = [0, 1, 2, 3, 4, 5] 

Si lo que necesitaba saber lo que había en la posición (1,1) de la matriz 2D que haría algunos álgebra simple y obtener 4.

¿Hay algún aumento en el rendimiento obtenido mediante el uso de una matriz 1D en lugar de una matriz 2D. Los datos en las matrices se pueden llamar millones de veces durante el cálculo.

Espero que la explicación de la estructura de los datos sea clara ... si no me lo diga y trataré de explicarlo mejor.

Gracias :)

EDITAR El lenguaje es C

Answer 1

Tome un vistazo a Performance of 2-dimensional array vs 1-dimensional array

Answer 2

matrices A menudo 2D se implementan como matrices 1D. A veces, las matrices 2D se implementan mediante una matriz 1D de punteros a matrices 1D. El primer caso, obviamente, no tiene ninguna penalización de rendimiento en comparación con una matriz 1D, porque es idéntica a una matriz 1D. El segundo caso podría tener una leve penalización de rendimiento debido a la indirección adicional (y efectos adicionales sutiles como una menor localidad de caché).

Es diferente para cada sistema de qué tipo se utiliza, por lo que sin información sobre lo que está utilizando, realmente no hay manera de estar seguro. Aconsejaría probar el rendimiento solo si es realmente importante para ti. Y si el rendimiento no es tan importante, entonces no te preocupes por eso.

Para C, las matrices en 2D son matrices 1D con azúcar sintáctico, por lo que el rendimiento es idéntico.

Answer 3

Usted no ha mencionado que el lenguaje es con respecto a este o cómo se aplicaría la matriz 2D. En C las matrices 2D se implementan realmente como matrices 1D donde C realiza automáticamente la aritmética en los índices para acceder al elemento correcto. Entonces haría lo que hace tu amigo de todos modos detrás de escena.

En otros idiomas una matriz 2D puede ser un array de punteros a las matrices internas, en cuyo caso el acceso a un elemento sería matriz referencia a un puntero de búsqueda + + matriz de búsqueda, que es probablemente más lento que el cálculo del índice, sin embargo sería no valdrá la pena optimizar a menos que sepa que esto es un cuello de botella.

Answer 4

oneD_index = 3 * y + x; 

Donde x es la posición dentro de la fila ey la posición en la columna. En lugar de 3, usa el ancho de su columna. De esta forma puedes convertir tus coordenadas 2D a una coordenada 1D.

Answer 5

Para un 2-d Matriz de anchura H W y la altura se puede representarla como un 1-d matriz de longitud W * H donde cada índice

(x,y) 

donde x es la columna e Y es la fila, del conjunto de 2 d asignado al índice

i=y*W + x 

en el conjunto 1-D. De manera similar, puede usar el mapeo inverso:

y = i/W 
x = i % W 

. Si realiza W una potencia de 2 (W = 2^m), puede utilizar el hack

y = i >> m; 
x = (i & (W-1)) 

donde esta optimización se limita sólo al caso en el que W es una potencia de 2. Un compilador lo más probable echo de menos esta micro-optimización, así que tendrías que implementarla tú mismo.

El módulo es un operador lento en C/C++, por lo que hacerlo desaparecer es una ventaja.

Además, con matrices grandes de 2-d, tenga en cuenta que la computadora las almacena en la memoria como una matriz de 1-d y básicamente descifra los índices usando las asignaciones que enumeré arriba.

Mucho más importante que la forma en que determina estas asignaciones es cómo se accede a la matriz. Hay dos formas de hacerlo, columna principal y fila mayor. La forma en que atraviesa es más importante que que cualquier otro factor porque determina si está usando el almacenamiento en caché para su ventaja. Por favor, lea http://en.wikipedia.org/wiki/Row-major_order.