자료구조 - 담는 그릇이 속도를 정한다

회원 10만 명 중에 이메일로 한 명을 찾는다. 코드는 세 줄인데 어떤 구현은 즉시 끝나고 어떤 구현은 눈에 띄게 느리다. 갈린 건 알고리즘이 아니라 어디에 담아뒀느냐다.

상자 하나에 다 넣으면

주방을 떠올려 보자. 그릇이든 국자든 양념이든 큰 상자 하나에 다 넣어두는 집이 있다. 넣기는 세상 편하다. 문을 열고 던져 넣으면 끝이다.

문제는 꺼낼 때다. 후추가 필요하면 상자를 뒤진다. 운이 좋으면 맨 위에서 나오고, 없으면 바닥까지 다 뒤진 뒤에야 없다는 걸 안다.

코드에서 리스트가 딱 이 상자다.

for (User u : users) {
    if (u.email.equals(target)) return u;
}
return null;

넣는 건 맨 뒤에 붙이면 그만이다. 찾는 건 처음부터 하나씩 본다. 10만 명이면 최악에 10만 번이고, 없는 이메일일 때가 항상 최악이다. 끝까지 다 봐야 없다고 답할 수 있으니까.

이 상자를 가나다순 선반으로 바꾸면 찾기가 빨라진다. 그런데 공짜는 아니다. 그게 이 시리즈 전체의 이야기다.

그릇이 정하는 건 ‘무엇이’ 빠른가다

여기서 흔한 오해를 하나 걷어내야 한다. 자료구조는 빠른 것과 느린 것으로 나뉘지 않는다.

가나다순으로 꽂아둔 선반은 찾기가 빠르다. 대신 물건이 하나 늘 때마다 제자리를 벌려 끼워 넣어야 한다. 상자는 반대다. 넣기가 공짜인 대신 찾기를 매번 비싸게 치른다.

그러니까 그릇을 고르는 일은 “제일 빠른 걸 고른다”가 아니다. 어느 동작을 싸게 하고 어느 동작을 비싸게 할지 고르는 일이다. 하루에 한 번 넣고 만 번 찾는다면 선반이 옳고, 만 번 넣고 한 번 훑는다면 상자가 옳다.

“이 자료구조가 제일 좋나요”라는 질문에 답이 없는 이유가 이거다. 무엇을 자주 하느냐를 먼저 말해야 답이 나온다.

네 가지를 묻는다

그래서 새 그릇을 만나면 물어볼 것이 정해져 있다. 넷이다.

자료구조를 외운다는 건 이름을 외우는 게 아니라 각 그릇이 이 네 질문에 어떻게 답하는지를 아는 것이다. 이 시리즈에서 그릇을 하나씩 열어볼 때마다 결국 이 넷으로 돌아온다.

넷 중 무엇이 중요한지는 만드는 것마다 다르다. 알림 큐는 넣기와 빼기만 있으면 되고 찾기는 필요 없다. 회원 조회는 찾기가 전부다. 필요 없는 걸 빠르게 만드느라 필요한 걸 느리게 만드는 게 가장 흔한 실수다.

붙여 두느냐, 꼬리표로 잇느냐

그릇을 만드는 방식은 밑바닥에서 두 갈래로 갈린다. 한자리에 붙여 두거나, 흩어 두고 꼬리표로 잇거나다.

붙여 두면 세 번째 것을 바로 집는다. 시작 자리에 두 칸을 더한 곳으로 곧장 가면 되기 때문이다. 대신 중간에 하나 끼워 넣으려면 뒤를 전부 밀어야 한다.

흩어 두면 반대다. 끼워 넣기는 꼬리표만 고쳐 잇는 일이라 싸다. 대신 세 번째 것을 보려면 첫째부터 꼬리표를 따라 걸어야 한다. 건너뛸 방법이 없다.

빠르다를 무엇으로 재나

“이 방법이 빠르다”를 초로 재면 안 된다. 기계가 바뀌면 숫자가 통째로 달라지기 때문이다. 그래서 세는 건 시간이 아니라 일의 횟수, 그리고 보는 건 절대값이 아니라 데이터가 늘 때 그 횟수가 어떻게 늘어나는가다.

상자를 뒤지는 방식은 물건이 10배 늘면 뒤지는 횟수도 10배 는다. 정렬해두고 반씩 접어 들어가는 방식은 10배가 늘어도 횟수는 서너 번 더 늘 뿐이다.

