자료구조 핵심 원리 - 동적 배열

 

1.  동적 배열

초기 배열은 같은 데이터 타입을 가진 변수 집합이었습니다. 아직도 많은 언어에서 배열은 같은 타입 변수들을 저장합니다. 하지만 C 언어를 제외한 거의 대부분의 언어가 초기 형태의 배열이 아닌 동적 배열을 지원합니다. 동적 배열은 기존 배열이 가지는 장점은 유지하면서 여러 단점은 보완한 형태로 구현되었습니다.

 

메모리에 데이터를 저장하는 영역은 세 군데인데, 그중 스택과 힙 영역이 있습니다. 스택은 실제 스택 프레임(파이썬의 스택 프레임과 개념은 같지만 실제 할당되는 공간은 다름)이 쌓이는 메모리 공간이고, 힙은 변수의 생성 시기와 소멸 시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당되는 영역입니다. 동적 배열 개념을 이해하려면 스택과 힙 차이를 알아야 합니다.

 

스택 프레임을 할당하려면 미리 할당될 스택 프레임의 크기를 알고 있어야 합니다. 그래서 스택 영역에 배열을 만들기 위해서는 반드시 고정된 크기로 만들어야 했습니다. 사용할 데이터의 크기가 가변적으로 변할 수 있는 상황이라면 스택에 고정 크기를 가지는 배열을 만들어 쓰기에 어려움이 많습니다.

 

이에 반해 힙 영역은 프로그래머가 원하는 만큼 크기를 할당받을 수 있기에 일단 필요한 만큼 할당받아 데이터를 저장하다가, 많은 메모리가 필요한 순간이 오면 더 큰 공간을 확보하여 이전 배열 요소를 모두 복사한 후 새로운 데이터를 삽입할 수 있습니다. 동적 배열이란 힙 영역에 저장되는 배열을 의미합니다. C++의 vector, 자바의 ArrayList, 파이썬의 리스트가 동적 배열입니다.

 

간단히 동적 배열의 ADT(추상형 자료형)을 작성해 보겠습니다.

 

Dynamic Array
Object : 원소의 순서 있는 유한 집합 Array

Operation
1. Array.is_empty( ) -> Boolean : 리스트가 비어 있으면 TRUE, 아니면 FALSE 반환
2. Array.add_last(element) : 리스트의 마지막에 원소 추가
3. Array.insert(index, element) : 리스트의 index 위치에 element 원소 삽입
4. Array[index] -> element : 인덱싱(indexing), 인덱스에 위치한 원소 반환
5. Array.remove_last( ) -> element : 리스트의 마지막 원소를 삭제한 후 반환
6. Array.remove(index) -> element : 인덱스에 위치한 원소를 삭제하고 반환

 

 

1.1  지역성의 원리와 캐시

배열이 스택 또는 힙에 저장되면, 메모리상에서 물리적, 선형적으로 이어져 있습니다.

 

배열의 요소 1,2,3이 선형적으로 저장되어 있다.

 

배열이 선형적으로 저장되는 것은 큰 장점으로 작용하는 데, 지역성의 원리(principle of locality)와 캐시(cache)를 알아야 이해할 수 있습니다.

 

def sum_all(arr):
    ret = 0 # 1
    for elem in arr: # 2
        ret += elem
    return ret

 

위의 코드에는 연산 결과를 축적하는 ret 변수와 리스트에서 모든 요소를 하나씩 가져와 저장하는 elem 변수가 있습니다. CPU는 for 문이 수행될 때 배열의 모든 요소를 가져오면서 항상 ret 값을 먼저 가져옵니다. 이처럼 한번 접근한 변수는 계속해서 접근할 가능성이 높다는 것이 시간 지역성(temporal locality)입니다. 이번에는 배열의 요소를 생각해 봅시다. # 2 라인을 보면, 이번에 접근한 배열의 요소는 이전에 접근한 요소의 바로 다음이라는 것을 알 수 있지요. 이처럼 이번에 접근한 변수는 이전에 접근한 변수 근처에 있을 가능성이 높다는 것이 공간 지역성(spatial locality)입니다. 이런 지역성의 원리가 CPU와 메인 메모리 사이에 캐시를 두게 된 이유입니다.

 

