동적 배열

섬네일|여러 개의 값들이 기하학적 확장을 이용하여 동적 배열의 끝에 삽입되어 있다. 회색 셀들은 확장을 위해 예비된 공간을 의미한다. 삽입된 대부분 항목들은 (일정 시간) 빠르지만, 일부는 재할당이 필요하여 느리다. 마지막 배열의 논리적인 크기와 용량이 그림에 나타나 있다.
동적 배열()은 프로그래밍에서 크기가 고정되지 않은 배열을 의미한다. 일례로 C++ 표준 템플릿 라이브러리에서는 vector라는 타입이 동적 배열을 지원한다.

동적 배열은 동적 할당 배열과는 다르다. 동적 할당 배열은 배열이 할당될 때 크기가 고정되는 배열이지만 동적 배열은 이러한 고정 크기 배열을 백엔드로 사용할 수 있다.

 고정 크기 동적 배열과 용량 

간단한 동적 배열은 일반적으로 즉시 필요한 요소의 수보다 큰 고정 크기 배열을 할당하여 구성할 수 있다. 동적 배열의 요소는 기본 배열의 시작 부분에 연속적으로 저장되며, 기본 배열의 끝 부분에 있는 나머지 위치는 예약되거나 사용되지 않는다. 예약된 공간을 사용하여 동적 배열의 끝에 요소를 상수 시간에 추가할 수 있으며, 이 공간이 완전히 소모될 때까지 가능하다. 모든 공간이 소모되고 추가 요소를 추가해야 할 때, 기본 고정 크기 배열의 크기를 늘려야 한다. 일반적으로 크기 조정은 새 기본 배열을 할당하고 원본 배열에서 각 요소를 복사해야 하므로 비용이 많이 든다. 동적 배열의 끝에서 요소는 크기 조정이 필요 없으므로 상수 시간에 제거될 수 있다. 동적 배열 내용에 사용되는 요소의 수는 논리적 크기 또는 크기라고 불리며, 기본 배열의 크기는 동적 배열의 용량 또는 물리적 크기라고 불리며, 데이터를 재배치하지 않고 가능한 최대 크기이다.

최대 논리적 크기가 고정되거나(예: 사양에 의해) 배열이 할당되기 전에 계산될 수 있는 응용 프로그램에서는 고정 크기 배열이면 충분하다. 다음과 같은 경우 동적 배열이 선호될 수 있다:
 배열이 할당되기 전에 최대 논리적 크기를 알 수 없거나 계산하기 어렵다.
 사양에 의해 주어진 최대 논리적 크기가 변경될 가능성이 있다고 판단된다.
 동적 배열의 크기 조정에 대한 분할 상환 비용이 성능이나 응답성에 크게 영향을 미치지 않는다.

 기하급수적 확장 및 분할 상환 비용 

크기 조정 비용을 여러 번 부담하는 것을 피하기 위해 동적 배열은 크기를 두 배로 늘리는 등 크게 조정하고, 예약된 공간을 향후 확장에 사용한다. 끝에 요소를 추가하는 작업은 다음과 같이 작동할 수 있다:
function insertEnd(dynarray a, element e)
 if (a.size == a.capacity)
 // a의 현재 용량을 두 배로 늘린다:
 a.capacity ← a.capacity * 2
 // (여기에 내용을 새 메모리 위치로 복사한다)
 a[a.size] ← e
 a.size ← a.size + 1
n개의 요소가 삽입될 때, 용량은 등비수열을 이룬다. 배열을 일정한 비율 a로 확장하면 n개의 요소를 삽입하는 데 전체적으로 O(n) 시간이 걸리며, 이는 각 삽입이 분할 상환 상수 시간을 소요함을 의미한다. 많은 동적 배열은 크기가 용량의 30%와 같은 특정 임계값 아래로 떨어지면 기본 저장 공간의 일부를 할당 해제한다. 이 임계값은 이력 현상을 제공하고 (반복적인 확장 및 축소를 피하기 위한 안정적인 대역을 제공) 분할 상환 상수 비용으로 삽입 및 제거의 혼합 시퀀스를 지원하기 위해 1/a보다 엄격하게 작아야 한다.