오른쪽 열이 거의 안 자라는 게 보인다. 데이터가 100만 배 늘었는데 일은 세 배가 됐다. 이 “어떻게 늘어나는가”를 적는 표기법이 빅오이고, 다음 글에서 그것만 따로 본다.

미리 일해두면 나중이 싸다

선반이 상자보다 찾기가 빠른 진짜 이유는 선반이 좋아서가 아니다. 넣을 때 이미 순서를 맞추는 일을 해뒀기 때문이다. 찾을 때 안 하는 일을 넣을 때 했을 뿐, 일이 사라진 게 아니다.

자료구조에서 “빠르다”는 대개 이 모양이다. 일을 없앤 게 아니라 옮긴 것이다.

• 정렬해 두면 찾기가 싸진다. 대신 넣을 때마다 자리를 지켜야 한다.
• 라벨을 계산해 두면 곧장 집는다. 대신 라벨을 만드는 비용을 매번 낸다.
• 따로 목록을 하나 더 들면 조회가 준다. 대신 원본이 바뀔 때 그 목록도 같이 고쳐야 한다.

데이터베이스 인덱스가 정확히 세 번째다. 조회를 빠르게 하려고 정렬된 목록을 하나 더 들고, 그 대가로 INSERT마다 그 목록도 손본다. 인덱스를 많이 걸면 쓰기가 느려진다는 말이 여기서 나온다.

그래서 그릇을 고르기 전에 물어야 할 게 하나 더 있다. 읽기가 많은가, 쓰기가 많은가. 미리 해두는 일은 나중에 여러 번 찾을 때만 남는 장사다.

이미 매일 쓰고 있다

여기까지 읽고 “실무에서는 이런 걸 직접 안 만드는데”라고 생각했다면 절반만 맞다. 직접 만들지 않을 뿐 매일 고르고 있다.

Map을 쓸지 List를 쓸지 고르는 순간이 곧 자료구조를 고르는 순간이다. 대개는 아무거나 써도 티가 안 난다. 데이터가 커지고 나서야 그 선택이 드러난다. 100건일 땐 뭘 써도 즉시 끝나지만 100만 건이 되면 상자와 선반의 차이가 응답 시간에 그대로 나온다.

성능 문제를 붙잡고 있는데 코드에 이상한 데가 없다면, 그릇을 잘못 골랐는지 보는 게 빠른 길일 때가 많다. 반대로 아직 100건인 데이터를 위해 정교한 그릇을 짜는 건 미리 낸 값만 남는 일이다.

이름이 겹치는 두 자리

이 시리즈를 읽기 전에 미리 갈라둘 게 있다. 뒤에 나올 이름 둘이 이 블로그의 다른 글에서 전혀 다른 뜻으로 쓰인다.

힙은 두 가지다. 메모리의 힙은 프로그램이 오래 쓸 데이터를 얻어 쓰는 영역이다. 이 시리즈에서 볼 힙은 제일 큰 값이 늘 꼭대기에 있는 그릇이고, 둘은 이름만 같고 아무 관계가 없다.

해시도 두 가지다. 암호에서의 해시는 되돌릴 수 없게 뭉개는 게 목적이다. 자료구조에서의 해시는 어느 서랍에 넣을지 자리를 계산하는 게 목적이라, 되돌릴 수 없다는 성질은 곁다리다. 같은 낱말이 목적이 다른 두 곳에 쓰이는 것뿐이다.

정리

• 자료구조는 빠른 것과 느린 것으로 안 나뉜다. 무엇을 싸게 하고 무엇을 비싸게 할지 고르는 일이다.
• 그릇을 만나면 넷을 묻는다. 넣기·빼기·찾기·훑기. 무엇이 중요한지는 만드는 것마다 다르다.
• 밑바닥은 두 갈래다. 붙여 두면 곧장 집고 끼우기가 비싸고, 흩어 두고 꼬리표로 이으면 반대다.
• “빠르다”는 대개 일을 없앤 게 아니라 옮긴 것이다. 미리 해두는 일은 나중에 여러 번 찾을 때만 남는다.
• 재는 단위는 초가 아니라 데이터가 늘 때 일이 몇 배가 되는가다.

다음 글은 그 “몇 배가 되는가”만 따로 본다. 빅오는 어려운 수학이 아니라 그래프의 모양을 이름으로 부르는 것에 가깝다.