# 1에 있는 ret 변수에 # 2의 arr에서 요소를 하나씩 가져와 ret에 더하고 있습니다. # 3 라인이 실행될 때 어떤 일이 일어나는지 한번 고민해 봅시다. CPU에는 메인 메모리에서 가져온 데이터를 일시적으로 저장할 수 있는 메모리 공간인 레지스터가 존재합니다. 이 레지스터는 그 어떤 메모리보다 빠르기 때문에 CPU가 값을 요청했을 때 1클럭 만에 데이터를 CPU 연산 장치인 ALU(Arithmetic Logic Unit)(산술 논리 장치)로 보낼 수 있습니다. 반면, 메모리에서 데이터를 가져올 때는 20~100클럭 정도가 소요됩니다.

 

# 3 라인에 있는 덧셈 연산이 실행되려면 메인 메모리에 저장된 ret 변수와 리스트 arr의 한 요소 값을 가진 elem 변수가 필요합니다. 메모리에서 바로 CPU의 연산 장치로 ret와 elem 값을 가져올 수 없으므로 반드시 CPU에 있는 메모리 공간인 레지스터로 값을 가져와야 합니다. 레지스터로 가져온 두 값은 이제야 더해집니다. 이 결괏값은 어디에 저장될까요? 다시 임시 레지스터에 저장됩니다. 임시 레지스터에 저장된 후에야 다시 메모리에 있는 ret 변수에 저장됩니다. 핵심은 간단합니다. 메인 메모리에 있는 변수는 연산을 하기 전과 후에 반드시 레지스터를 거친다는 점이지요.

 

정작 덧셈 연산은 1클럭 만에 계산되는데, 이를 위해 ret 값을 가져오는 데 최소 20클럭, 배열의 한 요소를 가져오는 데 또 20클럭, 다시 결괏값을 레지스터에서 메인 메모리의 ret로 옮기는 데 20클럭이 소요되어 최소한 60클럭 이상이 소요됩니다. 게다가 이와 같은 작업을 배열의 모든 요소에서 수행해야 합니다. 매우 비효율적이지요.

 

하드웨어 설계자들은 지역성의 원리를 토대로 이와 같은 비효율성이 엄청나게 많이 일어난다는 것을 알게 되었습니다. 이에 한 가지 발상을 합니다. CPU와 메인 메모리 사이에 성능이 빠른 버퍼로 메모리를 둔다면 이런 비효율성을 줄일 수 있지 않을까 하는 아이디어였습니다. 이에 도입된 것이 캐시입니다. 캐시가 어디에 있는지, 어떻게 작동하는지 간단하게 알아보도록 하죠.

 

 

 

위의 그림을 보면, 캐시는 CPU와 메인 메모리 사이에 위치해 있습니다. CPU는 필요한 변수를 메인 메모리에서 직접 가져오지 않고 캐시에 요청합니다. 처음으로 한 요청이므로 캐시에 arr[1] 값이 없습니다.

 

 

위의 그림을 보면, 캐시에 CPU가 요청한 변수가 없으므로 캐시는 메인 메모리에 arr[1] 값을 요청합니다. 그런데 이때 arr[1] 값만 가져오는 것이 아니라 주변 변수까지 한꺼번에 가져옵니다. 배열이므로 주변 요소들을 함께 가져오는 것이지요.

 

만약, CPU가 for 문을 수행하고 있었다면 분명 배열의 다음 요소를 요청할 것입니다. 이때 CPU는 다시 캐시에 arr[2]를 요청하게 되고, 캐시에는 이전 요청 때 arr[2]까지 모두 가져온 상태이므로 메인 메모리에 값을 요청하지 않고 바로 CPU에 전달합니다. CPU가 캐시에 요청했는데 요청한 데이터가 없다면 이를 캐시 미스(cache miss)라고 하고, 요청한 데이터가 있다면 캐시 히트(cache hit)라고 합니다.

 

캐시에서 CPU로 데이터를 전달하는 데 걸리는 시간은 3클럭입니다. 메인 메모리에서 가져오는 것보다 훨씬 빠르지요. 공간 지역성을 고려한다면 캐시 히트가 발생했을 때 성능은 월등하게 향상됩니다. 배열은 선형적으로 이어져 있기 때문에 cache hit가 발생하기 좋은 최적의 조건입니다. 

 

 

