Matrices rectangulares .NET: ¿cómo acceder en un bucle?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Básicamente tienes dos formas de hacer esto:
for (int x = 0; x < UPPER_X; x++)
for (int y = 0; y < UPPER_Y; y++)
{
arr1[x, y] = get_value();
arr2[y, x] = get_value();
}
La única diferencia es qué variable cambiar en el bucle interno: primero o segundo. Escuché que los resultados difieren de un idioma a otro.
¿Cuál es el orden correcto para .NET?
Solución
El motivo por el cual uno es más rápido que el otro tiene que ver con la memoria caché del procesador y la forma en que los datos se almacenan en la memoria.
Hay dos formas normales de almacenar los datos bidimensionales en un espacio de direcciones unidimensional. Puede almacenar todos los datos para la primera fila, luego la segunda fila, y así sucesivamente (también conocido como orden principal de fila ), o puede hacerlo por columnas (también conocido como < a href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> orden principal de columna ). A continuación se muestran las ubicaciones de memoria para una matriz de 3x3 para ambas opciones.
Filas:
1 2 3
4 5 6
7 8 9
Columnas:
1 4 7
2 5 8
3 6 9
Cuando accede a una ubicación de memoria, se carga una línea de caché completa (que puede tener entre 8 y 512 bytes, según Wikipedia). Entonces, si accede a la siguiente ubicación de memoria, ya estará en el caché. Por lo tanto, puede ser mucho más rápido acceder a la memoria secuencialmente que saltar en el espacio de direcciones. Por lo tanto, con grandes matrices bidimensionales, puede haber una diferencia de velocidad significativa entre elegir filas o columnas como su variable de bucle interno.
Otros consejos
Debes comparar tus circunstancias particulares para estar seguro.
Pensaría que no habría diferencia para las matrices rectangulares (es decir, memoria asignada contiguamente), PERO de acuerdo con esto Artículo de MSDN hay una diferencia:
Puede obtener mejores resultados si convertir una matriz multidimensional en una matriz unidimensional. Si no te importa la sintaxis, esto puede ser trivial; solo use un índice como compensar. Por ejemplo, lo siguiente declara una matriz unidimensional para ser utilizado como una matriz bidimensional:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
Para indexar los elementos de este matriz, utilice el siguiente desplazamiento:
myArray[row * COLUMN_DIM + column];
Esto, sin duda, será más rápido que un equivalente dentado o rectangular matriz.
Así que hice el punto de referencia y los resultados son que el acceso a arr1 es tres veces más rápido.
Muy interesante, nunca me detuve a considerar que puede ser una gran diferencia simplemente accediendo a los índices de la matriz "no secuencialmente". Lo intenté yo mismo, y también encontré que el siguiente código tenía el segundo bucle entre 2 y 3 veces más largo:
// Hmmm, how to insert blank lines in the code formatter???
static void Main(string[] args)
{
Stopwatch timer = new Stopwatch();
int arraySize = 10000;
// First array, access X by Y
int[,] xbyy = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
xbyy[x, y] = 15;
}
timer.Stop();
TimeSpan duration = timer.Elapsed;
string realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("X by Y took " + realTimeFormat);
// Seecond array, access Y by X
int[,] ybyx = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
ybyx[y, x] = 15;
}
timer.Stop();
duration = timer.Elapsed;
realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("Y by X took " + realTimeFormat);
Console.ReadLine();
}
Para mantener las cosas cortas, aquí están los fragmentos de IL emitidos para el bucle X por Y y el bucle Y por X.
Código inicial antes del bucle,
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
// Code size 290 (0x122)
.maxstack 4
.locals init ([0] class [System]System.Diagnostics.Stopwatch timer,
[1] int32 arraySize,
[2] int32[0...,0...] xbyy,
[3] int32 x,
[4] int32 y,
[5] valuetype [mscorlib]System.TimeSpan duration,
[6] string realTimeFormat,
[7] int32[0...,0...] ybyx,
[8] int32 V_8,
[9] int32 V_9)
IL_0000: newobj instance void [System]System.Diagnostics.Stopwatch::.ctor()
IL_0005: stloc.0
IL_0006: ldc.i4 0x2710
IL_000b: stloc.1
bucle X por Y
IL_000c: ldloc.1
IL_000d: ldloc.1
IL_000e: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0013: stloc.2
IL_0014: ldloc.0
IL_0015: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_001a: ldc.i4.0
IL_001b: stloc.3
IL_001c: br.s IL_003d
IL_001e: ldc.i4.0
IL_001f: stloc.s y
IL_0021: br.s IL_0034
IL_0023: ldloc.2
IL_0024: ldloc.3
IL_0025: ldloc.s y
IL_0027: ldc.i4.s 15
IL_0029: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_002e: ldloc.s y
IL_0030: ldc.i4.1
IL_0031: add
IL_0032: stloc.s y
IL_0034: ldloc.s y
IL_0036: ldloc.1
IL_0037: blt.s IL_0023
IL_0039: ldloc.3
IL_003a: ldc.i4.1
IL_003b: add
IL_003c: stloc.3
IL_003d: ldloc.3
IL_003e: ldloc.1
IL_003f: blt.s IL_001e
IL_0041: ldloc.0
bucle Y por X
IL_0090: ldloc.1
IL_0091: ldloc.1
IL_0092: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0097: stloc.s ybyx
IL_0099: ldloc.0
IL_009a: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_009f: ldc.i4.0
IL_00a0: stloc.s V_8
IL_00a2: br.s IL_00c7
IL_00a4: ldc.i4.0
IL_00a5: stloc.s V_9
IL_00a7: br.s IL_00bc
IL_00a9: ldloc.s ybyx
IL_00ab: ldloc.s V_9
IL_00ad: ldloc.s V_8
IL_00af: ldc.i4.s 15
IL_00b1: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_00b6: ldloc.s V_9
IL_00b8: ldc.i4.1
IL_00b9: add
IL_00ba: stloc.s V_9
IL_00bc: ldloc.s V_9
IL_00be: ldloc.1
IL_00bf: blt.s IL_00a9
IL_00c1: ldloc.s V_8
IL_00c3: ldc.i4.1
IL_00c4: add
IL_00c5: stloc.s V_8
IL_00c7: ldloc.s V_8
IL_00c9: ldloc.1
IL_00ca: blt.s IL_00a4
IL_00cc: ldloc.0
El flujo lógico IL es algo similar. La principal diferencia que puedo observar es que el primer ciclo logra usar stloc e ldloc para las posiciones 2 y 3 para la primera matriz y la variable de índice X. En el momento en que llegó al segundo bucle, había gastado el maxstack y, por lo tanto, utilizaba las instrucciones stloc.s y ldloc.s. Creo que esta es la diferencia entre hacer referencia a variables en la pila y en el montón, y contribuir al rendimiento más lento.
Ahora, si cambia el orden en que se prueban los bucles, de modo que el bucle Y por X se ejecute primero para acceder a las referencias de la pila, verá que las duraciones de tiempo se invierten.
ACTUALIZACIÓN: Me equivoqué al hacer referencia a direcciones de pila o montón. Parece que las primeras cuatro variables en un método son más eficientes para hacer referencia con los códigos de operación dedicados stloc.0, 1, 3, 4 y ldloc.0, 1, 3, 4.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
