배열과 동적 배열 - 늘어나는 리스트의 비밀

이 장에서 배우는 것

Python에서 리스트에 값을 하나씩 추가하면 길이가 늘어난다. 그러나 값을 담는 저장 공간이 매번 한 칸씩 늘어나는 것은 아니다. 미리 확보한 빈칸을 쓰다가 공간이 모자라면 더 큰 저장 공간을 마련하고 기존 값을 옮기는 방식으로 동작을 설명할 수 있다. 이 장에서는 그 방식을 직접 구현하고, 값을 몇 번 옮기는지 세어 본다.

《논리로 푸는 알고리즘》이 자료구조를 사용하는 쪽에 초점을 맞춘다면, 이 책은 자료구조를 만드는 쪽을 살핀다. 자료구조란 값을 보관하는 규칙과 값을 다루는 연산을 함께 정한 것이다. 같은 값을 저장하더라도 어떤 규칙을 선택하느냐에 따라 추가하거나 찾는 데 필요한 일이 달라진다.

• 고정 크기 배열에서 위치로 값을 읽는 방법과 길이·용량의 차이를 설명한다.
• 공간이 모자랄 때 용량을 두 배로 늘리는 동적 배열을 구현한다.
• 복사 횟수를 세어 연속된 추가 연산의 분할 상환 시간을 확인한다.
• 중간 삽입과 삭제에 필요한 이동 횟수를 계산한다.
• 직접 만든 배열과 내장 리스트의 결과를 비교하고, 측정할 수 있는 범위를 구분한다.

문제 상황

작업 도구에서 사용자가 입력한 기록 번호를 입력 순서대로 보관한다고 하자. 처음에는 번호가 몇 개 들어올지 모른다. 열 칸만 준비하면 열한 번째 입력을 처리할 방법이 필요하고, 처음부터 아주 많은 칸을 준비하면 쓰지 않는 공간이 생긴다. 최근 입력만 추가하는 동안에는 빠르게 동작하던 화면도 오래된 기록 사이에 새 번호를 끼워 넣을 때는 더 많은 일을 하게 된다.

구현 과제의 요구사항을 다음처럼 정한다. 정수 위치로 값을 읽고 바꿀 수 있어야 한다. 마지막에 값을 추가할 수 있어야 하며, 지정한 위치에 값을 삽입하거나 그 위치의 값을 삭제할 수 있어야 한다. 공간이 부족해도 사용자가 직접 저장 공간을 교체할 필요가 없어야 한다. 여기에 기존 값을 복사한 횟수와 삽입·삭제 때문에 값을 이동한 횟수를 출력하는 조건을 더한다.

내장 리스트를 저장소로 쓰기는 하지만, 그 리스트의 길이는 만든 뒤 바꾸지 않는다. [None] * capacity로 칸을 확보하고 정수 위치로 읽거나 쓰는 기능만 사용한다. 구현 내부에서는 내장 리스트의 append, insert, pop을 호출하지 않는다. 마지막 비교에서만 내장 리스트의 연산을 사용한다. 이렇게 사용 범위를 제한하면 공간 관리와 값 이동을 직접 책임질 수 있다.

고정 크기 배열과 길이·용량

배열(array)은 위치 번호로 각 칸을 구분하는 저장 방식이다. 전공 수업에서는 이 위치 번호를 인덱스(index)라고 부른다. 여기서는 첫 칸의 번호를 0으로 정한다. 길이가 n인 배열에 들어 있는 값의 위치는 0부터 n - 1까지다. 이 구현은 음수 위치를 허용하지 않는다.

고정 크기 배열은 생성할 때 칸 수를 정하고, 그 저장소 자체의 칸 수를 바꾸지 않는다. 전공 수업에서 배열의 빠른 위치 접근을 설명할 때는 시작 위치와 칸 간격으로 원하는 칸의 위치를 계산한다고 설명한다. 이 장에서는 그 계산을 직접 다루지 않고, Python 리스트의 정수 위치 접근을 한 번의 기본 연산으로 취급한다.

Python 리스트의 칸에는 객체 자체의 모든 내용이 들어가는 것이 아니라 객체를 가리키는 참조가 들어간다. 참조란 객체에 도달하기 위한 연결 정보다. 따라서 이 장에서 값 하나를 복사한다는 말은 객체 내부를 새로 만드는 것이 아니라 참조 하나를 다른 칸에 기록한다는 뜻이다.