동적 배열은 분할 상환 분석을 가르칠 때 흔히 사용되는 예시이다.

 성장 인자 
동적 배열의 성장 인자는 공간-시간 트레이드오프 및 메모리 할당자 자체에서 사용되는 알고리즘을 포함한 여러 요인에 따라 달라진다. 성장 인자 a의 경우, 삽입 작업당 평균 시간은 약 a/(a−1)이고, 낭비되는 셀의 수는 (a−1)n으로 제한된다. 메모리 할당자가 최초 적합 할당 알고리즘을 사용하는 경우, a=2와 같은 성장 인자 값은 상당한 양의 메모리가 여전히 사용 가능하더라도 동적 배열 확장이 메모리 부족을 일으킬 수 있다. 황금비와 1.5 값을 포함하여 이상적인 성장 인자 값에 대한 다양한 논의가 있었다. 그러나 많은 교과서는 단순성과 분석 목적으로 a = 2를 사용한다.

다음은 여러 인기 있는 구현에서 사용되는 성장 인자이다.

 성능 
동적 배열은 배열과 유사한 성능을 가지며, 요소를 추가하고 제거하는 새로운 작업이 추가된다.

 특정 인덱스의 값을 가져오거나 설정하기 (상수 시간)
 요소를 순서대로 반복하기 (선형 시간, 좋은 캐시 성능)
 배열 중간에 요소 삽입 또는 삭제 (선형 시간)
 배열 끝에 요소 삽입 또는 삭제 (분할 상환 상수 시간)

동적 배열은 참조 국부성 및 데이터 캐시 활용, 압축성(낮은 메모리 사용), 임의 접근을 포함하여 배열의 많은 장점을 활용한다. 일반적으로 크기 및 용량 정보 저장을 위한 작은 고정 추가 오버헤드만 있다. 이로 인해 동적 배열은 캐시 친화적인 자료 구조를 구축하기 위한 매력적인 도구가 된다. 그러나 파이썬이나 자바와 같이 참조 의미론을 강제하는 언어에서는 동적 배열이 실제 데이터를 저장하지 않고, 메모리의 다른 영역에 있는 데이터에 대한 참조를 저장하는 경우가 많다. 이 경우 배열의 항목을 순차적으로 액세스하는 것은 실제로 여러 개의 비연속적인 메모리 영역을 액세스하는 것을 수반하므로, 이 자료 구조의 캐시 친화성의 많은 장점이 상실된다.

연결 리스트와 비교하여 동적 배열은 색인화가 더 빠르고(상수 시간 대 선형 시간) 참조 국부성 개선으로 인해 일반적으로 반복이 더 빠르다. 그러나 동적 배열은 모든 후속 요소를 이동해야 하므로 임의 위치에 삽입 또는 삭제하는 데 선형 시간이 필요한 반면, 연결 리스트는 이를 상수 시간에 수행할 수 있다. 이 단점은 아래의 변형에서 논의된 갭 버퍼 및 계층형 벡터 변형으로 완화된다. 또한, 매우 조각난 메모리 영역에서는 큰 동적 배열을 위한 연속적인 공간을 찾는 것이 비싸거나 불가능할 수 있지만, 연결 리스트는 전체 자료 구조가 연속적으로 저장될 필요가 없다.

균형 트리는 동적 배열과 연결 리스트의 모든 작업을 합리적으로 효율적으로 제공하면서 목록을 저장할 수 있지만, 목록의 끝에 삽입하는 작업과 반복하는 작업은 비연속적인 저장과 트리 탐색/조작 오버헤드로 인해 이론적으로나 실제적으로 동적 배열보다 느리다.

 변형 
갭 버퍼는 동적 배열과 유사하지만, 동일한 임의 위치 근처에 뭉쳐 있는 효율적인 삽입 및 삭제 작업을 허용한다. 일부 덱 구현은 배열 덱을 사용하는데, 이는 한쪽 끝뿐만 아니라 양쪽 끝에서 분할 상환 상수 시간 삽입/제거를 허용한다.

