¿Diferencias entre una matriz multidimensional "[,]" y una matriz de matrices "[][]" en C#?
¿Cuáles son las diferencias entre matrices multidimensionales double[,]y matrices de matrices ?double[][] en C#?
¿Si hay una diferencia?
¿Cuál es el mejor uso para cada uno?
Las matrices dentadas (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 mejor.
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étodos. 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á el 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 utilizar matrices irregulares, puede realizar fácilmente operaciones como el intercambio de filas y el cambio de tamaño de filas. 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 las use para analizar sus proyectos.
Una matriz multidimensional crea un bonito diseño de memoria lineal, mientras que una matriz irregular implica varios niveles adicionales de direccionamiento indirecto.
Buscar el valor jagged[3][6]en una matriz irregular var jagged = new int[10][5]funciona así:
- Busque el elemento en el índice 3 (que es una matriz).
- Busque el elemento en el índice 6 de esa matriz (que es un valor).
En este caso, para cada dimensión, hay una búsqueda adicional (este es un patrón de acceso a la 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 irregular es siempre 1, pero una matriz multidimensional puede tener cualquier rango. GetLengthSe puede utilizar el método de cualquier matriz para obtener la longitud de cada dimensión. Para la matriz multidimensional de este ejemplo, mult.GetLength(1)se 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 continuo, mientras que una matriz irregular no tiene que ser cuadrada, por ejemplo, jagged[1].Lengthno tiene que ser igual a 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 tiempos de matrices irregulares, la segunda muestra matrices multidimensionales y la tercera, bueno, así debe ser. El programa 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, más o menos lo mismo que mi propia interpretación de cómo debería ser la búsqueda de matrices multidimensionales, consulte 'Single()'. Lamentablemente, el compilador JIT de Windows es realmente estúpido y esto, lamentablemente, dificulta estas discusiones sobre el rendimiento, ya que hay demasiadas inconsistencias.
Estos son los tiempos que obtuve en Windows, lo mismo ocurre aquí, la primera fila son matrices 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 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.
Array of Array (matriz irregular) le permite hacer que cada elemento contenga otra matriz del mismo tipo de longitud variable.
Entonces, si está seguro de que la estructura de los datos se parece a una tabla (filas/columnas fijas), puede utilizar una matriz multidimensional. La matriz irregular son elementos fijos y cada elemento puede contener una matriz de longitud variable
Por ejemplo, pseudocódigo:
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 si cada fila tuviera un número variable de columnas:
1 | 2 | 3 | 4 11 | 12 21 | 22 | 23
Actualización .NET 6:
Con el lanzamiento de .NET 6 decidí que era un buen momento para revisar este tema. Reescribí el código de prueba para el nuevo .NET y lo ejecuté con el requisito de que cada parte se ejecutara al menos durante un segundo. La prueba se realizó en AMD Ryzen 5600x.
¿Resultados? Es complicado. Parece que la matriz única es la de mayor rendimiento para matrices más pequeñas y grandes (< ~25x25x25 & > ~200x200x200) y las matrices irregulares son las más rápidas en el medio. Desafortunadamente, según mis pruebas, parece que las multidimensionales son, con diferencia, la opción más lenta. En el mejor de los casos, funciona dos veces más lento que la opción más rápida. ¡Pero! Depende de para qué necesite las matrices, porque las matrices irregulares pueden tardar mucho más en inicializarse en un cubo de 50 ^ 3; la inicialización fue aproximadamente 3 veces más larga que la unidimensional. Multidimensional era sólo un poco más lento que unidimensional.
¿La conclusión? Si necesita código rápido, compárelo usted mismo en la máquina en la que se ejecutará. La arquitectura de la CPU puede cambiar completamente el rendimiento relativo de cada método.
¡Números!
Method name Ticks/Iteration Scaled to the best
Array size 1x1x1 (10,000,000 iterations):
Jagged: 0.15 4.28
Single: 0.035 1
Multi-dimensional: 0.77 22
Array size 10x10x10 (25,000 iterations):
Jagged: 15 1.67
Single: 9 1
Multi-dimensional: 56 6.2
Array size 25x25x25 (25,000 iterations):
Jagged: 157 1.3
Single: 120 1
Multi-dimensional: 667 5.56
Array size 50x50x50 (10,000 iterations):
Jagged: 1,140 1
Single: 2,440 2.14
Multi-dimensional: 5,210 4.57
Array size 100x100x100 (10,000 iterations):
Jagged: 9,800 1
Single: 19,800 2
Multi-dimensional: 41,700 4.25
Array size 200x200x200 (1,000 iterations):
Jagged: 161,622 1
Single: 175,507 1.086
Multi-dimensional: 351,275 2.17
Array size 500x500x500 (100 iterations):
Jagged: 4,057.413 1.5
Single: 2,709,301 1
Multi-dimensional: 5,359,393 1.98
¿No confías en mí? Ejecútelo usted mismo y verifique.
Nota: el tamaño constante parece dar una ventaja a las matrices irregulares, pero no es lo suficientemente significativo como para cambiar el orden en mis puntos de referencia. En algunos casos, he medido una disminución de ~7 % en el rendimiento cuando uso el tamaño de la entrada del usuario para matrices irregulares, ninguna diferencia para matrices individuales y una diferencia muy pequeña (~1 % o menos) para matrices multidimensionales. Es más prominente en el medio, donde las matrices irregulares toman la delantera.
using System.Diagnostics;
const string Format = "{0,7:0.000} ";
const int TotalPasses = 25000;
const int Size = 50;
Stopwatch timer = new();
var functionList = new List<Action> { Jagged, Single, SingleStandard, Multi };
Console.WriteLine("{0,5}{1,20}{2,20}{3,20}{4,20}", "Run", "Ticks", "ms", "Ticks/Instance", "ms/Instance");
foreach (var item in functionList)
{
var warmup = Test(item);
var run = Test(item);
Console.WriteLine($"{item.Method.Name}:");
PrintResult("warmup", warmup);
PrintResult("run", run);
Console.WriteLine();
}
static void PrintResult(string name, long ticks)
{
Console.WriteLine("{0,10}{1,20}{2,20}{3,20}{4,20}", name, ticks, string.Format(Format, (decimal)ticks / TimeSpan.TicksPerMillisecond), (decimal)ticks / TotalPasses, (decimal)ticks / TotalPasses / TimeSpan.TicksPerMillisecond);
}
long Test(Action func)
{
timer.Restart();
func();
timer.Stop();
return timer.ElapsedTicks;
}
static void Jagged()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var jagged = new int[Size][][];
for (var i = 0; i < Size; i++)
{
jagged[i] = new int[Size][];
for (var j = 0; j < Size; j++)
{
jagged[i][j] = new int[Size];
for (var k = 0; k < Size; k++)
{
jagged[i][j][k] = i * j * k;
}
}
}
}
}
static void Multi()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var multi = new int[Size, Size, Size];
for (var i = 0; i < Size; i++)
{
for (var j = 0; j < Size; j++)
{
for (var k = 0; k < Size; k++)
{
multi[i, j, k] = i * j * k;
}
}
}
}
}
static void Single()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var single = new int[Size * Size * Size];
for (var i = 0; i < Size; i++)
{
int iOffset = i * Size * Size;
for (var j = 0; j < Size; j++)
{
var jOffset = iOffset + j * Size;
for (var k = 0; k < Size; k++)
{
single[jOffset + k] = i * j * k;
}
}
}
}
}
static void SingleStandard()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var single = new int[Size * Size * Size];
for (var i = 0; i < Size; i++)
{
for (var j = 0; j < Size; j++)
{
for (var k = 0; k < Size; k++)
{
single[i * Size * Size + j * Size + k] = i * j * k;
}
}
}
}
}
Lección aprendida: incluya siempre la CPU en los puntos de referencia, porque marca la diferencia. ¿Lo hizo esta vez? No lo sé, pero sospecho que podría haber sido así.
Respuesta original:
Me gustaría actualizar sobre 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 la vista previa 2 de .NET Core 2.0. Aumenté el valor de la dimensión para hacer menos visible cualquier posible influencia de las aplicaciones en segundo plano.
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 desmontajes 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 eran aún más rápidas que las multidimensionales, pero supongo que tiene que ver con alguna optimización realizada en la CPU.