동적 배열(dynamic array)은 고정 크기 저장소를 필요에 따라 교체하면서 길이를 바꿀 수 있게 만든 구조다. 이때 실제로 들어 있는 값의 개수인 길이와, 현재 저장소가 담을 수 있는 최대 개수인 용량을 따로 관리한다. 코드에서는 각각 size와 capacity다.

그림의 빈칸은 아직 값의 자리를 차지하지 않는다. 저장소에 None이 있다고 해서 빈칸이라고 판단하지도 않는다. 사용자가 실제 값으로 None을 넣을 수 있기 때문이다. 값이 있는 범위는 size로 판단한다. 실행 중 항상 지켜야 하는 조건을 전공 수업에서는 불변식(invariant)이라고 부른다. 여기서 핵심 조건은 0 ≤ size ≤ capacity이며, 실제 값은 0 이상 size 미만의 위치에 있다는 것이다.

길이와 용량은 서로 다른 질문에 답한다

항목	의미	예
길이	현재 저장한 값의 개수	3
용량	교체 없이 담을 수 있는 값의 개수	6
사용 중인 위치	읽기와 변경이 가능한 범위	0, 1, 2
다음 추가 위치	새 값을 기록할 칸	3

두 배 확장과 분할 상환 시간

마지막에 추가할 때 빈칸이 있으면 size 위치에 값을 쓰고 길이를 1 늘린다. 빈칸이 없으면 현재 용량의 두 배인 저장소를 만든다. 기존 값을 같은 순서로 복사한 다음 저장소를 교체하고 새 값을 쓴다. 용량이 0이면 두 배로 늘려도 0이므로, 이 구현은 처음부터 1 이상의 용량만 허용한다.

연산량을 비교할 때 입력 크기가 커짐에 따라 일이 얼마나 늘어나는지를 시간 복잡도라고 부른다. 전공 수업의 O 표기는 세부 상수보다 증가 형태를 나타내는 표기다. 값의 개수와 관계없이 일정한 횟수로 끝나면 O(1), 값의 개수 n에 비례해 일이 늘어나면 O(n)이라고 쓴다. 이 표기는 실행 시간을 초 단위로 약속하지 않는다.

빈칸이 있을 때 추가는 O(1)이지만, 확장을 동반하는 추가는 기존 n개를 복사하므로 O(n)이다. 그렇다고 추가를 m번 할 때마다 n개를 복사하지는 않는다. 초기 용량이 1이면 확장 때 복사하는 개수는 1, 2, 4, 8처럼 늘어난다. m이 2의 거듭제곱이고 정확히 m번 추가했다면, 총 복사 횟수는 1 + 2 + 4 + … + m / 2 = m - 1이다.

m이 2의 거듭제곱이 아니어도 총 복사 횟수는 2m보다 작다. 새 값 m개를 기록하는 일까지 합쳐도 전체 일은 m에 비례한다. 여러 연산을 묶어 총비용을 계산한 뒤 연산 하나당 비용을 설명하는 방법을 전공 수업에서는 분할 상환 분석(amortized analysis)이라고 부른다. 두 배 확장을 사용하는 마지막 추가의 분할 상환 시간은 O(1)이다.

이 결론은 입력을 무작위로 뽑아서 평균을 냈다는 뜻이 아니다. 같은 규칙으로 실행한 연속 추가 전체를 계산한 결과다. 어느 한 번의 추가가 오래 걸릴 수 있다는 사실도 그대로 남는다. 따라서 특정 요청 한 번의 지연이 중요한 상황에서는 전체 평균과 개별 연산의 비용을 구별해야 한다.

완성 코드에서는 저장 칸 읽기, 저장 칸 쓰기, 새 저장소의 칸 초기화를 각각 1회로 센다. 용량 c의 [None] * c는 초기화 c회다. 복사와 이동 횟수는 읽기·쓰기와 별도로 표시하는 설명용 수치이며, 총비용에 다시 더하지 않는다. 반복 조건 검사, 정수 계산, 출력은 세지 않는다. 이처럼 무엇을 한 번으로 셀지 정하는 약속을 비용 모형이라고 한다.

초기 용량 1에서 연속 추가의 총비용은 추가 개수에 비례한다

추가 개수 m	기존 값 복사	칸 초기화	총비용
4	3	7	17
8	7	15	37
16	15	31	77

