tamaño - recorrer matriz c#
¿Cuáles son las diferencias entre una matriz multidimensional y una matriz de matrices en C#? (9)
Además de las otras respuestas, tenga en cuenta que una matriz multidimensional se asigna como un objeto grueso grande en el montón. Esto tiene algunas implicaciones:
- Algunas matrices multidimensionales se asignarán en el montón de objetos grandes (LOH) donde sus equivalentes de matrices irregulares equivalentes no tendrían.
- El GC tendrá que encontrar un único bloque de memoria libre contiguo para asignar una matriz multidimensional, mientras que una matriz irregular puede ser capaz de llenar los huecos causados 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 de forma predeterminada (debe solicitarlo y solicitarlo cada vez que lo desee).
-
<gcAllowVeryLargeObjects>buscar en<gcAllowVeryLargeObjects>para obtener matrices multidimensionales mucho antes de que<gcAllowVeryLargeObjects>el problema si solo utiliza matrices irregulares.
¿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?
En pocas palabras, los arreglos 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.
Por lo tanto, si está seguro de que la estructura de los 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 que cada fila tiene un número variable de columnas:
1 | 2 | 3 | 4 11 | 12 21 | 22 | 23
Esto podría haberse mencionado en las respuestas anteriores pero no explícitamente: con una matriz dentada puede usar array[row] para referirse a una fila completa de datos, pero esto no está permitido para matrices multi-d.
Estoy analizando los archivos .il generados por ildasm para crear una base de datos de ensamblajes, clases, métodos y procedimientos almacenados para usarlos haciendo una conversión. Me encontré con lo siguiente, que rompió mi análisis.
.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, pp. 149-150 explica.
<type>[] se denomina Vector de <type> ,
<type>[<bounds> [<bounds>**] ] se denomina una matriz de <type>
** medios pueden repetirse, [ ] significa opcional.
Ejemplos: Sea <type> = int32 .
1) int32[...,...] es una matriz bidimensional de límites y tamaños inferiores no definidos
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
Las matrices de matrices (matrices dentadas) son más rápidas que las matrices multidimensionales y se pueden utilizar con mayor eficacia. Los arreglos multidimensionales tienen una mejor sintaxis.
Si escribe un código simple con matrices dentadas y multidimensionales y luego inspecciona el ensamblaje compilado con un desensamblador IL, verá que el almacenamiento y la recuperación de las matrices dentadas (o de una sola dimensión) son simples instrucciones de IL, mientras que las mismas operaciones para matrices multidimensionales son un 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 utilizar matrices dentadas, puede realizar fácilmente operaciones como el intercambio de filas y el cambio de tamaño de las filas. Tal vez 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 usa para analizar sus proyectos.
Las matrices multidimensionales son matrices de dimensión (n-1).
Así que int[,] square = new int[2,2] es una matriz cuadrada 2x2, int[,,] cube = new int [3,3,3] es un cubo - matriz cuadrada 3x3. No se requiere proporcionalidad.
Las matrices dentadas son solo matrices de matrices, una matriz donde cada celda contiene una matriz.
Así que los MDA son proporcionales, ¡JD puede no serlo! ¡Cada celda puede contener una matriz de longitud arbitraria!
Me gustaría actualizar sobre esto, porque en .NET Los arreglos multidimensionales son más rápidos que los arreglos irregulares . Ejecuté las pruebas de John Leidegren y estos son los resultados en .NET Core 2.0 preview 2. Aumenté el valor de dimensión para hacer que cualquier posible influencia de las aplicaciones en segundo plano sea menos visible.
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; Se necesitan 34 instrucciones para ejecutar.
multi[i, j, k] = i * j * k; Se necesitan 11 instrucciones para ejecutar.
single[i * dim * dim + j * dim + k] = i * j * k; Se necesitan 23 instrucciones para ejecutar.
No pude identificar por qué los arreglos unidimensionales eran aún más rápidos que los multidimensionales, pero creo que tiene que ver con la optimización realizada en la CPU.
Una matriz multidimensional crea un buen diseño de memoria lineal, mientras que una matriz irregular implica varios niveles adicionales de direccionamiento indirecto.
Buscando el valor jagged[3][6] en una matriz dentada var jagged = new int[10][5] funciona así: 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 la memoria costoso).
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 el número total de elementos, es decir, 10 * 30 = 300.
La propiedad Rank de una matriz irregular 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 continua, mientras que una matriz dentada no tiene que ser cuadrada, por ejemplo, jagged[1].Length no tiene que ser igual a jagged[2].Length , que sería verdadera 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 los tiempos de las 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 tu 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 las ventanas, los tiempos de las matrices dentadas son muy superiores, más o menos lo mismo que mi propia interpretación de cómo debería ser la matriz multidimensional, consulte "Único ()". Lamentablemente, el compilador JIT de Windows es realmente estúpido, y desafortunadamente esto dificulta las discusiones sobre el rendimiento, ya que hay demasiadas inconsistencias
Estos son los tiempos que obtuve en Windows, el mismo acuerdo aquí, la primera fila son matrices irregulares, la segunda multidimensional y la tercera implementación mía de multidimensional, tenga en cuenta lo mucho más lento que 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();
}
}
Prefacio: este comentario está destinado a abordar share , pero debido al sistema de reputación tonta de SO, no puedo publicarlo donde corresponda.
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 algoritmos de verificación de límites más complicados. Puede verificar esto fácilmente mirando, no a la IL, sino al ensamblaje 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í, puedes ver que no hay sobrecarga por las llamadas a métodos. La verificación de límites es muy complicada gracias a la posibilidad de índices no nulos, que es una funcionalidad que no se ofrece con matrices dentadas. Si eliminamos los sub, cmp y jmps para los casos que no son cero, el código se resuelve en gran (x*y_max+y)*sizeof(ptr)+sizeof(array_header) . Este cálculo es tan rápido (una multiplicación podría reemplazarse por un desplazamiento, ya que esa es la razón por la que elegimos que los bytes se dimensionen 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á los límites anidados, verificando el acceso al elemento mientras se repite en 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, aunque la sobrecarga de verificación de límites para acceder 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 llevar muchas veces más tiempo de ejecución.