다차원 배열과 C#배열 배열의 차이점은 무엇입니까?
https://stackoverflow.com/questions/597720
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다차원 배열의 차이점은 무엇입니까? double[,] 및 배열 double[][] C#에서?
차이가 있다면 각각에 가장 적합한 것은 무엇입니까?
해결책
배열 배열 (Jagged Array)은 다차원 배열보다 빠르며보다 효과적으로 사용할 수 있습니다. 다차원 배열에는 더 좋은 구문이 있습니다.
Jagged 및 다차원 배열을 사용하여 간단한 코드를 작성한 다음 IL 분해기를 사용하여 컴파일 된 어셈블리를 검사하면 Jagged (또는 단일 치수) 배열의 저장 및 검색이 간단한 IL 명령어임을 알 수 있습니다. 항상 느린 호출.
다음 방법을 고려하십시오.
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;
}
그들의 IL은 다음과 같습니다.
.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
Jagged Array를 사용하면 Row Swap 및 Row Resize와 같은 작업을 쉽게 수행 할 수 있습니다. 어쩌면 다차원 배열의 사용이 더 안전 할 수도 있지만, Microsoft FXCOP조차도 프로젝트를 분석하는 데 사용할 때는 다차원 대신 들쭉날쭉 한 배열을 사용해야한다고 말합니다.
다른 팁
다차원 배열은 멋진 선형 메모리 레이아웃을 생성하는 반면, 들쭉날쭉 한 배열은 여러 수준의 간접 수준을 의미합니다.
가치를 찾고 있습니다 jagged[3][6] 들쭉날쭉 한 배열에서 var jagged = new int[10][5] 다음과 같이 작동합니다. 인덱스 3 (배열)의 요소를 찾아 해당 배열 (값)의 인덱스 6의 요소를 찾으십시오. 이 경우 각 차원마다 추가 조회가 있습니다 (이것은 비싼 메모리 액세스 패턴입니다).
다차원 배열은 메모리에 선형으로 배치되며, 실제 값은 인덱스를 곱하여 발견됩니다. 그러나 배열이 주어지면 var mult = new int[10,30],, Length 해당 다차원 배열의 특성은 총 요소의 수를 반환합니다. 즉, 10 * 30 = 300.
그만큼 Rank 들쭉날쭉 한 배열의 속성은 항상 1이지만 다차원 배열은 모든 순위를 가질 수 있습니다. 그만큼 GetLength 모든 배열의 방법을 사용하여 각 차원의 길이를 얻을 수 있습니다. 이 예에서 다차원 배열의 경우 mult.GetLength(1) 반환 30.
다차원 배열을 색인화하는 것이 더 빠릅니다. 예를 들어이 예에서 다차원 배열이 주어졌습니다 mult[1,7] = 30 * 1 + 7 = 37, 해당 색인 37에서 요소를 가져옵니다. 이것은 하나의 메모리 위치 만 관련되기 때문에 더 나은 메모리 액세스 패턴입니다. 이는 배열의 기본 주소입니다.
따라서 다차원 배열은 연속 메모리 블록을 할당하는 반면, 들쭉날쭉 한 배열은 정사각형 일 필요는 없습니다. jagged[1].Length 동일 할 필요가 없습니다 jagged[2].Length, 이는 다차원 배열에 해당됩니다.
성능
성능 현명하고 다차원 배열이 더 빠르야합니다. 훨씬 더 빠르지 만 CLR 구현이 실제로 나쁜 구현으로 인해 그렇지 않습니다.
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
첫 번째 행은 들쭉날쭉 한 배열의 타이밍이며, 두 번째 행은 다차원 배열을 보여주고 세 번째는 그렇습니다. 이 프로그램은 아래에 나와 있습니다. fyi 이것은 모노를 실행하는 것으로 테스트되었습니다. (Windows 타이밍은 대부분 CLR 구현 변동으로 인해 크게 다릅니다).
창에서, 들쭉날쭉 한 배열의 타이밍은 다차원 배열이 어떤 모습인지에 대한 내 자신의 해석과 거의 같으며, 'Single ()'를 참조하십시오. 안타깝게도 Windows Jit-Compiler는 정말 어리 석고 불행히도 이러한 성능 토론을 어렵게 만들었습니다. 너무 많은 불일치가 있습니다.
이것들은 내가 창에서 얻은 타이밍입니다. 여기에서 같은 거래, 첫 번째 행은 들쭉날쭉 한 배열, 두 번째 다차원 및 세 번째 다차원 구현, 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
소스 코드:
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();
}
}
다차원 배열은 DBMS의 테이블과 유사합니다.
배열 배열 (Jagged Array)을 사용하면 각 요소가 동일한 유형의 변수 길이의 다른 배열을 보유 할 수 있습니다.
따라서 데이터 구조가 테이블 (고정 행/열)처럼 보이면 다차원 배열을 사용할 수 있습니다. Jagged Array는 고정 요소이며 각 요소는 변수 길이 배열을 보유 할 수 있습니다.
예 : psuedocode :
int[,] data = new int[2,2];
data[0,0] = 1;
data[0,1] = 2;
data[1,0] = 3;
data[1,1] = 4;
위의 것을 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 };
위의 열을 가변 수의 열이있는 각 행이라고 생각하십시오.
1 | 2 | 3 | 4 11 | 12 21 | 22 | 23
머리말: 이 의견은 다루기위한 것입니다 Okutane이 제공 한 답변, 그러나 어리석은 평판 시스템 때문에, 나는 그것이 속한 곳에 게시 할 수 없습니다.
메소드 호출로 인해 하나가 다른 것보다 느리다는 주장은 정확하지 않습니다. 하나는 더 복잡한 경계 확인 알고리즘으로 인해 다른 하나보다 느립니다. IL이 아니라 컴파일 된 어셈블리를 보면서 쉽게 확인할 수 있습니다. 예를 들어, 내 4.5 설치에서 ECX에 의해 가리키는 2 차원 배열에 저장된 요소 (EDX의 포인터를 통해)에 액세스하면 EAX에 저장된 인덱스가 있는데, EDX는 다음과 같습니다.
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]
여기서 메소드 호출의 오버 헤드가 없음을 알 수 있습니다. 바운드 점검은 제로 인덱스가 아닌 인덱스의 가능성 덕분에 매우 복잡합니다. 이는 들쭉날쭉 한 배열과 함께 제공되지 않는 기능입니다. 0이 아닌 사례에 대해 서브, CMP 및 JMP를 제거하면 코드가 거의 해결됩니다. (x*y_max+y)*sizeof(ptr)+sizeof(array_header). 이 계산은 요소에 임의의 액세스를 위해 다른 어떤 것과 같이, 우리가 두 비트의 힘으로 크기로 크기를 선택하는 바이트를 선택한 모든 이유이기 때문에이 계산은 빠르고 (하나는 교대로 대체 될 수 있습니다.
또 다른 합병증은 최신 컴파일러가 단일 차원 배열을 반복하면서 요소 액세스를 위해 중첩 된 경계 확인을 최적화하는 많은 경우가 있다는 것입니다. 결과는 기본적으로 배열의 인접한 메모리보다 인덱스 포인터를 발전시키는 코드입니다. 다차원 배열에 대한 순진한 반복에는 일반적으로 중첩 논리의 추가 레이어가 포함되므로 컴파일러는 작업을 최적화 할 가능성이 적습니다. 따라서 단일 요소에 액세스하는 오버 헤드가 배열 치수 및 크기와 관련하여 일정한 런타임으로 상각되지만 차이를 측정하는 간단한 테스트 케이스는 실행하는 데 여러 배가 더 걸릴 수 있습니다.
나는 이것에 대해 업데이트하고 싶습니다. 왜냐하면 .NET 코어 다차 차원 배열은 들쭉날쭉 한 배열보다 빠릅니다. 나는 시험을 실행했다 존 리즈 그렌 그리고 이것들은 .NET Core 2.0 미리보기의 결과입니다. 2는 배경 앱의 가능한 영향을 줄 수 있도록 차원 값을 증가 시켰습니다.
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
나는 disassemblies를 살펴 보았고 이것이 내가 찾은 것입니다.
jagged[i][j][k] = i * j * k; 실행하려면 34 개의 지침이 필요했습니다
multi[i, j, k] = i * j * k; 실행하려면 11 개의 지침이 필요했습니다
single[i * dim * dim + j * dim + k] = i * j * k; 실행하려면 23 개의 지침이 필요했습니다
단일 차원 어레이가 다차원보다 여전히 빠른 이유를 식별 할 수 없었지만 CPU에서 이루어진 최적화와 관련이 있다고 생각합니다.
다차원 배열은 (N-1) 차원 행렬입니다.
그래서 int[,] square = new int[2,2] 정사각형 매트릭스 2x2, int[,,] cube = new int [3,3,3] 큐브 - 사각형 매트릭스 3x3입니다. 비례가 필요하지 않습니다.
Jagged Array는 배열 배열 일뿐입니다. 각 셀에는 배열이 포함 된 배열입니다.
따라서 MDA는 비례하지 않으며 JD는 그렇지 않을 수 있습니다! 각 셀에는 임의의 길이가 포함될 수 있습니다!
이것은 위의 답변에서 언급되었지만 명시 적으로 언급되지 않았을 수도 있습니다. Jagged Array를 사용하면 사용할 수 있습니다. array[row] 전체 데이터 행을 참조하려면 멀티 -D 배열에는 허용되지 않습니다.
Idlasm이 생성 한 .il 파일을 구문 분석하여 어셈블리, 클래스, 방법 및 전환을 사용하기위한 저장 절차의 데이터베이스를 구축합니다. 나는 다음을 발견했다.
.method private hidebysig instance uint32[0...,0...]
GenerateWorkingKey(uint8[] key,
bool forEncryption) cil managed
서적 전문가 .NET 2.0 IL 어셈블러, Serge Lidin, Apress, 2006, 8 장, 원시 유형 및 서명, pp. 149-150에 대해 설명합니다.
<type>[] 벡터라고합니다 <type>,
<type>[<bounds> [<bounds>**] ] 배열이라고합니다 <type>
** 수단을 반복 할 수 있습니다. [ ] 선택 사항을 의미합니다.
예 :하자 <type> = int32.
1) int32[...,...] 정의되지 않은 하한 및 크기의 2 차원 배열입니다.
2) int32[2...5] 하한 2 및 크기 4의 1 차원 배열입니다.
3) int32[0...,0...] 하한 0 및 정의되지 않은 크기의 2 차원 배열입니다.
톰
다른 답변 외에도 다차원 배열은 힙에 하나의 큰 청키 물체로 할당됩니다. 이것은 몇 가지 의미가 있습니다.
- 일부 다차원 배열은 대형 물체 힙 (LOH)에 할당되어 동등한 들쭉날쭉 한 배열 대응 물에도 할당되지 않습니다.
- GC는 다차원 배열을 할당하기 위해 단일 연속 무료 메모리 블록을 찾아야하는 반면, 들쭉날쭉 한 배열은 힙 조각화로 인한 간격을 채울 수 있습니다 ... 이것은 압축으로 인해 .NET에서 문제가되지 않습니다. , 그러나 LOH는 기본적으로 압축되지 않습니다 (요청해야하며 원할 때마다 요청해야합니다).
- 당신은 조사하고 싶을 것입니다
<gcAllowVeryLargeObjects>다차원 배열 용 방법 Jagged Array 만 사용하면 문제가 발생하기 전에 발생합니다.
