¿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 las matrices de matrices double[][]en C #?

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

Las matrices de matrices (matrices irregulares) son más rápidas que las matrices multidimensionales y se pueden usar de manera más efectiva. Las matrices multidimensionales tienen una sintaxis más agradable.

Si escribe un código simple usando matrices irregulares y multidimensionales y luego inspecciona el ensamblaje compilado con un desensamblador IL, verá que el almacenamiento y la recuperación de matrices irregulares (o unidimensionales) son instrucciones IL simples, mientras que las mismas operaciones para matrices multidimensionales son método invocaciones que siempre son 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 tales como cambio de fila y cambio de tamaño de fila. Quizás en algunos casos el uso de matrices multidimensionales sea más seguro, pero incluso Microsoft FxCop dice que se deben usar matrices irregulares en lugar de multidimensionales cuando se usa para analizar sus proyectos.

Una matriz multidimensional crea un diseño de memoria lineal agradable, mientras que una matriz irregular implica varios niveles adicionales de indirección.

Buscar el valor jagged[3][6]en una matriz irregular var jagged = new int[10][5]funciona de la siguiente manera: busque el elemento en el índice 3 (que es una matriz) y busque 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 memoria costoso).

Una matriz multidimensional se presenta linealmente en la memoria, el valor real se encuentra multiplicando los índices. Sin embargo, dada la matriz var mult = new int[10,30], la Lengthpropiedad de esa matriz multidimensional devuelve el número total de elementos, es decir, 10 * 30 = 300.

La Rankpropiedad de una matriz dentada es siempre 1, pero una matriz multidimensional puede tener cualquier rango. El GetLengthmétodo 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 dirección base de la matriz.

Por lo tanto, una matriz multidimensional asigna un bloque de memoria continua, mientras que una matriz irregular no tiene que ser cuadrada, por ejemplo jagged[1].Length, no tiene que ser igual 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 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 tiempos de matrices irregulares, la segunda muestra matrices multidimensionales y la tercera, bueno, así es como debería ser. El programa se muestra a continuación, para su información, esto se probó con 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 debería ser la búsqueda de matrices multidimensionales, ver 'Single ()'. Lamentablemente, el compilador JIT de Windows es realmente estúpido, y esto desafortunadamente dificulta estas discusiones de rendimiento, hay demasiadas inconsistencias.

Estos son los tiempos que obtuve en Windows, el mismo trato aquí, la primera fila son matrices irregulares, la segunda es multidimensional y la tercera es mi propia implementación de multidimensional, tenga en cuenta cuánto más lento es esto en Windows en comparación con 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();
    }
}

En pocas palabras, las matrices multidimensionales son similares a una tabla en DBMS.
La matriz de matriz (matriz irregular) le permite hacer que cada elemento contenga otra matriz del mismo tipo de longitud variable.

Por lo tanto, si está seguro de que la estructura de datos se parece a 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 2x2:

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 como cada fila que tiene un número variable de columnas:

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

Prefacio: Este comentario está destinado a abordar la respuesta proporcionada por okutane , pero debido al sistema de reputación tonto de SO, no puedo publicarlo donde pertenece.

Su afirmación de que uno es más lento que el otro debido a las llamadas al método no es correcta. 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 el IL, sino el ensamblado compilado. Por ejemplo, en mi instalación 4.5, el acceso a un elemento (a través del puntero en edx) almacenado en una matriz bidimensional apuntada por ecx con índices almacenados en eax y edx se ve así:

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 por las llamadas a métodos. La comprobación de límites es muy complicada 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 los casos distintos de cero, el código prácticamente se resuelve (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Este cálculo es casi tan rápido (una multiplicación podría ser reemplazada por un cambio, ya que esa es la razón por la que elegimos bytes para ser dimensionados 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 compilador moderno optimizará la comprobación de límites anidados para el acceso a elementos mientras itera sobre una matriz de una sola dimensión. El resultado es un código que básicamente solo 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 compilador optimice la operación. Por lo tanto, a pesar de que la sobrecarga de verificación de límites de acceso a un solo elemento se amortiza en tiempo de ejecución constante con respecto a las dimensiones y tamaños de la matriz, un caso de prueba simple para medir la diferencia puede tardar mucho más en ejecutarse.

Me gustaría actualizar esto, porque en .NET Core las matrices multidimensionales son más rápidas que las matrices irregulares . Ejecuté las pruebas de John Leidegren y estos son los resultados en .NET Core 2.0 preview 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 

Investigué los desensamblajes y esto es lo que encontré

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

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

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

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

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

Entonces int[,] square = new int[2,2]es matriz cuadrada 2x2, int[,,] cube = new int [3,3,3]es un cubo - matriz cuadrada 3x3. No se requiere proporcionalidad.

Las matrices irregulares son solo matrices de matrices, una matriz donde cada celda contiene una matriz.

Así que MDA son proporcionales, ¡JD puede no serlo! ¡Cada celda puede contener una matriz de longitud arbitraria!

Esto podría haber sido mencionado en las respuestas anteriores, pero no explícitamente: con una matriz irregular puede usar array[row]para referir una fila completa de datos, pero esto no está permitido para matrices multi-d.

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ón de objetos grandes (LOH) donde sus contrapartes de matriz dentada equivalentes no tendrían de otra manera.
2. El GC necesitará encontrar un solo bloque de memoria libre contiguo para asignar una matriz multidimensional, mientras que una matriz irregular podría llenar los huecos causados ​​por la fragmentación del montón ... esto generalmente no es un problema en .NET debido a la compactación , pero el LOH no se compacta de manera predeterminada (debe solicitarlo y debe hacerlo cada vez que lo desee).
3. Querrá buscar <gcAllowVeryLargeObjects>matrices multidimensionales mucho antes de que surja el problema si solo usa matrices irregulares.

Estoy analizando archivos .il generados por ildasm para construir una base de datos de ensamblajes, clases, métodos y procedimientos almacenados para usar para hacer una conversión. Encontré lo siguiente, que rompió mi análisis.

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

Explica el libro Expert .NET 2.0 IL Assembler, de Serge Lidin, Apress, publicado en 2006, Capítulo 8, Tipos y firmas primitivas, págs. 149-150.

<type>[]se denomina Vector de <type>,

<type>[<bounds> [<bounds>**] ] se denomina una serie de <type>

**los medios pueden repetirse, los [ ]medios son opcionales.

Ejemplos: Let <type> = 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