¿Cuáles son las diferencias entre una matriz multidimensional y una matriz de matrices en C #?

¿Cuáles son las diferencias entre las matrices multidimensionales double[,] y array-of-arrays double[][] en C #?

Si hay una diferencia, ¿cuál es el mejor uso para cada uno?

La matriz de matrices (matrices dentadas) es más rápida que las matrices multidimensionales y se puede usar de manera más efectiva. Las matrices multidimensionales tienen una syntax más agradable.

Si escribe un código simple utilizando matrices dentadas y multidimensionales y luego inspecciona el ensamblado comstackdo con un desensamblador IL, verá que el almacenamiento y la recuperación de arreglos dentados (o unidimensionales) son simples instrucciones IL mientras que las mismas operaciones para matrices multidimensionales son métodos invocaciones que son siempre más lentas

Considere los siguientes métodos:

 static void SetElementAt(int[][] array, int i, int j, int value) { array[i][j] = value; } static void SetElementAt(int[,] array, int i, int j, int value) { array[i, j] = value; } 

Su IL será la siguiente:

 .method private hidebysig static void SetElementAt(int32[][] 'array', int32 i, int32 j, int32 'value') cil managed { // Code size 7 (0x7) .maxstack 8 IL_0000: ldarg.0 IL_0001: ldarg.1 IL_0002: ldelem.ref IL_0003: ldarg.2 IL_0004: ldarg.3 IL_0005: stelem.i4 IL_0006: ret } // end of method Program::SetElementAt .method private hidebysig static void SetElementAt(int32[0...,0...] 'array', int32 i, int32 j, int32 'value') cil managed { // Code size 10 (0xa) .maxstack 8 IL_0000: ldarg.0 IL_0001: ldarg.1 IL_0002: ldarg.2 IL_0003: ldarg.3 IL_0004: call instance void int32[0...,0...]::Set(int32, int32, int32) IL_0009: ret } // end of method Program::SetElementAt 

Al usar matrices irregulares, puede realizar fácilmente operaciones como cambio de fila y cambio de tamaño de fila. Tal vez en algunos casos el uso de matrices multidimensionales sea más seguro, pero incluso Microsoft FxCop dice que las matrices dentadas deberían usarse en lugar de las multidimensionales cuando las usa para analizar sus proyectos.

Una matriz multidimensional crea una buena disposición de memoria lineal, mientras que una matriz dentada implica varios niveles adicionales de indirección.

Buscando el valor jagged[3][6] en una matriz dentada var jagged = new int[10][5] funciona así: Busca el elemento en el índice 3 (que es una matriz) y busca el elemento en el índice 6 en esa matriz (que es un valor). Para cada dimensión en este caso, hay una búsqueda adicional (este es un patrón de acceso a la memoria caro).

Una matriz multidimensional se presenta linealmente en la memoria, el valor real se encuentra al multiplicar los índices. Sin embargo, dada la matriz var mult = new int[10,30] , la propiedad Length de esa matriz multidimensional devuelve la cantidad total de elementos, es decir, 10 * 30 = 300.

La propiedad Rank de una matriz dentada es siempre 1, pero una matriz multidimensional puede tener cualquier rango. El método GetLength de cualquier matriz se puede usar para obtener la longitud de cada dimensión. Para la matriz multidimensional en este ejemplo, mult.GetLength(1) devuelve 30.

La indexación de la matriz multidimensional es más rápida. por ejemplo, dada la matriz multidimensional en este ejemplo mult[1,7] = 30 * 1 + 7 = 37, obtenga el elemento en ese índice 37. Este es un mejor patrón de acceso a la memoria porque solo está involucrada una ubicación de memoria, que es la base dirección de la matriz.

Por lo tanto, una matriz multidimensional asigna un bloque de memoria continuo, mientras que una matriz dentada no tiene que ser cuadrada, p. Ej jagged[1].Length no tiene que ser jagged[2].Length , lo que sería cierto para cualquier matriz multidimensional.

Actuación

En cuanto al rendimiento, las matrices multidimensionales deberían ser más rápidas. Mucho más rápido, pero debido a una implementación de CLR realmente mala, no lo son.

  23.084 16.634 15.215 15.489 14.407 13.691 14.695 14.398 14.551 14.252 25.782 27.484 25.711 20.844 19.607 20.349 25.861 26.214 19.677 20.171 5.050 5.085 6.412 5.225 5.100 5.751 6.650 5.222 6.770 5.305 

La primera fila son los tiempos de las matrices irregulares, la segunda muestra las matrices multidimensionales y la tercera, así es como debería ser. El progtwig se muestra a continuación, para su información, esto se probó ejecutando mono. (Los tiempos de Windows son muy diferentes, principalmente debido a las variaciones de implementación de CLR).

En Windows, los tiempos de las matrices irregulares son muy superiores, casi lo mismo que mi propia interpretación de cómo debe ser la apariencia de la matriz multidimensional, vea ‘Single ()’. Lamentablemente, el comstackdor JIT de Windows es realmente estúpido, y desafortunadamente hace que estas discusiones de rendimiento sean difíciles, hay demasiadas incoherencias.

Estos son los tiempos que obtuve en Windows, el mismo trato aquí, la primera fila son arreglos irregulares, la segunda multidimensional y la tercera mi propia implementación de multidimensional, observe cuánto más lento es esto en Windows en comparación con el mono.

  8.438 2.004 8.439 4.362 4.936 4.533 4.751 4.776 4.635 5.864 7.414 13.196 11.940 11.832 11.675 11.811 11.812 12.964 11.885 11.751 11.355 10.788 10.527 10.541 10.745 10.723 10.651 10.930 10.639 10.595 

Código fuente:

 using System; using System.Diagnostics; static class ArrayPref { const string Format = "{0,7:0.000} "; static void Main() { Jagged(); Multi(); Single(); } static void Jagged() { const int dim = 100; for(var passes = 0; passes < 10; passes++) { var timer = new Stopwatch(); timer.Start(); var jagged = new int[dim][][]; for(var i = 0; i < dim; i++) { jagged[i] = new int[dim][]; for(var j = 0; j < dim; j++) { jagged[i][j] = new int[dim]; for(var k = 0; k < dim; k++) { jagged[i][j][k] = i * j * k; } } } timer.Stop(); Console.Write(Format, (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond); } Console.WriteLine(); } static void Multi() { const int dim = 100; for(var passes = 0; passes < 10; passes++) { var timer = new Stopwatch(); timer.Start(); var multi = new int[dim,dim,dim]; for(var i = 0; i < dim; i++) { for(var j = 0; j < dim; j++) { for(var k = 0; k < dim; k++) { multi[i,j,k] = i * j * k; } } } timer.Stop(); Console.Write(Format, (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond); } Console.WriteLine(); } static void Single() { const int dim = 100; for(var passes = 0; passes < 10; passes++) { var timer = new Stopwatch(); timer.Start(); var single = new int[dim*dim*dim]; for(var i = 0; i < dim; i++) { for(var j = 0; j < dim; j++) { for(var k = 0; k < dim; k++) { single[i*dim*dim+j*dim+k] = i * j * k; } } } timer.Stop(); Console.Write(Format, (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond); } Console.WriteLine(); } } 

Simplemente coloque matrices multidimensionales que son similares a una tabla en DBMS.
Array of Array (matriz dentada) le permite a cada elemento tener otra matriz del mismo tipo de longitud variable.

Entonces, si está seguro de que la estructura de los datos se ve como una tabla (filas / columnas fijas), puede usar una matriz multidimensional. La matriz dentada son elementos fijos y cada elemento puede contener una matriz de longitud variable

Por ejemplo, Psuedocode:

 int[,] data = new int[2,2]; data[0,0] = 1; data[0,1] = 2; data[1,0] = 3; data[1,1] = 4; 

Piense en lo anterior como una tabla de 2×2:

 1 | 2 3 | 4 
 int[][] jagged = new int[3][]; jagged[0] = new int[4] { 1, 2, 3, 4 }; jagged[1] = new int[2] { 11, 12 }; jagged[2] = new int[3] { 21, 22, 23 }; 

Piense en lo anterior ya que cada fila tiene una cantidad variable de columnas:

  1 | 2 | 3 | 4 11 | 12 21 | 22 | 23 

Prefacio: Este comentario tiene como objective abordar la respuesta proporcionada por okutane , pero debido al sistema de reputación tonto de SO, no puedo publicarlo donde corresponde.

Su afirmación de que uno es más lento que el otro debido a las llamadas al método no es correcto. Uno es más lento que el otro debido a los algoritmos de comprobación de límites más complicados. Puede verificar esto fácilmente mirando, no a la IL, sino al ensamblado comstackdo. Por ejemplo, en mi instalación 4.5, acceder a un elemento (mediante puntero en edx) almacenado en una matriz bidimensional apuntada por ecx con índices almacenados en eax y edx tiene el siguiente aspecto:

 sub eax,[ecx+10] cmp eax,[ecx+08] jae oops //jump to throw out of bounds exception sub edx,[ecx+14] cmp edx,[ecx+0C] jae oops //jump to throw out of bounds exception imul eax,[ecx+0C] add eax,edx lea edx,[ecx+eax*4+18] 

Aquí puede ver que no hay sobrecarga de llamadas de método. La comprobación de límites es muy intrincada gracias a la posibilidad de índices distintos de cero, que es una funcionalidad que no se ofrece con matrices irregulares. Si eliminamos los sub, cmp y jmps para casos distintos de cero, el código prácticamente se resuelve en (x*y_max+y)*sizeof(ptr)+sizeof(array_header) . Este cálculo es más o menos rápido (una multiplicación podría reemplazarse por un cambio, ya que esa es la razón por la que elegimos los bytes que se deben dimensionar como potencias de dos bits) como cualquier otra cosa para el acceso aleatorio a un elemento.

Otra complicación es que hay muchos casos en los que un comstackdor moderno optimizará los límites nesteds, verificando el acceso a los elementos mientras itera sobre una matriz de una sola dimensión. El resultado es un código que básicamente avanza un puntero de índice sobre la memoria contigua de la matriz. La iteración ingenua sobre matrices multidimensionales generalmente implica una capa adicional de lógica anidada, por lo que es menos probable que un comstackdor optimice la operación. Por lo tanto, aunque la sobrecarga de comprobación de límites para acceder a un único elemento se amortiza a tiempo de ejecución constante con respecto a las dimensiones y tamaños de matriz, un caso de prueba simple para medir la diferencia puede tardar mucho más tiempo en ejecutarse.

Me gustaría actualizar sobre esto, porque las matrices multidimensionales .NET Core son más rápidas que las matrices dentadas . Ejecuté las pruebas de John Leidegren y estos son los resultados de la vista previa de .NET Core 2.0 2. Aumenté el valor de la dimensión para que las posibles influencias de las aplicaciones en segundo plano sean menos visibles.

 Debug (code optimalization disabled) Running jagged 187.232 200.585 219.927 227.765 225.334 222.745 224.036 222.396 219.912 222.737 Running multi-dimensional 130.732 151.398 131.763 129.740 129.572 159.948 145.464 131.930 133.117 129.342 Running single-dimensional 91.153 145.657 111.974 96.436 100.015 97.640 94.581 139.658 108.326 92.931 Release (code optimalization enabled) Running jagged 108.503 95.409 128.187 121.877 119.295 118.201 102.321 116.393 125.499 116.459 Running multi-dimensional 62.292 60.627 60.611 60.883 61.167 60.923 62.083 60.932 61.444 62.974 Running single-dimensional 34.974 33.901 34.088 34.659 34.064 34.735 34.919 34.694 35.006 34.796 

Miré en desassemblys y esto es lo que encontré

jagged[i][j][k] = i * j * k; necesita 34 instrucciones para ejecutar

multi[i, j, k] = i * j * k; necesita 11 instrucciones para ejecutar

single[i * dim * dim + j * dim + k] = i * j * k; necesita 23 instrucciones para ejecutar

No pude identificar por qué las matrices unidimensionales eran aún más rápidas que las multidimensionales, pero creo que tiene que ver con alguna optimización realizada en la CPU

Las matrices multidimensionales son matrices de dimensión (n-1).

Entonces int[,] square = new int[2,2] es matriz cuadrada 2×2, int[,,] cube = new int [3,3,3] es un cubo – matriz cuadrada 3×3. La proporcionalidad no es requerida.

Las matrices irregulares son solo una matriz de matrices, una matriz en la que cada celda contiene una matriz.

Entonces MDA es proporcional, ¡JD puede no serlo! ¡Cada celda puede contener una matriz de longitud arbitraria!

Esto podría haberse mencionado en las respuestas anteriores, pero no explícitamente: con la matriz dentada puede usar la array[row] para referir una fila completa de datos, pero esto no está permitido para las matrices de varias direcciones.

Además de las otras respuestas, tenga en cuenta que una matriz multidimensional se asigna como un gran objeto grueso en el montón. Esto tiene algunas implicaciones:

  1. Algunas matrices multidimensionales se asignarán en el Montículo de objetos grandes (LOH) donde sus contrapartidas de matriz dentada equivalente no tendrían.
  2. El GC necesitará encontrar un único bloque libre de memoria contiguo para asignar una matriz multidimensional, mientras que una matriz dentada podría ser capaz de llenar las lagunas causadas por la fragmentación del montón … esto no suele ser un problema en .NET debido a la compactación , pero el LOH no se compacta por defecto (tiene que solicitarlo, y debe preguntar cada vez que lo desee).
  3. Deseará buscar en para arreglos multidimensionales mucho antes de que el problema si solo usa matrices irregulares.

Estoy analizando archivos .il generados por ildasm para construir una base de datos de conjuntos de datos, clases, métodos y procedimientos almacenados para usar haciendo una conversión. Me encontré con lo siguiente, que rompió mi análisis sintáctico.

 .method private hidebysig instance uint32[0...,0...] GenerateWorkingKey(uint8[] key, bool forEncryption) cil managed 

El libro Expert .NET 2.0 IL Assembler, de Serge Lidin, Apress, publicado en 2006, Capítulo 8, Primitive Types and Signatures, págs. 149-150 explica.

[] se denomina vector de ,

[ [**] ] se denomina una matriz de

** significa que se puede repetir, [ ] significa opcional.

Ejemplos: Let = int32 .

1) int32[...,...] es una matriz bidimensional de límites y tamaños inferiores indefinidos

2) int32[2...5] es una matriz unidimensional de límite inferior 2 y tamaño 4.

3) int32[0...,0...] es una matriz bidimensional de límites inferiores 0 y tamaño indefinido.

Tom