어레이 데이터 구조

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '어레이 데이터 구조'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2008년 9월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

컴퓨터 과학에서 배열 데이터 구조(array data structure)는 요소(값 또는 변수)의 집합으로 구성된 데이터 구조이며, 각각은 적어도 하나의 배열 인덱스 또는 키로 식별됩니다.각 요소의 위치가 그 인덱스 태플로부터 수학식으로 ^[1][2][3]계산되도록 어레이를 기억한다.가장 단순한 데이터 구조 유형은 1차원 배열이라고도 하는 선형 배열입니다.

예를 들어 인덱스가 0 ~9인 10개의 32비트(4바이트) 정수 변수 배열은 메모리 주소 2000, 2004, 2008, ..., 2036(16진수:0x7D0,0x7D4,0x7D8, ...,0x7F4인덱스가 i인 요소가 주소 2000 + (i × 4)^[4]를 갖도록 합니다.

어레이의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기본 주소 또는 기본 주소라고 합니다.

행렬의 수학적 개념은 2차원 격자로 표현될 수 있기 때문에, 2차원 배열은 때때로 행렬이라고도 불립니다.어떤 경우에는 벡터가 아니라 튜플이 수학적으로 더 정확한 등가이긴 하지만, "벡터"라는 용어가 컴퓨팅에서 배열을 가리키기 위해 사용됩니다.테이블은 배열, 특히 룩업 테이블의 형태로 구현되는 경우가 많습니다.또한 테이블이라는 단어는 배열의 동의어로 사용되기도 합니다.

어레이는 가장 오래되고 중요한 데이터 구조 중 하나이며 거의 모든 프로그램에서 사용됩니다.또한 목록 및 문자열과 같은 다른 많은 데이터 구조 구현에도 사용됩니다.이들은 컴퓨터의 주소 지정 논리를 효과적으로 이용합니다.대부분의 현대 컴퓨터와 많은 외장 스토리지 디바이스에서 메모리는 1차원적인 단어 배열이며, 그 색인이 주소입니다.프로세서, 특히 벡터 프로세서는 어레이 동작에 최적화되어 있는 경우가 많습니다.

배열은 주로 요소 인덱스를 런타임에 계산할 수 있기 때문에 유용합니다.특히 이 기능을 통해 단일 반복문이 배열의 많은 요소를 임의로 처리할 수 있습니다.따라서 어레이 데이터 구조의 요소는 동일한 크기를 가져야 하며 동일한 데이터 표현을 사용해야 합니다.유효한 인덱스 튜플 세트와 요소의 주소(및 요소 주소 지정 공식)는 일반적으로 ^[3][5]배열이 사용되는 동안 고정되지만 항상 ^[2]고정되는 것은 아닙니다.

배열이라는 용어는 대부분의 고급 프로그래밍 언어에 의해 제공되는 데이터 유형인 배열 데이터 유형을 의미하는데, 런타임에 계산된 하나 이상의 인덱스에 의해 선택될 수 있는 값 또는 변수의 집합으로 구성됩니다.어레이 유형은 어레이 구조에 의해 구현되는 경우가 많지만, 일부 언어에서는 해시 테이블, 링크 목록, 검색 트리 또는 기타 데이터 구조에 의해 구현될 수 있습니다.

이 용어는 특히 알고리즘 설명에서 어레이의 필수 속성을 캡처하기 위한 이론적 컴퓨터 과학 모델인 "추상 배열" 또는 "추상 배열"을 의미하기 위해 사용됩니다.

역사

최초의 디지털 컴퓨터는 기계 언어 프로그래밍을 사용하여 데이터 테이블, 벡터 및 매트릭스 계산 및 기타 많은 목적으로 배열 구조를 설정하고 액세스했습니다.John von Neumann은 최초의 저장 프로그램 컴퓨터를 만드는 ^{[6]p. 159}동안 1945년에 최초의 배열 정렬 프로그램(머지 정렬)을 작성했습니다.배열 인덱싱은 원래 코드를 스스로 수정하고 나중에 인덱스 레지스터와 간접 주소 지정을 사용하여 수행되었습니다.Burroughs B5000 및 그 후계기 등 1960년대에 설계된 일부 메인프레임에서는 메모리 세그멘테이션을 사용하여 ^[7]하드웨어에서 인덱스 바운드를 체크했습니다.

어셈블리 언어에서는 일반적으로 머신 자체에서 제공하는 기능 이외에는 어레이를 특별히 지원하지 않습니다.FORTRAN(1957), Lisp(1958), COBOL(1960) 및 ALGOL 60(1960)을 포함한 최초의 고급 프로그래밍 언어는 다차원 배열을 지원했으며 C(1972)도 지원했다.C++(1983)에서는 런타임에^[3][5] 치수가 고정된 다차원 배열과 런타임에 유연한 ^[2]배열에 대한 클래스 템플릿이 존재한다.

적용들

배열은 다른 종류의 직사각형 테이블뿐만 아니라 수학적 벡터 및 행렬을 구현하기 위해 사용됩니다.크고 작은 대부분의 데이터베이스는 레코드가 요소인 1차원 배열로 구성됩니다(또는 포함).

배열은 목록, 힙, 해시 테이블, 디큐, 큐, 스택, 문자열 및 VLicast와 같은 다른 데이터 구조를 구현하기 위해 사용됩니다.다른 데이터 구조의 어레이 기반 구현은 단순하고 공간 효율적인(암묵적인 데이터 구조) 경우가 많아 공간 오버헤드가 거의 필요하지 않지만 트리 기반 데이터 구조(소트된 어레이를 검색 트리와 비교)에 비해 특히 변경 시 공간 복잡성이 낮을 수 있습니다.

프로그램 내 동적 메모리 할당, 특히 메모리 풀 할당을 에뮬레이트하기 위해 하나 이상의 대규모 어레이가 사용될 수 있습니다.이전에는, 「다이나믹 메모리」를 휴대용으로 할당하는 유일한 방법이었습니다.

어레이를 사용하여 프로그램의 일부 또는 완전한 제어 흐름을 결정할 수 있습니다(반복하지 않을 경우).IF 진술들.이 컨텍스트에서는 제어 테이블이라고 하며 어레이에 포함된 값에 따라 제어 플로우가 변경되는 전용 빌드 인터프리터와 함께 사용됩니다.배열에는 실행 경로를 지시하는 서브루틴 포인터(또는 SWITCH 문에 의해 동작할 수 있는 상대 서브루틴 번호)를 포함할 수 있습니다.

요소 식별자 및 주소 지정 공식

데이터 개체가 배열에 저장될 때 개별 개체는 일반적으로 음이 아닌 스칼라 정수인 인덱스에 의해 선택됩니다.인덱스는 첨자라고도 합니다.인덱스는 배열 값을 저장된 개체에 매핑합니다.

배열 요소를 인덱싱하는 방법에는 다음 세 가지가 있습니다.

0(제로 기반 인덱싱)

배열의 첫 번째 요소는 첨자 ^[8]0으로 인덱싱됩니다.

1 (1 베이스 인덱스화)

배열의 첫 번째 요소는 첨자 1로 인덱싱됩니다.

n(n 기반 인덱싱)

배열의 기본 인덱스는 자유롭게 선택할 수 있습니다.일반적으로 n 기반 인덱싱을 허용하는 프로그래밍 언어에서는 음의 인덱스 값 및 열거와 같은 기타 스칼라 데이터 유형도 허용하거나 문자를 배열 인덱스로 사용할 수 있습니다.

제로 베이스 인덱싱을 사용하는 것은 C, Java 및 Lisp를 포함한 많은 영향력 있는 프로그래밍 언어의 설계 선택입니다.따라서 첨자가 배열의 시작 위치로부터의 오프셋을 참조하기 때문에 첫 번째 요소의 오프셋은 0이 됩니다.

어레이는 여러 차원을 가질 수 있기 때문에 여러 인덱스를 사용하여 어레이에 액세스하는 것은 드문 일이 아닙니다.예를 들어, 2차원 배열은A행이 3개, 열이 4개인 경우 식에 따라 두 번째 행과 네 번째 열의 요소에 액세스할 수 있습니다.A[1][3]제로 베이스 인덱싱 시스템의 경우.따라서 2차원 배열에는 2개의 인덱스가, 3차원 배열에는 3개의 인덱스가, n차원 배열에는 n개의 인덱스가 사용됩니다.

요소를 지정하는 데 필요한 인덱스 수를 배열의 치수, 치수 또는 순위라고 합니다.

표준 배열에서 각 인덱스는 연속된 정수(또는 열거된 유형의 연속된 값)의 특정 범위로 제한되며 요소의 주소는 인덱스의 "선형" 공식에 의해 계산됩니다.

1차원 어레이

1차원 배열(또는 단일 차원 배열)은 선형 배열의 한 종류입니다.해당 요소에 액세스하려면 행 또는 열 인덱스를 나타낼 수 있는 단일 첨자가 필요합니다.

예로서 C 선언을 고려합니다.int anArrayName[10];10개의 정수로 이루어진 1차원 배열을 선언합니다.여기서 어레이는 10가지 유형의 요소를 저장할 수 있습니다.int이 배열은 0에서 9까지의 인덱스를 가지고 있습니다.예를 들어 표현식anArrayName[0]그리고.anArrayName[9]는 각각 첫 번째 요소와 마지막 요소입니다.

선형 어드레싱을 사용하는 벡터의 경우 지수 i를 가진 요소는 주소 B + c × i에 위치합니다. 여기서 B는 고정 베이스 주소이고 c는 고정 상수이며 주소 증분 또는 스트라이드라고도 합니다.

유효한 요소 인덱스가 0에서 시작하는 경우 상수 B는 단순히 배열의 첫 번째 요소의 주소입니다.이러한 이유로 C 프로그래밍 언어는 배열 인덱스가 항상 0에서 시작되도록 지정합니다. 많은 프로그래머는 이 요소를 "first"가 아니라 "zeroth"라고 부릅니다.

다만, 베이스 주소 B의 적절한 선택에 의해서, 제1 요소의 인덱스를 선택할 수 있다.예를 들어 배열에 인덱스1 ~ 5의 5개의 요소가 있고 베이스 주소 B가 B + 30c로 대체되어 있는 경우 동일한 요소의 인덱스는 31 ~35가 됩니다번호가 0으로 시작하지 않으면 상수 B는 요소의 주소가 될 수 없습니다.

다차원 어레이

다차원 배열의 경우, 지수 i, j를 가진 요소는 주소 B + c · i + d · j를 가질 것이다.여기서 계수 c와 d는 각각 행과 열 주소의 증분이다.

보다 일반적으로 k차원 배열에서 인덱스가₁ i, i₂, ..., i인_k 요소의 주소는

B + c₁ · i₁ + c₂ · i₂ + … + c_k · i_k

예: int a [ 2 ] [ 3 ] ;

즉, 어레이 a에는 2행 3열이 있으며 어레이는 정수형입니다.여기서는 6개의 요소를 선형으로 저장할 수 있지만 첫 번째 행에서 선형으로 시작하여 두 번째 행으로 계속됩니다.위의 배열은 a, a₁₂, a₁₃, a₂₁, a₂₂, a, a, a로₂₃ 저장됩니다₁₁.

이 공식은 메모리에 들어갈 수 있는 배열에 대해 k의 곱셈과 k의 덧셈만 필요합니다.또, 어느 계수가 2의 고정 거듭제곱이라면, 곱셈을 비트 시프트로 대체할 수 있다.

모든 유효한 인덱스 태플이 개별 요소의 주소에 매핑되도록 계수_k c를 선택해야 합니다.

모든 인덱스의 최소 법적 값이 0인 경우 B는 인덱스가 모두 0인 요소의 주소입니다.1차원 경우와 마찬가지로 베이스 어드레스 B를 변경함으로써 요소 인덱스를 변경해도 된다.따라서 2차원 배열에 각각 1에서 10까지 및 1에서 20까지 색인이 지정된 행과 열이 있는 경우 B를₁ B + c₂ - 3c로 대체하면 각각 0에서 9까지 및 4에서 23까지 번호가 다시 지정됩니다.이 기능을 이용하여 일부 언어(FORTRAN 77 등)는 수학적 전통에서와 같이 배열 인덱스가 1로 시작되도록 지정하고 다른 언어(Fortran 90, Pascal 및 Algol 등)는 사용자가 각 인덱스의 최소값을 선택할 수 있도록 합니다.

도프 벡터

어드레싱 공식은 치수 d, 기본 주소 B 및 증분₁ c₂, c, c_k, ..., c로 완전히 정의됩니다.이러한 파라미터를 배열의 디스크립터 또는 스트라이드 벡터 ^[2][3]또는 도프 벡터라고 불리는 레코드에 넣는 것이 많은 경우 유용합니다.각 요소의 크기와 각 지수에 허용되는 최소값과 최대값을 도프 벡터에 포함할 수 있다.도프 벡터는 어레이의 완전한 핸들로서 프로시저의 인수로서 어레이를 건네주는 편리한 방법입니다.도프 ^[2]벡터를 조작함으로써 많은 유용한 어레이 슬라이스 조작(서브 어레이 선택, 인덱스 스왑 또는 인덱스 방향 반전 등)을 매우 효율적으로 실행할 수 있다.

콤팩트한 레이아웃

종종 계수는 요소가 메모리의 인접 영역을 차지하도록 선택됩니다.하지만 그럴 필요는 없습니다.어레이는 항상 연속적인 요소로 작성되어 있어도 일부 어레이 슬라이싱 조작에 의해 이들 요소로부터 비연속적인 서브 어레이가 작성될 수 있습니다.

2차원 배열에는 두 가지 체계적인 소형 레이아웃이 있습니다.예를 들어, 행렬을 고려합니다.

$({displaystyle A=bmatrix}1&2&3\4&5&6\7&8&9\end{bmatrix})}$

