시간과 공간 맞바꿈

시간과 공간 맞바꿈은 메모리를 더 내주고 계산 시간을 줄이는 선택입니다. 한 번 구한 답을 저장해 두고 다음에는 다시 구하지 않습니다. 거꾸로 시간을 더 들여 메모리를 아끼는 선택도 있습니다. 둘 중 무엇을 고를지는 메모리의 여유와 같은 계산이 되풀이되는 정도가 정합니다.

상세

구구단을 외운 사람은 칠 곱하기 팔을 물으면 바로 오십육이라고 답합니다. 외우지 않은 사람은 칠을 여덟 번 더해서 답을 냅니다. 외운 사람은 답을 바로 내는 대신 머릿속에 표 하나를 넣어 두었습니다.

프로그램에서 답을 저장해 두는 쪽은 계산이 줄고 메모리가 늡니다. 답을 다시 계산하는 쪽은 메모리가 줄고 계산이 늡니다. 이 문서는 이 두 쪽을 양 끝이라고 부릅니다. 양 끝 사이에서 고르는 일이 시간과 공간 맞바꿈입니다.

이 절은 먼저 두 자원을 재는 잣대를 세웁니다. 그다음 사용자를 찾는 짧은 코드로 양 끝을 견줍니다. 끝을 고르는 조건은 마지막에 표로 모읍니다.

이 맞바꿈을 모르면 한쪽 자원만 보고 고르게 됩니다. 응답을 줄이려고 저장본을 늘리다 메모리가 바닥나기도 합니다. 메모리를 아끼려다 같은 조회를 요청마다 되풀이하기도 합니다.

두 자원을 재는 잣대

시간은 코드가 일을 끝내기까지 하는 연산의 수로 잽니다. 입력이 커질 때 이 수가 어떤 꼴로 늘어나는지를 시간 복잡도라고 부릅니다. 초 단위로 재지 않는 까닭은 같은 코드도 기계마다 걸리는 초가 다르기 때문입니다.

그래도 이 문서의 시간은 두 가지를 함께 가리킵니다. 꼴을 견줄 때는 연산의 수입니다. 캐시나 디스크를 말할 때는 사용자가 응답을 기다리는 실제 시간입니다. 디스크를 한 번 읽는 일은 연산 하나로 세지만 메모리를 읽을 때보다 훨씬 오래 걸립니다.

공간은 코드가 값을 담아 두려고 쓰는 메모리입니다. 이 문서에서는 공간을 메모리라고 부릅니다. 입력이 커질 때 메모리가 어떤 꼴로 늘어나는지를 공간 복잡도라고 부릅니다.

두 꼴은 빅오 표기법으로 줄여 적습니다. 입력 크기를 n 이라 둡니다. 연산이 n 에 비례해 늘면 O(n) 이라고 적습니다. 입력과 상관없이 일정하면 O(1) 이라고 적습니다.

맞바꿈을 따질 때는 이 두 꼴을 나란히 놓습니다. 어떤 방법이 시간 꼴을 줄였다고 해 봅시다. 그 대신 메모리 꼴이 늘었다면 그 방법은 맞바꿈을 한 것입니다.

사용자를 찾는 두 방법

사용자 목록에서 번호로 이름을 찾는 일을 생각해 봅시다. 아래 코드는 같은 일을 두 방법으로 합니다. find 는 목록을 훑습니다. by_id 는 찾기 전에 딕셔너리를 하나 만들어 둡니다. 딕셔너리는 키를 주면 짝지은 값을 바로 꺼내 주는 모음입니다.

users = [
    {"id": 7, "name": "kim"},
    {"id": 3, "name": "lee"},
    {"id": 9, "name": "park"},
]

def find(uid):
    for u in users:
        if u["id"] == uid:
            return u["name"]

by_id = {u["id"]: u["name"] for u in users}

find(9)     # 'park'
by_id[9]    # 'park'

