1. 배열이 인덱스 하나로 값을 바로 찾아내는 원리
배열(array)은 데이터를 메모리 위에 빈틈없이 나란히 늘어놓는 자료구조입니다. 컴퓨터 메모리를 아주 긴 서랍장이라고 생각하면, 배열은 서랍을 순서대로 쭉 채워서 쓰는 방식에 가깝습니다. 서랍 하나하나에는 번호가 붙어 있고, 이 번호를 흔히 주소라고 부릅니다.
배열에서 세 번째 칸에 있는 값을 꺼내고 싶다면, 시작 서랍 번호에 칸 하나의 크기를 곱해 더하기만 하면 바로 그 위치를 계산할 수 있습니다. 데이터가 열 개든 백만 개든 이 계산은 항상 한 번으로 끝나기 때문에, 인덱스로 값을 꺼내는 연산은 데이터 개수와 상관없이 걸리는 시간이 똑같습니다. 파이썬의 nums[3]처럼 대괄호에 숫자를 넣는 문법도 이 원리를 그대로 쓰고 있습니다.
2. 파이썬 리스트는 크기가 고정되지 않은 동적 배열입니다
원래 배열은 처음 만들 때 크기를 정해두고 그 이상은 넣을 수 없는 구조였습니다. 열 칸짜리 배열이라면 열한 번째 값을 넣을 자리가 아예 없습니다. 그런데 파이썬 리스트를 쓸 때는 이런 제약을 느낀 적이 거의 없을 겁니다. append를 몇 번을 부르든 계속 늘어납니다.
이렇게 크기가 필요할 때마다 알아서 늘어나는 배열을 동적 배열이라고 부릅니다. 파이썬 리스트 내부에는 지금 담긴 값의 개수 말고도 여유 공간이 조금 더 마련되어 있습니다. append로 값을 넣을 때 이 여유 공간이 남아 있으면 그냥 채워 넣기만 하면 되니 빠르게 끝나지만, 여유 공간이 다 차버리면 더 큰 새 저장 공간을 만들어 기존 값을 전부 옮겨 담는 작업이 뒤에서 조용히 일어납니다.
3. 용량이 늘어나는 순간을 코드로 확인해보기
말로만 들으면 잘 와닿지 않으니 파이썬 sys 모듈로 리스트가 실제로 차지하는 메모리 크기를 직접 찍어보겠습니다.
import sys
nums = []
prev_size = sys.getsizeof(nums)
for i in range(20):
nums.append(i)
size = sys.getsizeof(nums)
if size != prev_size:
print(len(nums), "개 넣었을 때 용량 변경", prev_size, "->", size)
prev_size = size
1 개 넣었을 때 용량 변경 56 -> 88
5 개 넣었을 때 용량 변경 88 -> 120
9 개 넣었을 때 용량 변경 120 -> 184
17 개 넣었을 때 용량 변경 184 -> 248
값을 하나씩 넣을 때마다 매번 크기가 바뀌는 게 아니라, 한동안 크기가 그대로 유지되다가 어느 순간 한꺼번에 늘어나는 걸 볼 수 있습니다. 여유 공간을 넉넉히 확보해두고 다 차면 한 번에 더 크게 재할당하는 동적 배열의 동작 방식입니다.
4. append가 분할상환 O(1)이라고 불리는 이유
재할당이 일어나는 순간에는 기존 값을 전부 새 공간으로 옮겨야 하니, 그 한 번의 append는 데이터 개수만큼 시간이 걸리는 O(n) 작업이 됩니다. 다만 이런 무거운 순간이 자주 오지는 않습니다. 앞서 확인한 것처럼 9개일 때 한 번 늘어난 다음에는 17개가 될 때까지 한참을 그대로 버팁니다.
append를 n번 반복했을 때 걸린 시간을 전부 더해서 n으로 나누면, 가끔 있는 O(n)짜리 재할당 비용이 수많은 O(1)짜리 append 사이에 넓게 퍼져서 평균적으로는 한 번에 O(1) 수준이 됩니다. 이렇게 여러 번 반복했을 때의 평균 비용으로 계산하는 방식을 분할상환(amortized) 비용이라고 부르고, append는 분할상환 O(1)이라고 표현하는 것이 정확합니다.
5. 어디에 넣느냐에 따라 완전히 달라지는 비용
append는 리스트 맨 뒤에 값을 붙이는 연산이라 여유 공간에 바로 채워 넣으면 그만입니다. 하지만 맨 앞이나 중간에 값을 끼워 넣으려면 이야기가 달라집니다. insert(0, x)처럼 맨 앞에 값을 넣으면, 기존에 있던 값들을 전부 한 칸씩 뒤로 밀어야 새로 들어온 값이 앉을 자리가 생깁니다.
nums = [1, 2, 3, 4, 5]
nums.insert(0, 0)
print(nums)
[0, 1, 2, 3, 4, 5]
결과만 보면 값 하나 추가한 것처럼 단순해 보이지만, 내부적으로는 다섯 개를 모두 한 칸씩 밀어낸 뒤에야 0을 앞에 놓을 수 있었습니다. 리스트 길이가 n이라면 최악의 경우 n개를 전부 밀어야 하니 맨 앞 삽입과 삭제는 O(n)이고, 중간에 넣거나 뺄 때도 마찬가지입니다.
6. 리스트 앞에서 계속 값을 빼는 코드가 위험한 이유
큐(queue)처럼 들어온 순서대로 값을 꺼내 쓰는 로직을 짜면서 리스트에 pop(0)이나 insert(0, x)를 반복문 안에서 계속 부르는 실수를 자주 하게 됩니다. 한 번은 O(n)이라 별일 아닌 것 같지만, 이걸 n번 반복하면 전체는 O(n^2)까지 느려집니다.
이런 상황을 위해 파이썬은 collections 모듈에 deque를 따로 제공합니다. deque는 양쪽 끝에서 넣고 빼는 연산을 전부 O(1)로 처리합니다. 이십만 개짜리 데이터로 직접 비교해보겠습니다.
import time
from collections import deque
lst = list(range(200000))
start = time.time()
for _ in range(3000):
lst.insert(0, 0)
print("리스트 insert(0, x) 3000회", time.time() - start)
dq = deque(range(200000))
start = time.time()
for _ in range(3000):
dq.appendleft(0)
print("deque appendleft 3000회", time.time() - start)
리스트 insert(0, x) 3000회 0.4809
deque appendleft 3000회 0.000334
같은 3000번인데 리스트 쪽은 시간이 눈에 보일 정도로 걸리고 deque 쪽은 거의 순간적으로 끝납니다. 앞이나 뒤에서 값을 자주 넣고 빼야 하는 상황이라면 리스트 대신 deque를 쓰는 것이 정석입니다.
7. 2차원 리스트를 만들 때 걸리는 흔한 함정
격자나 표 형태의 데이터를 다룰 때 흔히 [[0] * 3] * 3처럼 리스트를 곱해서 2차원 리스트를 만들곤 합니다. 겉보기에는 3행 3열짜리 표가 만들어진 것 같지만 눈에 잘 띄지 않는 함정이 숨어 있습니다.
grid = [[0] * 3] * 3
grid[0][0] = 9
print(grid)
[[9, 0, 0], [9, 0, 0], [9, 0, 0]]
분명 grid[0][0]만 바꿨는데 세 행이 전부 똑같이 바뀌어버렸습니다. [0] * 3으로 만든 리스트 하나를 세 번 복사한 것이 아니라, 같은 리스트를 가리키는 주소 세 개를 늘어놓은 것이기 때문입니다.
이 문제를 피하려면 리스트 컴프리헨션으로 매번 새 리스트를 따로 만들어야 합니다.
grid2 = [[0] * 3 for _ in range(3)]
grid2[0][0] = 9
print(grid2)
[[9, 0, 0], [0, 0, 0], [0, 0, 0]]
for _ in range(3)이 반복될 때마다 [0] * 3이 매번 새로 실행되어 서로 다른 리스트 세 개가 만들어지기 때문입니다.
8. 배열을 고를 때 기억해둘 것
지금까지 살펴본 연산들을 한데 모아보면, 배열은 인덱스로 값을 꺼내는 것과 맨 뒤에 값을 붙이는 것은 아주 빠르지만, 맨 앞이나 중간을 건드리는 순간 데이터 개수만큼 시간이 걸리는 자료구조입니다. 자주 하는 연산이 조회와 뒤쪽 추가라면 리스트만으로 충분하고, 앞쪽에서 넣고 빼는 일이 잦다면 deque로 바꾸는 것만으로 성능이 달라집니다.
코드를 짤 때 다루려는 데이터에 어떤 연산을 얼마나 자주 쓸지 떠올려보는 습관을 들이면, 데이터 양이 늘어났을 때 갑자기 느려지는 코드를 피하기가 한결 쉬워집니다.