.NET Rechteckige Arrays: wie in einer Schleife zuzugreifen?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Im Grunde haben Sie zwei Möglichkeiten, dies zu tun:
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();
}
Der einzige Unterschied ist, welche Variablen in der inneren Schleife zu ändern: erste oder zweite. Ich habe gehört, dass die Ergebnisse von Sprache zu Sprache unterscheiden.
Was ist richtig, um für .NET?
Lösung
Der Grund ist schneller als der andere mit dem Cache des Prozessors zu tun hat, und die Art und Weise werden die Daten im Speicher angelegt.
Es gibt zwei normale Wege, um die zweidimensionalen Daten zu speichern ist in eindimensionalen Adressraum, Sie können entweder für die erste Zeile alle Daten speichern, dann die zweite Reihe, und so weiter (auch bekannt als Reihenhauptordnung ), oder Sie können es durch Spalten tun (auch bekannt als < a href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> Spaltenhauptordnung ). Im Folgenden finden Sie, was die Speicherplätze für beide Optionen für eine 3x3-Array sein würde.
Zeilen:
1 2 3
4 5 6
7 8 9
Spalten:
1 4 7
2 5 8
3 6 9
Wenn Sie einen Speicherplatz zuzugreifen, eine gesamte Cache-Zeile (die zwischen 8 und 512 Bytes, entsprechend Wikipedia sein kann) wird in den Cache geladen. Wenn Sie also das nächste Speicherplatz zugreifen wird es bereits im Cache sein. So kann es viel schneller Speicher sequentiell zuzugreifen, als um den Raum in der Adresse zu springen. So mit großen zweidimensionalen Anordnungen, kann eine deutliche Geschwindigkeits Unterschied zwischen Zeilen oder Spalten als innere Schleife Variable wählen.
Andere Tipps
Sie sollten Benchmark Ihre besonderen Umständen sicher sein.
Sie würden denken, dass es kein Unterschied für rechteckigen Arrays wäre (dh zusammenhängend zugewiesenen Speicher), aber nach diesem MSDN-Artikel gibt es einen Unterschied:
können Sie erhalten noch bessere Ergebnisse durch Umwandeln einer multidimensionalen Array in ein eindimensionales Array. Wenn Sie nicht die Syntax ausmacht, kann das sein trivial; verwenden nur einen Index als versetzt. Zum Beispiel, nach dem deklariert ein eindimensionales Array als zweidimensionale Anordnung verwendet werden:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
Für die Indizierung der Elemente dieser Array, verwenden Sie die folgende Offset:
myArray[row * COLUMN_DIM + column];
Dies wird zweifellos schneller als ein äquivalenter gezackten oder rechteckigen Array.
So habe ich die Benchmark und die Ergebnisse sind, dass der Zugang zu arr1 dreimal schneller ist.
Sehr interessant, ich habe nie aufgehört zu bedenken, dass einfach einen so großen Unterschied, indem sie den Array-Indizes „nicht sequentiell“ zugreifen. Ich habe ein es versuchen, mich und fand auch der folgende Code die zweite Schleife hatte nehmen zwischen 2 - 3-mal länger:
// 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();
}
Um es kurz zu halten, ist hier der emittierten IL-Schnipsel für die X durch Y-Schleife und der Y durch X-Schleife.
Initial-Code vor dem 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
Looping X durch 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
Looping Y durch 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
Der IL logische Ablauf ist ähnlich. Der Hauptunterschied I beobachten kann, ist die erste Schleife stloc ldloc und für die Positionen 2 und 3 für die erste Anordnung und das X-Index-Variable zu verwenden, verwaltet. Durch die Zeit, um es in die zweite Schleife kam, hatte er die maxstack verbraucht und benutzt somit die stloc.s und ldloc.s Anweisungen. Ich glaube, dies ist der Unterschied Variablen auf dem Stack im Vergleich zu auf dem Heap zwischen Referenzierung, und die langsameren Leistung beitragen.
Nun, wenn Sie den Auftrag tauschen, in dem die Schleifen getestet werden, so dass der Y von X Schleife zuerst ausgeführt wird Stapel Referenzen zugreifen, sehen Sie die Zeitdauer umgekehrt gehen.
UPDATE: Ich war falsch über Referenzierung Stack oder Heap-Adressen. Es scheint nur, dass die ersten vier Variablen in einer Methode effizienter mit dem dedizierten stloc.0 zu referenzieren, 1, 3, 4 und ldloc.0, 1, 3, 4 OP-Codes.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
