.NET retangular Arrays: como o acesso em um loop?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Basicamente, você tem duas maneiras para fazer isso:
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();
}
A única diferença é o que variável a mudança no loop interno: primeiro ou segundo. Ouvi dizer que os resultados diferem de língua para língua.
O que é ordem certa para .NET?
Solução
A única razão é mais rápido do que o outro tem a ver com o cache do processador, e da forma como os dados são dispostos em memória.
Existem duas maneiras normais para armazenar os dados bidimensionais está no espaço de endereçamento unidimensional, ou você pode armazenar todos os dados para a primeira linha, em seguida, a segunda linha, e assim por diante (aka remar grande encomenda ), ou você pode fazê-lo por colunas (aka < a href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> grande ordem da coluna ). Abaixo está o que as posições de memória seria para uma matriz 3x3 para ambas as opções.
Linhas:
1 2 3
4 5 6
7 8 9
Colunas:
1 4 7
2 5 8
3 6 9
Quando você acessar um local de memória, uma linha de cache inteira (que pode ser entre 8 e 512 bytes, de acordo com a Wikipedia) é carregado no cache. Então, se você acessar o próximo local de memória que já estará no cache. Assim, ele pode ser muito mais rápido para acesso sequencialmente memória do que a pular no espaço de endereço. Assim, com grandes matrizes bidimensionais, pode haver uma diferença de velocidade significativa entre a escolha de linhas ou colunas como a variável de loop interno.
Outras dicas
Você deve referência suas circunstâncias particulares para ter certeza.
Você poderia pensar que não haveria diferença para matrizes retangulares (memória ou seja, de forma contígua alocados), mas de acordo com esta artigo MSDN há uma diferença:
Você pode obter ainda melhores resultados por a conversão de uma matriz multidimensional em uma matriz de uma só dimensão. E se você não se importa a sintaxe, isto pode ser trivial; basta usar um índice como um Deslocamento. Por exemplo, a seguir declara uma matriz unidimensional para ser utilizado como uma matriz bidimensional:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
Para indexar os elementos desta matriz, use o seguinte offset:
myArray[row * COLUMN_DIM + column];
Este será sem dúvida mais rápido do que um equivalente irregulares ou rectangular array.
Então eu fiz o ponto de referência e os resultados são que o acesso à arr1 é três vezes mais rápido.
Muito interessante, eu nunca parou para pensar que pode ser uma enorme diferença tão simplesmente acessando os índices de matriz "não sequencial". Eu dei-lhe uma tentativa mim mesmo, e também encontrou o seguinte código teve o segundo ciclo, tendo entre 2-3 vezes mais:
// 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 manter as coisas curto, aqui estão os trechos de IL emitidos para o X pelo circuito Y e Y por X loop.
código inicial antes de 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 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
looping 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
O fluxo lógico IL é um pouco semelhante. A principal diferença é que pode-se observar a primeira espira consegue usar stloc e ldloc para as posições 2 e 3 para o primeiro conjunto e o índice variável X. No momento em que ele veio para o segundo ciclo, que tinha gasto o maxstack e, portanto, utilizado os stloc.s e instruções ldloc.s. Eu acredito que esta é a diferença entre variáveis ??referenciando na pilha contra na pilha, e contribuindo para o desempenho mais lento.
Agora, se você trocar a ordem em que os laços são testados, para que o Y por X laço é executado primeiro a referências pilha de acesso, você vai ver as durações de tempo se inverteu.
UPDATE: Eu estava errado sobre como fazer referência pilha ou heap endereços. Parece apenas que os primeiros quatro variáveis ??em um método são mais eficientes para referência com o stloc.0 dedicado, 1, 3, 4 e ldloc.0, 1, 3, 4 opcodes.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