find 는 찾을 때마다 목록을 앞에서부터 훑습니다. 사용자가 n 명이면 한 번 찾는 데 최대 n 번 견줍니다. 더 쓰는 메모리는 반복 변수 하나뿐입니다.

by_id 는 번호와 이름의 짝을 미리 모두 담아 둡니다. 그래서 한 번 찾는 데 평균 O(1) 이면 됩니다. 대개는 한 번에 꺼내지만 드물게 더 걸릴 때가 있어 평균이라고 적습니다.

대신 n 명 몫의 짝을 담을 메모리가 더 듭니다. 딕셔너리를 만들 때 목록을 한 번 훑는 시간도 듭니다.

찾기를 k 번 되풀이하면 차이가 드러납니다. 두 방법이 k 번 찾는 동안 드는 시간과 더 쓰는 메모리를 나란히 놓으면 이렇습니다.

찾기가 한 번뿐이면 딕셔너리를 만드는 데 목록을 한 번 훑으므로 얻는 것이 없습니다. 찾기가 되풀이될수록 목록 훑기의 시간은 k 에 n 을 곱한 만큼 불어납니다. 딕셔너리 쪽은 처음 만든 값을 계속 나눠 씁니다.

한쪽 끝 — 저장해 두기

저장해 두기는 앞으로 다시 쓸 것을 미리 담아 둡니다. 담는 것은 크게 둘입니다. 한 번 계산한 답과, 원하는 값이 어디 있는지 알려 주는 위치입니다.

이 끝을 고르는 기법은 백엔드에 많습니다. 아래 표는 기법마다 담아 두는 것과 그 덕에 줄어드는 일을 짝지었습니다.

상품 목록 화면을 담아 두는 응답 캐시가 캐싱의 흔한 예입니다. 요청마다 데이터베이스에서 상품을 모아 화면을 만드는 대신 한 번 만든 결과를 메모리에 담아 둡니다. 다음 요청은 담아 둔 결과를 받습니다.

이 끝이 내주는 것은 메모리만이 아닙니다. 원본이 바뀌면 저장해 둔 답은 틀린 답이 됩니다. 그래서 원본이 바뀔 때 저장본을 지우거나 고치는 일이 따라붙습니다. 이 일을 캐시 무효화라고 부릅니다.

원본과 함께 고쳐야 하는 저장본은 쓰기마다 일을 늘립니다. 인덱스가 그렇습니다. 행을 하나 넣을 때마다 인덱스에도 그 값을 넣어야 합니다. 읽기에서 줄인 시간을 쓰기에서 일부 갚는 셈입니다.

저장본이 메모리에 다 들어가지 않으면 이 끝은 제 몫을 못 합니다. 메모리가 모자라면 운영체제가 메모리 내용을 디스크로 내보내는 스와핑을 시작합니다. 연산 수는 늘지 않아도 디스크를 오가는 동안 실제 응답 시간은 오히려 늘어납니다.

다른 끝 — 다시 계산하기

다시 계산하기는 필요할 때마다 원본에서 답을 새로 만듭니다. 담아 두는 것이 없으니 메모리가 적게 듭니다. 저장본이 없으니 낡을 일도 없습니다. 대신 같은 계산을 쓸 때마다 되풀이합니다.

이 끝을 고르는 기법도 여럿입니다. 기법마다 아끼는 메모리와 그 대신 더 드는 일을 짝지으면 다음과 같습니다.

스트리밍은 데이터를 한꺼번에 메모리에 올리지 않고 조금씩 받아 처리하는 방식입니다. 로그 파일의 줄 수를 셀 때 한 줄을 읽으면 바로 버립니다. 그러면 파일이 커져도 쓰는 메모리가 거의 늘지 않습니다. 대신 같은 파일을 두 번 훑어야 하는 일이면 파일을 처음부터 다시 읽습니다.