표의 총비용에는 최초 저장소 초기화도 들어 있다. m이 2의 거듭제곱이면 초기화는 2m - 1회, 읽기는 m - 1회, 쓰기는 2m - 1회이므로 합계는 5m - 3이다. 빈칸을 만드는 비용까지 포함해도 m에 비례한다. 확장 중에는 이전 저장소와 새 저장소가 함께 필요하므로 잠시 필요한 저장 공간도 늘어난다.

중간 삽입은 왜 값을 밀어야 하는가

위치 i에 새 값을 넣으려면 그 위치부터 끝까지 있던 값이 한 칸씩 오른쪽으로 이동해야 한다. 이동 개수는 n - i다. 여기서 n은 삽입 전 길이다. 뒤에서부터 이동해야 아직 읽지 않은 값을 덮어쓰지 않는다. 맨 끝에 넣으면 이동은 0회지만, 맨 앞에 넣으면 기존 값 전부를 이동한다.

삭제는 반대 방향이다. 위치 i의 값을 꺼낸 뒤 오른쪽 값들을 왼쪽으로 당긴다. 삭제 전 길이가 n이면 이동 횟수는 n - i - 1이다. 마지막 칸은 None으로 지워 더 이상 필요하지 않은 참조를 남기지 않는다. 이 구현은 삭제해도 용량을 줄이지 않는다.

확장이 없는 삽입의 총비용은 이동마다 읽기와 쓰기가 한 번씩 필요하고 새 값도 한 번 쓰므로 2(n - i) + 1이다. 삭제는 반환할 값을 한 번 읽고, 이동마다 두 번 접근하고, 마지막 칸을 한 번 지우므로 2(n - i - 1) + 2다. 완성 코드에서는 길이 8인 배열의 앞·중간·끝에서 이 식을 확인한다.

저장 공간에 여유가 있다는 사실은 중간 삽입의 이동을 없애 주지 않는다. 또한 꽉 찬 배열에 중간 삽입을 하면 확장을 위한 복사와 삽입을 위한 이동이 모두 발생한다. 두 일을 구분해서 세어야 느려진 이유를 설명할 수 있다.

완성 코드

다음 내용을 main.py로 저장한다. 외부 패키지나 입력은 필요하지 않다. 오류 검사에는 잘못된 인자를 알리는 ValueError와 범위를 벗어난 위치를 알리는 IndexError를 사용한다. 이들은 실행 중 문제를 전달하는 예외다.