줄자 순서 레이아웃(정적으로 선언된 배열의 경우 C에 의해 채택됨)에서는 각 행의 요소는 연속된 위치에 저장되며 행의 모든 요소는 연속된 행의 요소보다 낮은 주소를 가집니다.

1

2

3

4

5

6

7

8

9

(종래 Fortran에서 사용되던) 줄자 순서로 각 열의 요소는 메모리에 연속되며 열의 모든 요소는 연속된 열의 요소보다 낮은 주소를 가집니다.

1

4

7

2

5

8

3

6

9

인덱스가 3개 이상인 배열의 경우 "행 주순서"는 인덱스 튜플이 마지막 인덱스에서 하나만 다른 두 요소를 연속된 위치에 배치합니다."컬럼 메이저 순서"는 첫 번째 지수와 유사하다.

프로세서 캐시 또는 가상 메모리를 사용하는 시스템에서는 연속적인 요소를 메모리의 연속된 위치에 저장하면 어레이 스캔이 매우 빠릅니다.다차원 배열을 사용하는 대부분의 알고리즘은 예측 가능한 순서로 배열을 검색합니다.프로그래머(또는 고도의 컴파일러)는 이 정보를 사용하여 각 배열의 행 또는 열 메이저 레이아웃 중 하나를 선택할 수 있습니다.예를 들어 두 행렬의 곱 A·B를 계산할 때는 A를 줄자 순서로, B를 줄자 순서로 저장하는 것이 가장 좋습니다.

