[자료구조 04] 리스트 연산의 비용

리스트에 값을 넣고 빼는 방법은 여러 가지입니다. 그런데 겉보기엔 비슷한 이 동작들이 어디를 건드리느냐에 따라 속도가 크게 갈립니다. 핵심 규칙은 하나로 요약됩니다. 리스트는 끝을 건드리는 일은 빠르고, 앞이나 중간을 건드리는 일은 느립니다. 왜 그런 규칙이 생기는지, 자주 쓰는 메서드를 하나하나 예제로 확인하고 마지막에는 실제 시간까지 재 보겠습니다. 여기서 말하는 비용이란 그 동작이 데이터가 많아질 때 얼마나 버거워지는가를 뜻합니다. 리스트 하나만 놓고도 넣고 빼는 자리에 따라 이렇게 성격이 달라진다는 점이 흥미롭습니다.

04.1 append, 끝에 붙이기는 빠릅니다

리스트 끝에 값을 하나 붙여 보겠습니다.

lst = [1, 2, 3]

lst.append(4)

print(lst)

[1, 2, 3, 4]

append는 맨 뒤에 값을 더합니다. 뒤에 붙이는 것이라 이미 있는 원소들을 움직일 필요가 없습니다. 1, 2, 3은 그대로 두고 그 다음 빈자리에 4를 놓으면 끝입니다. 그래서 개수가 많아도 걸리는 시간이 거의 일정한 O(1)입니다. 리스트에 값을 쌓아 나갈 때 가장 즐겨 쓰는 방법입니다. 파이썬 리스트는 미리 여유 공간을 조금씩 확보해 두기 때문에, 대부분의 append는 빈자리에 값만 놓으면 끝납니다. 이런 이유로 평균 O(1)이라고 말합니다. 반복해서 값을 모을 때는 빈 리스트를 만들고 append로 하나씩 담는 방식이 기본형입니다.

04.2 insert(0, x), 맨 앞에 끼우기는 느립니다

이번엔 같은 방식으로 값을 맨 앞에 끼워 보겠습니다.

lst = [1, 2, 3, 4]

lst.insert(0, 99)

print(lst)

[99, 1, 2, 3, 4]

insert(0, 99)는 0번 자리에 99를 끼웁니다. 문제는 그 자리가 이미 차 있다는 것입니다. 99가 들어갈 공간을 만들려면 원래 있던 1, 2, 3, 4를 모두 한 칸씩 뒤로 밀어야 합니다. 원소가 많을수록 밀어내는 일도 그만큼 많아지므로 O(n)입니다. 똑같은 삽입인데 끝이 아니라 앞이라는 이유만으로 등급이 갈립니다. 값을 앞쪽에 자주 넣어야 하는 프로그램에서 무심코 insert(0)을 반복하면, 데이터가 늘수록 눈에 띄게 느려지니 주의해야 합니다. 화면 맨 위에 새 항목을 계속 추가하는 목록 같은 경우가 대표적으로 이 함정에 빠지기 쉽습니다. 반대로 뒤에서 넣고 빼기만 하면 리스트만큼 편하고 빠른 그릇도 없습니다.

04.3 pop(), 끝에서 빼기는 빠릅니다

이제 빼는 쪽을 보겠습니다. 끝 원소를 꺼내 보겠습니다.

lst = [99, 1, 2, 3, 4]

x = lst.pop()

print(x, lst)

4 [99, 1, 2, 3]

pop()은 괄호를 비워 두면 맨 끝 원소를 빼면서 그 값을 돌려줍니다. 꺼낸 4가 x에 담기고 리스트에서는 사라졌습니다. 끝을 빼면 나머지 원소들은 자리를 그대로 지키면 되므로, 아무것도 옮길 필요가 없습니다. 그래서 O(1)로 빠릅니다. pop()은 마지막에 넣은 것을 먼저 꺼내는 스택 구조를 만들 때 특히 요긴하게 쓰입니다. 괄호 안에 인덱스를 넣으면 특정 자리의 원소를 빼낼 수도 있습니다.

04.4 pop(0), 앞에서 빼기는 느립니다

반대로 맨 앞 원소를 빼 보겠습니다.

lst = [99, 1, 2, 3]

y = lst.pop(0)

print(y, lst)

99 [1, 2, 3]