class DynamicArray:
    def __init__(self, capacity=1):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.size = 0
        self._data = [None] * capacity
        self.reads = 0
        self.writes = 0
        self.initialized = capacity
        self.copies = 0
        self.shifts = 0

    def reset_counts(self):
        self.reads = 0
        self.writes = 0
        self.initialized = 0
        self.copies = 0
        self.shifts = 0

    def _read(self, index):
        self.reads += 1
        return self._data[index]

    def _write(self, index, value):
        self.writes += 1
        self._data[index] = value

    def _check(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("index out of range")

    def get(self, index):
        self._check(index)
        return self._read(index)

    def set(self, index, value):
        self._check(index)
        self._write(index, value)

    def _grow(self):
        new_capacity = self.capacity * 2
        new_data = [None] * new_capacity
        self.initialized += new_capacity
        for index in range(self.size):
            value = self._read(index)
            new_data[index] = value
            self.writes += 1
            self.copies += 1
        self._data = new_data
        self.capacity = new_capacity

    def append(self, value):
        if self.size == self.capacity:
            self._grow()
        self._write(self.size, value)
        self.size += 1

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("index out of range")
        if self.size == self.capacity:
            self._grow()
        for position in range(self.size, index, -1):
            self._write(position, self._read(position - 1))
            self.shifts += 1
        self._write(index, value)
        self.size += 1

    def pop(self, index):
        self._check(index)
        value = self._read(index)
        for position in range(index, self.size - 1):
            self._write(position, self._read(position + 1))
            self.shifts += 1
        self._write(self.size - 1, None)
        self.size -= 1
        return value

    def work(self):
        return self.reads + self.writes + self.initialized

    def counts(self):
        return (
            f"copy={self.copies} shift={self.shifts} "
            f"read={self.reads} write={self.writes} "
            f"init={self.initialized} work={self.work()}"
        )

    def to_text(self):
        text = "["
        for index in range(self.size):
            if index != 0:
                text += ", "
            text += str(self._data[index])
        return text + "]"


def filled(size, capacity):
    array = DynamicArray(capacity)
    for value in range(size):
        array.append(value)
    array.reset_counts()
    return array


def append_experiment():
    for size in (4, 8, 16):
        array = DynamicArray()
        deltas = ""
        for value in range(size):
            before = array.copies
            array.append(value)
            if value != 0:
                deltas += " "
            deltas += str(array.copies - before)
        print(f"append {size}: {array.counts()}")
        if size == 16:
            print(f"copies per append: {deltas}")


def operation_experiment():
    array = filled(8, 16)
    value = array.get(4)
    print(f"get 4 = {value}: {array.counts()}")
    array.reset_counts()
    array.set(4, 99)
    print(f"set 4: {array.counts()}")

    for index in (0, 4, 8):
        array = filled(8, 16)
        array.insert(index, 99)
        print(f"insert {index}: {array.counts()}")

    for index in (0, 4, 7):
        array = filled(8, 16)
        value = array.pop(index)
        print(f"pop {index} = {value}: {array.counts()}")

    array = filled(8, 8)
    array.append(99)
    print(f"full append: {array.counts()}")


def comparison():
    custom = DynamicArray()
    for value in (10, 20, 30, 40):
        custom.append(value)
    custom.insert(2, 25)
    custom_removed = custom.pop(1)

    builtin = []
    for value in (10, 20, 30, 40):
        builtin.append(value)
    builtin.insert(2, 25)
    builtin_removed = builtin.pop(1)

    same = custom.size == len(builtin)
    for index in range(custom.size):
        if custom.get(index) != builtin[index]:
            same = False
    same = same and custom_removed == builtin_removed

    print(f"custom: {custom.to_text()}, removed={custom_removed}")
    print(f"builtin: {builtin}, removed={builtin_removed}")
    print(f"same: {same}")
    print(f"custom moves: copy={custom.copies} shift={custom.shifts}")
    print("builtin logical shifts: 5; internal copies: not measured")


def main():
    append_experiment()
    operation_experiment()
    comparison()


if __name__ == "__main__":
    main()

줄별 해설

class DynamicArray:는 저장 상태와 연산을 한 객체로 묶는다. 생성자의 첫 조건문은 양수 용량만 받아들이고, self._data = [None] * capacity는 고정 길이 저장소를 만든다. 이어지는 다섯 대입문은 비용 계수기를 준비한다. 최초 저장소를 만드는 일도 비용이므로 initialized는 0이 아니라 최초 용량에서 시작한다.

reset_counts의 대입문들은 배열의 값을 바꾸지 않고 측정 구간만 새로 시작한다. 실험 준비에 사용한 추가 비용과 실험 대상 연산의 비용을 분리하기 위한 메서드다. 메서드란 클래스 안에 정의되어 객체의 상태를 사용하는 함수다. 이름 앞의 밑줄은 내부 구현용이라는 관례이며 호출을 강제로 막지는 않는다.

_read는 계수기를 늘린 뒤 한 칸을 반환한다. _write도 같은 방식으로 한 칸을 기록한다. _check는 실제 값이 있는 범위만 허용한다. 따라서 용량이 16이어도 길이가 8이면 get(8)은 실패한다. get과 set은 범위를 확인한 뒤 각각 읽기 한 번, 쓰기 한 번으로 끝난다.

_grow의 첫 세 줄은 두 배 용량의 저장소를 만들고 초기화 비용을 더한다. 반복문의 range(self.size)는 실제 값만 순서대로 방문한다. 아직 새 저장소로 교체하지 않았으므로 읽기는 _read로 하고, 쓰기는 new_data[index]에 직접 수행한다. 이 직접 쓰기도 계수기에 반드시 더한다. 마지막 두 대입은 복사가 끝난 저장소를 현재 저장소로 채택한다.

append는 공간이 꽉 찼을 때만 확장한다. 그다음 기존 길이를 위치로 삼아 새 값을 쓰고 길이를 늘린다. 길이 증가는 쓰기 뒤에 일어나므로, 새 값이 들어가기 전에는 그 위치를 실제 값으로 취급하지 않는다.

insert는 읽기와 다른 범위 검사를 쓴다. 길이와 같은 위치는 끝에 삽입한다는 뜻이므로 허용한다. range(self.size, index, -1)은 마지막 빈칸부터 삽입 위치 바로 오른쪽까지 거꾸로 방문한다. 각 반복에서 왼쪽 값을 읽어 오른쪽에 쓰고 이동 횟수를 1 늘린다. 자리가 생긴 뒤 새 값을 쓰고 길이를 늘린다.

pop은 삭제할 값을 먼저 보관한다. 반복문의 오른쪽 경계는 포함되지 않으므로 마지막 반복에서 마지막 값을 바로 왼쪽으로 옮긴다. 이어서 이전 마지막 칸을 지우고 길이를 줄인다. 마지막 위치를 삭제하면 반복문은 실행되지 않지만, 반환할 값 읽기와 칸 지우기는 여전히 필요하다.

work는 기본 비용 세 가지의 합을 구한다. counts는 그 수치를 문자열에 넣는다. 문자열 앞의 f는 중괄호 안의 값을 문자열에 채우는 Python 문법이다. to_text는 출력 확인용이며 직접 저장소를 읽어서 계수기를 바꾸지 않는다. 문자열을 만드는 비용은 자료구조 연산의 측정에서 제외한다.

filled는 같은 조건의 배열을 반복해서 준비한다. 각 실험은 준비가 끝난 뒤 계수기를 초기화하므로 서로 영향을 주지 않는다. append_experiment는 추가 직전과 직후의 복사 횟수 차이를 기록한다. operation_experiment는 여유 공간이 있는 삽입·삭제와 꽉 찬 상태의 추가를 따로 측정한다.

comparison은 두 구현에 같은 값을 넣고 같은 삽입·삭제를 실행한다. 결과의 길이, 각 값, 삭제 반환값을 비교한다. 비교 과정의 get은 읽기 계수기를 늘리지만, 마지막 출력에서는 복사와 이동만 사용하므로 이 확인 작업이 출력된 이동 횟수에 영향을 주지 않는다. 마지막 조건문은 파일을 직접 실행했을 때 main을 호출한다.

실행 결과

macOS와 Linux에서 Python 3.12 이상으로 실행한다. 난수를 사용하지 않으므로 실행할 때마다 같은 결과가 나온다.

python3 main.py

append 4: copy=3 shift=0 read=3 write=7 init=7 work=17
append 8: copy=7 shift=0 read=7 write=15 init=15 work=37
append 16: copy=15 shift=0 read=15 write=31 init=31 work=77
copies per append: 0 1 2 0 4 0 0 0 8 0 0 0 0 0 0 0
get 4 = 4: copy=0 shift=0 read=1 write=0 init=0 work=1
set 4: copy=0 shift=0 read=0 write=1 init=0 work=1
insert 0: copy=0 shift=8 read=8 write=9 init=0 work=17
insert 4: copy=0 shift=4 read=4 write=5 init=0 work=9
insert 8: copy=0 shift=0 read=0 write=1 init=0 work=1
pop 0 = 0: copy=0 shift=7 read=8 write=8 init=0 work=16
pop 4 = 4: copy=0 shift=3 read=4 write=4 init=0 work=8
pop 7 = 7: copy=0 shift=0 read=1 write=1 init=0 work=2
full append: copy=8 shift=0 read=8 write=9 init=16 work=33
custom: [10, 25, 30, 40], removed=20
builtin: [10, 25, 30, 40], removed=20
same: True
custom moves: copy=7 shift=5
builtin logical shifts: 5; internal copies: not measured

추가별 복사 횟수에는 1, 2, 4, 8이 드문드문 나타난다. 이 간격이 늘어나기 때문에 총비용이 추가 횟수에 비례한다. 반면 길이 8에서 앞에 삽입하면 8개를 이동한다. 마지막에 삽입할 때의 이동 0회와 구별되는 지점이다.

마지막 비교에서 직접 구현한 배열의 복사 7회는 용량 1에서 2로, 2에서 4로, 4에서 8로 확장하며 발생한 1 + 2 + 4회다. 이동 5회는 삽입에서 2회, 삭제에서 3회다. 내장 리스트에도 같은 순서를 유지하려면 논리적으로 이 5개 값의 위치가 바뀌어야 한다.

그러나 이 프로그램은 내장 리스트 내부의 실제 복사 횟수를 측정하지 않는다. 내장 구현이 이 코드와 같은 확장 비율을 쓴다고 가정해서도 안 된다. 따라서 비교 결과는 값과 반환값의 일치, 그리고 순서 유지를 위해 위치가 달라지는 값의 개수까지다. 메모리 관리 방식이나 내부 명령 수까지 같다는 결론은 내릴 수 없다.

실무에서 자주 틀리는 것

용량을 유효한 값의 개수로 사용한다

다음 검사는 실제 값이 없는 빈칸까지 읽게 한다. 유효한 읽기 범위는 용량이 아니라 길이로 정한다.

# 틀린 코드
if index < 0 or index >= self.capacity:
    raise IndexError("index out of range")

# 고친 코드
if index < 0 or index >= self.size:
    raise IndexError("index out of range")

filled(3, 8).get(3)으로 확인할 수 있다. 고친 구현은 예외를 발생시킨다. 삽입은 끝 위치를 허용하므로 별도의 조건이 필요하다는 점도 함께 확인한다.

삽입할 때 앞에서부터 이동한다

앞에서부터 오른쪽으로 복사하면 다음에 읽어야 할 값을 먼저 덮어쓴다. 예를 들어 10, 20, 30의 위치 1에 삽입하려다가 20을 뒤에 쓰면, 원래 30을 읽기 전에 그 칸이 바뀐다.

# 틀린 코드
for position in range(index, self.size):
    self._write(position + 1, self._read(position))

# 고친 코드
for position in range(self.size, index, -1):
    self._write(position, self._read(position - 1))

완성 코드의 comparison에 있는 중간 삽입이 순서를 확인한다. 확인용 값이 모두 같으면 덮어쓰기 오류를 발견하기 어려우므로 서로 다른 값을 사용한다.

확장할 때 한 칸만 더 확보한다

용량을 한 칸씩 늘리면 꽉 찬 뒤의 추가마다 기존 값을 복사한다. 초기 용량 1에서 m개까지 넣을 때 복사는 1 + 2 + … + (m - 1) = m(m - 1) / 2회가 된다. 전체 비용은 O(m²)다.

# 틀린 코드
new_capacity = self.capacity + 1

# 고친 코드
new_capacity = self.capacity * 2

완성 코드의 해당 줄을 한 칸 증가 방식으로 바꾸어 실행하면 16개 추가의 복사 횟수가 15에서 120으로 늘어난다. 매번 마지막에 추가했어도 확장 규칙 때문에 전체 비용이 달라진다.

계수기를 중복 합산한다

복사 한 번은 이미 읽기 한 번과 쓰기 한 번에 반영되어 있다. 복사와 이동을 다시 합치면 같은 일을 두 번 센다. 실행 시간과 계수기의 숫자를 직접 같은 단위로 취급하는 것도 피해야 한다.

# 틀린 코드
return (
    self.reads + self.writes + self.initialized
    + self.copies + self.shifts
)

# 고친 코드
return self.reads + self.writes + self.initialized

복사와 이동은 비용의 원인을 설명하는 보조 수치다. 총비용은 합의한 기본 연산으로만 계산한다. 또한 실험 준비가 끝난 뒤 reset_counts를 호출해야 측정 대상 한 번의 비용을 해석할 수 있다.

한눈에 보기

직접 구현한 동적 배열의 연산 비용

연산	주요 작업	시간 복잡도	실행 확인
위치 읽기·변경	한 칸 접근	O(1)	각각 비용 1
여유가 있는 끝 추가	새 값 기록	O(1)	끝 삽입 비용 1
확장하는 끝 추가	저장소 생성과 n개 복사	O(n)	8개 복사, 비용 33
연속 끝 추가	가끔 두 배 확장	분할 상환 O(1)	16회 총비용 77
위치 i 삽입	n - i개 오른쪽 이동	최악 O(n)	앞 삽입 이동 8회
위치 i 삭제	n - i - 1개 왼쪽 이동	최악 O(n)	앞 삭제 이동 7회
끝 삭제	값 읽기와 칸 지우기	O(1)	비용 2

이 구현의 저장 공간은 용량에 비례한다. 초기 용량 1에서 추가만 했다면 값이 하나 이상일 때 용량은 길이의 두 배보다 작다. 하지만 삭제 후에도 용량을 유지하므로, 삭제가 이어진 상태에는 이 관계를 적용할 수 없다. 다음 장에서는 값을 연속된 칸에 모으는 방식에서 벗어나, 각 값의 연결 관계로 순서를 유지하는 방법을 다룬다.

연습 문제

1. 초기 용량 1에서 값을 9개 추가하면 최종 용량과 복사·읽기·쓰기·초기화·총비용은 각각 얼마인가. 완성 코드로 확인하라.
2. 길이 6, 용량 8인 배열의 위치 2에 삽입할 때 이동과 총비용을 계산하라. 같은 초기 상태에서 위치 2를 삭제하는 경우도 구하라.
3. 유효한 위치에 대한 읽기·변경, 잘못된 읽기, 끝 삽입을 한 함수에서 검사하라. None도 값으로 저장할 수 있는지 확인하라.
4. 초기 용량을 3으로 바꾸고 10개를 추가하라. 최종 용량과 복사 횟수를 계산하고, 처음부터 용량이 2의 거듭제곱이어야 하는지 설명하라.

정답과 해설

1. 아홉 번째 추가는 확장을 일으킨다

최종 용량은 16이다. 복사는 1 + 2 + 4 + 8 = 15회이고 읽기도 15회다. 쓰기는 새 값 9개와 복사 15회를 합친 24회다. 초기화는 1 + 2 + 4 + 8 + 16 = 31회이므로 총비용은 70이다.

def answer_one():
    array = DynamicArray()
    for value in range(9):
        array.append(value)
    print(array.capacity, array.counts())

# 출력
# 16 copy=15 shift=0 read=15 write=24 init=31 work=70

추가 횟수가 2의 거듭제곱이 아니므로 앞에서 구한 5m - 3을 그대로 대입할 수 없다. 확장이 언제 발생했는지부터 확인해야 한다.

2. 삽입과 삭제의 이동 개수는 하나 차이 난다

삽입은 6 - 2 = 4개를 이동한다. 읽기 4회와 쓰기 5회로 비용은 9다. 삭제는 6 - 2 - 1 = 3개를 이동한다. 반환할 값 읽기를 포함해 읽기 4회, 마지막 칸 지우기를 포함해 쓰기 4회이므로 비용은 8이다.

def answer_two():
    array = filled(6, 8)
    array.insert(2, 99)
    print(array.counts())
    array = filled(6, 8)
    array.pop(2)
    print(array.counts())

# 출력
# copy=0 shift=4 read=4 write=5 init=0 work=9
# copy=0 shift=3 read=4 write=4 init=0 work=8

3. 빈칸 여부는 값이 아니라 길이로 판단한다

assert는 조건이 참인지 확인하고, 거짓이면 검사를 중단시키는 문장이다. 다음 함수는 정상 동작을 확인하고 예상한 예외가 발생했는지도 검사한다. try는 예외가 발생할 수 있는 코드를 실행하고, except는 지정한 예외를 처리한다.

def answer_three():
    array = DynamicArray(4)
    array.append(None)
    assert array.size == 1
    assert array.get(0) is None
    array.set(0, 7)
    assert array.get(0) == 7

    for index in (-1, 1):
        try:
            array.get(index)
        except IndexError:
            pass
        else:
            raise AssertionError("expected IndexError")

    array.insert(array.size, 9)
    assert array.to_text() == "[7, 9]"
    print("checks passed")

# 출력
# checks passed

길이 1에서 위치 1의 읽기는 실패하지만 같은 위치의 삽입은 가능하다. 저장소의 빈칸에 남아 있는 값이 무엇인지는 이 규칙에 영향을 주지 않는다.

4. 두 배 증가에는 특정한 시작 용량이 필요하지 않다

용량은 3, 6, 12로 바뀐다. 10개를 담은 최종 용량은 12이며 복사는 3 + 6 = 9회다. 두 배로 증가하는 규칙이 중요하며 최초 용량이 2의 거듭제곱일 필요는 없다.

def answer_four():
    array = DynamicArray(3)
    for value in range(10):
        array.append(value)
    print(array.capacity, array.copies)

# 출력
# 12 9

각 정답 함수는 완성 코드의 main 정의 앞에 붙이고 main에서 호출하면 실행할 수 있다. 실험 조건을 바꿀 때는 초기 용량, 초기 길이, 계수기 초기화 시점을 함께 기록해야 계산과 출력이 같은 상황을 설명하게 된다.