크기 조정

정적 배열은 생성 시 크기가 고정되어 있으므로 요소를 삽입하거나 제거할 수 없습니다.다만, 새로운 어레이를 할당해, 낡은 어레이의 내용을 카피하는 것으로, 어레이의 동적 버전을 효과적으로 실장할 수 있습니다.다이나믹 어레이를 참조해 주세요.이 작업을 자주 수행하지 않으면 어레이 끝에 삽입할 때 상각된 상수 시간만 필요합니다.

일부 어레이 데이터 구조에서는 스토리지를 재할당하지 않지만 사용 중인 어레이 요소 수(카운트 또는 크기)를 저장합니다.따라서 어레이는 최대 크기 또는 용량이 고정된 동적 어레이가 됩니다.Pascal 문자열이 그 예입니다.

비선형 공식

더 복잡한(비선형) 공식도 가끔 사용됩니다.예를 들어 콤팩트한 2차원 삼각 어레이의 경우 주소 지정식은 도수 2의 다항식이다.

효율성.

둘 다 take(결정적 최악의 경우) 상수 시간을 저장하고 선택합니다.배열은 보유하고 있는 요소 수 n에서 선형(O(n) 공간을 사용합니다.

요소 사이즈가 k인 어레이와 캐시 라인 사이즈가 B바이트인 머신에서 n개의 요소 배열을 통해 반복할 경우 요소가 인접한 메모리 위치를 차지하기 때문에 최소의 캐시 누락이 필요합니다.이는 랜덤 메모리 위치에서 n개의 요소에 액세스하기 위해 필요한 캐시 누락 수보다 B/k의 대략적인 요인이 됩니다.그 결과, 어레이상의 시퀀셜 반복은, 참조의 인접성이라고 불리는 속성(단, 같은 (로컬) 어레이내에서 완전한 해시 또는 사소한 해시를 사용하는 것이, 보다 고속이 아니고, 일정시간내에 달성할 수 있는 것은 아닙니다).라이브러리는 메모리 범위(memcpy 등)를 복사하기 위해 저레벨로 최적화된 기능을 제공합니다.이 기능을 사용하면 어레이 요소의 연속된 블록을 개별 요소 액세스를 통해 이동하는 것보다 훨씬 빠르게 이동할 수 있습니다.이러한 최적화된 루틴의 속도 향상은 어레이 요소의 크기, 아키텍처 및 구현에 따라 달라집니다.

메모리 측면에서 어레이는 요소별 오버헤드가 없는 콤팩트한 데이터 구조입니다.배열별 오버헤드(예: 인덱스 경계 저장)가 있을 수 있지만 이는 언어에 따라 다릅니다.또한 어레이에 저장된 요소가 개별 변수에 저장된 동일한 요소보다 적은 메모리를 필요로 하는 경우도 있습니다. 이는 여러 어레이 요소를 한 단어로 저장할 수 있기 때문입니다. 이러한 어레이를 종종 패킹된 어레이라고 합니다.극단적인 경우(일반적으로 사용됨)는 비트 배열이며, 여기서 모든 비트는 단일 요소를 나타냅니다.따라서 단일 옥텟은 최대 8개의 다른 조건의 256개의 다른 조합을 가장 콤팩트한 형태로 유지할 수 있습니다.

정적으로 예측 가능한 액세스 패턴을 가진 어레이 액세스는 데이터 병렬화의 주요 소스입니다.

다른 데이터 구조와의 비교

목록 데이터 구조 비교

	훔쳐보다 (인덱스)	변환(삽입 또는 삭제)			여유 공간, 평균
		시작	끝.	가운데
링크 리스트	θ(n)	θ(1)	δ(1), 알려진 엔드 요소 δ(n), 알 수 없는 엔드 요소	Peek 시간 + θ(1)[9][10]	θ(n)
어레이	θ(1)	—	—	—	0
다이내믹 어레이	θ(1)	θ(n)	θ(1)상각	θ(n)	θ([11]n)
밸런스 트리	δ(로그 n)	δ(로그 n)	δ(로그 n)	δ(로그 n)	θ(n)
랜덤 액세스리스트	δ([12]로그 n)	θ(1)	--[12]	--[12]	θ(n)
해시 어레이 트리	θ(1)	θ(n)	θ(1)상각	θ(n)	θ(nn)

동적 어레이 또는 확장 가능한 어레이는 어레이와 비슷하지만 요소를 삽입 및 삭제하는 기능이 추가됩니다.특히 마지막에 추가 및 삭제가 효율적입니다.그러나 어레이는 추가 스토리지를 예약하지 않고 선형(δ(n)) 스토리지를 추가로 예약합니다.

연관 배열은 인덱스 값이 희박할 때 큰 스토리지 오버헤드 없이 어레이와 같은 기능을 제공하는 메커니즘을 제공합니다.예를 들어 인덱스 10과 20억의 값만 포함하는 배열은 이러한 구조를 사용하는 것이 좋습니다.정수 키를 가진 특수 연상 배열에는 Patricia tries, Judy 배열 및 van Emde Boas 트리가 포함됩니다.

밸런스 트리는 인덱스된 액세스에 O(log n) 시간이 필요하지만 O(^[13]log n) 시간 내에 요소를 삽입 또는 삭제할 수 있는 반면 확장 가능한 배열에서는 임의의 위치에 요소를 삽입 또는 삭제할 수 있는 선형(δ(n) 시간이 필요합니다.

링크된 목록을 사용하면 중간에 시간을 지속적으로 제거하고 삽입할 수 있지만 인덱스된 액세스에는 선형 시간이 걸립니다.일반적으로 메모리 사용량은 어레이보다 낮지만 여전히 선형적입니다.

엘리프 벡터는 다차원 배열 구조의 대안이다.1차원보다 작은 배열에 대한 참조의 1차원 배열을 사용합니다.특히 2차원의 경우, 이 대체 구조는 각 행(c 또는 c++의 포인터)에 대해 하나씩 벡터에 대한 포인터의 벡터입니다.따라서 배열 A의 행 i 및 열 j에 있는 요소는 이중 인덱싱(일반 표기법으로는 A[i][j])을 통해 액세스됩니다.이 대체 구조를 사용하면 각 행의 크기가 다를 수 있고, 일반적으로 각 지수의 유효 범위가 이전의 모든 지수의 값에 따라 달라지는 들쭉날쭉한 배열이 가능하다.또한 비트 시프트(행 포인터의 벡터 인덱스를 작성하기 위해)와 추가 메모리 액세스(행 주소 가져오기)로 대체되는 하나의 곱셈(열 주소 증분)을 저장합니다.이것은 일부 아키텍처에서 가치가 있을 수 있습니다.

치수

배열의 치수는 요소를 선택하는 데 필요한 인덱스 수입니다.따라서 배열이 가능한 인덱스 조합 집합의 함수로 간주될 경우 해당 도메인이 이산 서브셋인 공간의 차원입니다.따라서 1차원 배열은 데이터 리스트, 2차원 배열은 데이터의 ^[14]직사각형, 3차원 배열은 데이터 블록 등입니다.

이 값을 특정 도메인을 가진 모든 행렬 집합의 차원, 즉 배열 내의 요소 수와 혼동해서는 안 됩니다.예를 들어, 5행 4열의 배열은 2차원이지만 이러한 행렬은 20차원 공간을 형성합니다.마찬가지로 3차원 벡터는 크기 3의 1차원 배열로 나타낼 수 있다.

「 」를 참조해 주세요.

레퍼런스

외부 링크

• Wikibooks에서의 데이터 구조/어레이