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

454

¿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?

ecleel
fuente
77
El primero double[,]es una matriz rectangular, mientras que double[][]se conoce como una "matriz irregular". La primera tendrá el mismo número de "columnas" para cada fila, mientras que la segunda tendrá (potencialmente) un número diferente de "columnas" para cada fila.
GreatAndPowerfulOz

Respuestas:

334

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.

okutane
fuente
77
@ John, mídelos tú mismo y no hagas suposiciones.
Hosam Aly
2
@John: Mi primera reacción también, pero me equivoqué. Vea la pregunta de Hosams para más detalles.
Henk Holterman
38
Las matrices multidimensionales deberían ser lógicamente más eficientes, pero su implementación por parte del compilador JIT no lo es. El código anterior no es útil ya que no muestra el acceso a la matriz en un bucle.
ILoveFortran
3
@Henk Holterman: vea mi respuesta a continuación, podría ser el caso de que en Windows las matrices irregulares sean rápidas, pero uno tiene que darse cuenta de que esto es completamente específico de CLR y no el caso, por ejemplo, con mono ...
John Leidegren
12
Sé que esta es una vieja pregunta, solo me pregunto si CLR se ha optimizado para matrices multidimensionales desde que se hizo esta pregunta.
Anthony Nichols
197

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();
    }
}
John Leidegren
fuente
2
Intente cronometrarlos usted mismo y vea cómo funcionan ambos. Las matrices irregulares están mucho más optimizadas en .NET. Puede estar relacionado con la verificación de límites, pero independientemente de la razón, los tiempos y los puntos de referencia muestran claramente que las matrices irregulares son de acceso más rápido que las multidimensionales.
Hosam Aly
10
Pero sus tiempos parecen ser demasiado pequeños (unos pocos milisegundos). En este nivel, tendrá mucha interferencia de los servicios y / o controladores del sistema. Haga sus pruebas mucho más grandes, al menos tomando un segundo o dos.
Hosam Aly
8
@JohnLeidegren: El hecho de que las matrices multidimensionales funcionan mejor al indexar una dimensión que otra se ha entendido durante medio siglo, ya que los elementos que difieren en una sola dimensión particular se almacenarán consecutivamente en la memoria y con muchos tipos de memoria (pasado y presente), acceder a elementos consecutivos es más rápido que acceder a elementos distantes. Creo que en .net uno debería obtener resultados óptimos de indexación por el último subíndice que es lo que estaba haciendo, pero probar el tiempo con los subíndices intercambiados puede ser informativo en cualquier caso.
supercat
16
@supercat: las matrices multidimensionales en C # se almacenan en orden de fila principal , el intercambio del orden de los subíndices sería más lento ya que accedería a la memoria de manera no consecutiva. Por cierto, los tiempos informados ya no son precisos, obtengo casi el doble de veces más rápido para las matrices multidimensionales que las matrices irregulares (probado en el último .NET CLR), que es cómo debería ser ...
Amro
99
Sé que esto es un poco pedante, pero debo mencionar que esto no es Windows vs Mono, sino CLR vs Mono. A veces pareces confundirlos. Los dos no son equivalentes; Mono también funciona en Windows.
Magus
70

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
shahkalpesh
fuente
44
esto es lo que realmente importa al decidir qué usar ... no esta cosa de velocidad ... bueno, la velocidad puede convertirse en un factor cuando tienes una matriz cuadrada.
Xaser
46

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.

Eglin
fuente
1
Gracias por corregir la respuesta de okutane (no Dmitry). Es molesto que las personas den respuestas incorrectas en Stackoverflow y obtengan 250 votos positivos, mientras que otros dan respuestas correctas y obtienen mucho menos. Pero al final el código IL es irrelevante. Tienes que MEDIR realmente la velocidad para decir algo sobre el rendimiento. ¿Hiciste eso? Creo que la diferencia será ridícula.
Elmue
38

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

adsamcik
fuente
14

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!

abatishchev
fuente
7

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.

lznt
fuente
4

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.
Joe Amenta
fuente
2

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

Thomas C Hutchinson
fuente