1.2  인덱싱 : 데이터에 빠르게 접근한다.

배열에서는 인덱싱(indexing)을 이용하여 데이터에 접근합니다. 알다시피 인덱스는 0부터 시작하지요. 배열의 요소가 메모리에 선형적으로 존재하기 때문에 인덱싱은 다음과 같은 간단한 수식의 연산만으로도 쉽게 데이터에 접근할 수 있습니다. 

 

데이터 주소 값 = 배열의 첫 주소 값 + (데이터 크기 * 인덱스)

 

수식은 한 번의 연산으로도 값에 접근할 수 있으므로 빅오는 O(1)입니다. 

 

 

1.3  동적 배열에서 데이터의 삽입과 삭제 1

데이터 삽입과 삭제는 두 가지 경우로 나누어서 생각할 수 있습니다. 데이터를 배열의 마지막에 추가하거나 삭제하는 경우와 배열의 중간에 추가하거나 삭제하는 경우입니다.

 

먼저 데이터를 배열의 마지막에 추가하거나 삭제하는 경우를 알아보겠습니다.

 

보통 배열이 확보한 메모리 공간을 capacity라고 하고, 채워진 데이터 크기를 size라고 합니다. size보다 capacity가 크다면, 즉 배열에 요소가 채워질 공간이 충분하다면 추가하려는 데이터를 배열의 마지막 요소 다음에 추가하면 됩니다. 따라서 빅오는 O(1)입니다. 

 

삭제할 때도 마찬가지입니다. 배열의 마지막 요소만 삭제하면 되는데, 삭제라고 하면 메모리를 0으로 초기화한다든가 하는 조치를 취해야 할 것 같지만 단순히 동적 배열에서 요소 개수를 나타내는 size란 변수를 1 줄이기만 해도 충분합니다. 역시 빅오는 O(1)입니다.

 

문제는 배열이 가득 차 있을 때입니다. 이때는 충분한 공간을 다시 확보하고 기존 배열 요소를 모두 복사한 후 새로운 데이터를 추가해야 합니다. 빅오가 데이터 개수만큼 복사해야 하므로 O(n)이 됩니다. 이때 유용하게 적용할 수 있는 개념이 분할 상환 분석(amortized analysis)입니다. 분할 상환 분석을 이용한 연산의 빅오는 O(1)입니다.

 

 

위의 그림을 보면 capacity가 충분히 커서 996번 동안은 빅오가 O(1)이고 그 후 배열이 가득 찼을 때 딱 한 번 빅오가 O(n)이 됩니다. 이를 이렇게 생각하면 어떨까요? 배열이 가득 찼을 때 추가하는 연산의 비싼 비용을 나머지 996번의 연산 동안 골고루 나누어 빚을 갚았다고 말이지요. 사실 동적 배열에서 배열이 가득 찼을 때는 배열 크기의 2배만큼 capacity를 다시 잡기 때문에 이후에 다시 배열이 가득 차려면 상당한 연산이 추가로 필요합니다. 그동안은 쭉 빅오가 O(1)인 셈입니다.

 

 

1.4  동적 배열에서 데이터의 삽입과 삭제 2

이번에는 배열의 중간에 데이터를 삽입하거나 삭제하는 연산을 알아보겠습니다.

 

새로운 요소를 배열의 맨 처음에 삽입해야 한다고 가정해 보겠습니다. 이때 동적 배열에서는 데이터를 맨 처음에 삽입하고자 이미 있는 요소들을 모두 한 번씩 뒤로 옮깁니다. 그 후 배열의 맨 처음에 새로운 요소를 삽입합니다. 데이터 개수가 n이라면 모두 n번 복사해야 하므로 O(n)입니다.

 

 

삭제도 이와 같습니다. 맨 앞의 6을 삭제하려면 뒤에 있는 1부터 5까지 모든 요소를 한 번씩 앞으로 옮겨야 합니다. 그래서 빅오는 O(n)입니다. 동적 배열의 삽입과 삭제라고 하면 최악의 경우를 고려해야 하므로 O(n)이라고 말합니다.

 

 

 

(출처 : 파이썬으로 배우는 자료구조 핵심 원리)