굿리치는 k ≥ 2인 상수 매개변수일 때, 배열의 어느 위치에서든 삽입 및 삭제에 O(n1/k) 성능을 제공하고, 가져오기 및 설정에 O(k) 성능을 제공하는 계층형 벡터(tiered vectors)라는 동적 배열 알고리즘을 발표했다.

해시 배열 트리 (HAT)는 1996년 시타르스키(Sitarski)가 발표한 동적 배열 알고리즘이다. 해시 배열 트리는 배열의 요소 수 n에 대해 n1/2만큼의 저장 공간을 낭비한다. 이 알고리즘은 해시 배열 트리의 끝에 일련의 객체를 추가할 때 O(1) 분할 상환 성능을 가진다.

1999년 논문에서 브로드닉(Brodnik) 등은 특정 시점에 n개의 요소에 대해 n1/2 공간만 낭비하는 계층형 동적 배열 자료 구조를 설명하고, 연산이 분할 상환 상수 시간으로 유지되려면 어떤 동적 배열도 이만큼의 공간을 낭비해야 한다는 하한을 증명했다. 또한, 버퍼의 확장 및 축소가 분할 상환뿐만 아니라 최악의 경우 상수 시간을 갖는 변형도 제시했다.

배그웰(Bagwell) (2002)은 동적 배열을 구현하는 데 적용할 수 있는 VList 알고리즘을 발표했다.

"가장 나쁜 구현"이라고도 불리는 순진한 크기 변경 가능 배열(naïve resizable arrays)은 배열에 추가되는 각 항목에 대해 realloc을 호출하여, 배열의 할당된 크기를 포함하는 모든 데이터에 대해 정확히 충분하게 유지한다. 순진한 크기 변경 가능 배열은 C에서 크기 변경 가능 배열을 구현하는 가장 간단한 방법이다. 메모리를 낭비하지 않지만, 배열의 끝에 추가하는 데는 항상 Θ(n) 시간이 걸린다.
선형적으로 증가하는 배열은 배열 크기를 조정할 때마다 Θ(1) 공간을 미리 할당("낭비")하여 순진한 크기 변경 가능 배열보다 훨씬 빠르다. 배열 끝에 추가하는 데는 여전히 Θ(n) 시간이 걸리지만 상수가 훨씬 작다.
순진한 크기 변경 가능 배열과 선형적으로 증가하는 배열은 공간 제약이 있는 응용 프로그램에서 많은 작은 크기 변경 가능 배열이 필요할 때 유용할 수 있다.
또한 기하급수적으로 증가하는 동적 배열로 이어지는 교육적 예시로도 흔히 사용된다.

 언어 지원 

C++의 std::vector와 러스트의 std::vec::Vec은 동적 배열의 구현이며, 자바의 java.util.ArrayList와 닷넷 프레임워크의 System.Collections.ArrayList도 마찬가지이다.

.NET Framework 버전 2.0에 제공되는 일반 System.Collections.Generic.List
 클래스도 동적 배열로 구현된다. 스몰토크의 OrderedCollection은 동적 시작 및 끝 인덱스를 가진 동적 배열로, 첫 번째 요소의 제거도 O(1)이 된다.

파이썬의 list 자료형 구현은 성장 패턴이 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...인 동적 배열이다.

델파이와 D는 언어 코어에서 동적 배열을 구현한다.

에이다의 Ada.Containers.Vectors 제네릭 패키지는 주어진 서브타입에 대한 동적 배열 구현을 제공한다.

펄 및 루비와 같은 많은 스크립트 언어는 동적 배열을 내장 원시 자료형으로 제공한다.

여러 크로스 플랫폼 프레임워크는 C를 위한 동적 배열 구현을 제공하며, 여기에는 Core Foundation의 CFArray 및 CFMutableArray, GLib의 GArray 및 GPtrArray가 포함된다.

커먼 리스프는 내장 array 타입을 조절 가능하게 구성하고 fill-pointer로 삽입 위치를 지정할 수 있도록 하여 크기 변경 가능한 벡터에 대한 기본적인 지원을 제공한다.

 각주 

분류:배열
분류:분할 상환 자료 구조