Array rettangolari .NET: come accedere in un ciclo?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Fondamentalmente hai due modi per farlo:
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();
}
L'unica differenza è quale variabile modificare nel ciclo interno: primo o secondo. Ho sentito che i risultati differiscono da una lingua all'altra.
Qual è l'ordine giusto per .NET?
Soluzione
Il motivo per cui uno è più veloce dell'altro ha a che fare con la cache del processore e il modo in cui i dati sono disposti in memoria.
Esistono due modi normali per archiviare i dati bidimensionali nello spazio degli indirizzi unidimensionale, oppure è possibile memorizzare tutti i dati per la prima riga, quindi per la seconda riga e così via (ovvero ordine maggiore di riga ), oppure puoi farlo per colonne (aka < a href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> ordine maggiore colonna ). Di seguito sono riportate le posizioni di memoria per un array 3x3 per entrambe queste opzioni.
Righe:
1 2 3
4 5 6
7 8 9
Colonne:
1 4 7
2 5 8
3 6 9
Quando si accede a una posizione di memoria, un'intera riga della cache (che può essere compresa tra 8 e 512 byte, secondo Wikipedia) viene caricata nella cache. Quindi, se accedi alla posizione di memoria successiva, sarà già nella cache. Pertanto, può essere molto più veloce accedere alla memoria in sequenza piuttosto che saltare nello spazio degli indirizzi. Pertanto, con grandi matrici bidimensionali, può esserci una differenza di velocità significativa tra la scelta di righe o colonne come variabile del ciclo interno.
Altri suggerimenti
Dovresti essere sicuro delle tue circostanze particolari per essere sicuro.
Penseresti che non ci sarebbe alcuna differenza per le matrici rettangolari (ovvero memoria allocata in modo contiguo), MA secondo questo articolo MSDN c'è una differenza:
Puoi ottenere risultati ancora migliori di conversione di un array multidimensionale in un array monodimensionale. Se non ti dispiace la sintassi, questo può essere banale; basta usare un indice come compensare. Ad esempio, quanto segue dichiara un array monodimensionale in essere usato come un array bidimensionale:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
Per indicizzare gli elementi di questo array, utilizzare il seguente offset:
myArray[row * COLUMN_DIM + column];
Questo sarà senza dubbio più veloce di un equivalente frastagliato o rettangolare matrice.
Quindi ho fatto il benchmark e i risultati sono che l'accesso ad arr1 è tre volte più veloce.
Molto interessante, non ho mai smesso di considerare che può essere una differenza così grande semplicemente accedendo agli indici di array "non in sequenza". L'ho provato io stesso e ho anche scoperto che il codice seguente aveva il secondo ciclo che impiegava da 2 a 3 volte di più:
// 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();
}
Per farla breve, ecco gli snippet IL emessi per il ciclo X per Y e il ciclo Y per X.
Codice iniziale prima del looping,
.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
ciclo X per 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
ciclo Y per 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
Il flusso logico IL è in qualche modo simile. La differenza principale che posso osservare è che il primo loop riesce a usare stloc e ldloc per le posizioni 2 e 3 per il primo array e la variabile di indice X. Quando arrivò al secondo ciclo, aveva esaurito il maxstack e quindi utilizzava le istruzioni stloc.s e ldloc.s. Credo che questa sia la differenza tra il riferimento alle variabili nello stack e lo heap e il contributo alle prestazioni più lente.
Ora, se si scambia l'ordine in cui vengono testati i loop, in modo che il ciclo Y per X venga eseguito per primo per accedere ai riferimenti dello stack, vedrai le durate di temporizzazione invertite.
AGGIORNAMENTO: ho sbagliato a fare riferimento agli indirizzi di stack o heap. Sembra solo che le prime quattro variabili in un metodo siano più efficienti per fare riferimento con i codici operativi stloc.0, 1, 3, 4 e ldloc.0, 1, 3, 4 dedicati.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