pop(0)은 맨 앞 99를 빼는데, 그러면 0번 자리가 비어 버립니다. 이 빈자리를 메우려면 뒤의 값들을 전부 한 칸씩 앞으로 당겨야 합니다. 삽입과 마찬가지로 개수에 비례하는 O(n)입니다. 앞에서 자주 빼야 하는 상황이라면 리스트 대신, 앞뒤 모두 빠르게 넣고 빼는 deque(덱, 양방향 큐)라는 그릇을 씁니다. deque는 collections 모듈에 들어 있으며, 앞에서 빼는 일이 O(1)이라 줄 서기 같은 처리에 알맞습니다.

04.5 remove와 in, 값을 찾아야 하는 일

값 2를 찾아 지우고, 3이 들어 있는지 확인해 보겠습니다.

lst = [1, 2, 3]

lst.remove(2)

print(lst)

print(3 in lst)

[1, 3]

True

remove는 지울 값을, in은 있는지 물어볼 값을 앞에서부터 하나씩 찾아야 합니다. 그 값이 몇 번째에 있는지 미리 모르기 때문입니다. 그래서 둘 다 찾는 데 O(n)이 듭니다. 리스트에 이 값이 있나를 자주 물어야 하는 프로그램이라면, 앞 편에서 본 집합이나 딕셔너리에 담는 편이 훨씬 빠릅니다. 그쪽은 같은 물음을 평균 O(1)에 답하기 때문입니다. 리스트에서 in이 느린 이유 또한 앞에서부터 다 뒤지기 때문인데, 이는 첫 편에서 리스트와 집합의 속도를 비교하며 확인한 그 차이와 같습니다. 값의 위치를 미리 알고 있다면 인덱스로 지우는 편이 찾는 수고를 덜 수 있습니다.

04.6 끝과 앞의 속도 차이를 직접 재기

규칙을 숫자로 확인해 보겠습니다. 2만 개를 끝에 붙이는 방식과 앞에 끼우는 방식으로 각각 리스트를 만들어, 걸린 시간을 재 보겠습니다.

import timeit

def build_append(n):

a = []

for i in range(n):

a.append(i)

def build_insert0(n):

a = []

for i in range(n):

a.insert(0, i)

n = 20000

print(round(timeit.timeit(lambda: build_append(n), number=1), 4), "초 (append)")

print(round(timeit.timeit(lambda: build_insert0(n), number=1), 4), "초 (insert 0)")

0.0011 초 (append)

0.1299 초 (insert 0)

측정값은 컴퓨터에 따라 다르지만, 이번 실행에서는 앞에 끼우는 쪽이 약 100배 이상 느렸습니다. 똑같은 2만 개를 넣었는데 오직 넣는 자리 하나 때문에 이만한 차이가 난 것입니다. append는 매번 O(1)이라 전체가 가볍게 끝나지만, insert(0)은 매번 앞의 모든 원소를 밀어내느라 O(n)이 쌓여 이렇게 무거워집니다. O(1)과 O(n)이 실제로는 이렇게 벌어진다는 것을 눈으로 확인한 셈입니다. 이처럼 어느 쪽이 빠른지는 머리로 외우기보다, 직접 시간을 재 보면 훨씬 분명하게 와닿습니다. 앞에 끼우는 방식은 원소가 늘어날수록 한 번의 삽입도 점점 무거워져, 전체적으로는 훨씬 가파르게 느려집니다.

04.7 리스트 연산 비용 정리

끝을 다루는 append와 pop()은 O(1)로 빠릅니다. 앞이나 중간을 다루는 insert(0)과 pop(0)은 뒤 원소를 모두 밀거나 당겨야 해서 O(n)으로 느립니다. 값을 찾아야 하는 remove와 in도 앞에서부터 뒤지므로 O(n)입니다. 그래서 리스트는 끝에 쌓고 끝에서 빼는 용도에 가장 잘 맞습니다. 만약 앞에서 자주 넣고 빼야 하거나 어떤 값이 있는지를 자주 물어야 한다면, 그 일에 맞는 다른 그릇을 고르는 것이 훨씬 빠른 프로그램을 만드는 길입니다. 어떤 연산이 O(1)이고 어떤 것이 O(n)인지 감을 잡아 두면, 리스트를 훨씬 똑똑하게 쓸 수 있습니다. 자료구조를 고르는 눈은 이런 작은 비용 감각이 쌓여 만들어집니다.