외부 정렬은 메모리보다 큰 데이터를 정렬하는 방법입니다. 데이터를 메모리에 들어갈 만한 조각으로 나눠 조각마다 정렬합니다. 정렬한 조각은 디스크에 써 둡니다. 마지막에 그 조각들을 다시 읽어 하나로 합칩니다.

양 끝이 얻는 것과 내주는 것

두 끝은 서로 반대편을 내주고 얻습니다. 앞의 두 소절을 짝으로 모으면 이렇습니다.

끝을 고르는 조건

한쪽 끝이 늘 맞지는 않습니다. 어느 끝이 맞는지는 데이터와 요청의 생김새가 정합니다. 조건마다 고르는 끝과 그 까닭을 적으면 다음과 같습니다.

조건 둘이 서로 다른 끝을 가리킬 때도 있습니다. 자주 읽히는 데이터의 원본이 자주 바뀔 때가 그렇습니다. 그럴 때는 두 끝 사이의 한 점을 고릅니다.

두 끝 사이의 중간 지점

모든 답을 담는 대신 일부만 담는 방법은 두 끝 사이에 놓입니다. 대표적인 방법은 담아 둘 양에 한도를 두는 것입니다. 한도가 차면 담아 둔 것 가운데 하나를 버립니다. 이 일을 축출이라고 부릅니다.

버릴 것을 고르는 규칙으로는 LRU(Least Recently Used, 가장 오래 쓰이지 않은 것을 먼저 버리기)가 널리 쓰입니다. 이 규칙을 쓰면 자주 꺼내는 답이 남기 쉽습니다. 메모리 한도 안에서 되풀이되는 계산을 줄입니다.

다른 방법은 저장한 답에 유효 시간인 TTL(Time To Live)을 붙이는 것입니다. 시간이 지나면 저장본을 버립니다. 다음 요청이 오면 답을 다시 계산합니다. 원본이 바뀌어도 낡은 답이 남는 시간이 TTL 안으로 줄어듭니다.

맞바꿈이 생기지 않는 경우

두 자원을 함께 줄이는 방법이 있으면 고를 것이 없습니다. 그때는 맞바꿈이 생기지 않습니다.

정렬된 목록에서 값을 찾는 일이 예입니다. 앞에서부터 훑으면 시간이 O(n) 입니다. 가운데 값과 견줘 찾을 범위를 절반씩 줄이는 이진 탐색을 쓰면 시간이 O(log n) 으로 줄어듭니다.

log n 은 n 을 절반씩 몇 번 줄여야 1 이 되는지를 나타내는 수입니다. n 이 백만이어도 스무 번쯤이면 1 이 됩니다.

두 방법 모두 범위를 가리키는 변수 몇 개만 더 쓰므로 메모리는 O(1) 로 같습니다.

그래서 맞바꿈은 같은 일을 하는 방법 가운데 어느 것도 두 자원을 함께 줄이지 못할 때 따집니다. 한 방법이 시간과 메모리 둘 다 적게 쓰면 그 방법을 고르면 됩니다.

관련 항목

두 끝을 재는 잣대

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 보조 공간 · 분할 상환 비용 · 점근 분석

메모리를 내주고 시간을 줄이는 기법

메모이제이션 · 캐싱 · 인덱스 · 조회 테이블 · 비정규화 · 해시테이블 · 딕셔너리 · 구체화 뷰 · 동적 계획법 · 미리 계산

시간을 들여 메모리를 아끼는 기법

스트리밍 · 압축 · 외부 정렬 · 정규화 · 지연 평가 · 제너레이터

두 끝 사이의 중간 지점을 만드는 장치

축출 · LRU · TTL · 캐시 무효화

저장본을 두면 따라오는 문제

낡은 데이터 · 캐시 미스 · 캐시 스탬피드 · 스와핑 · 메모리 부족

이것과 나란히 놓이는 다른 맞바꿈 축

CAP · PACELC · 지연과 처리량 · RUM 추측

이것이 속하는 상위 분류

알고리즘 · 알고리즘 분석 · 자료구조 · 성능