순차 탐색과 자기 조직화

휴대전화의 연락처가 이름순이 아니라 저장한 순서대로 들어 있다고 해 봅시다. 원하는 사람을 찾으려면 위에서부터 하나씩 확인해야 하고, 자주 연락하는 사람이 목록 맨 아래에 있으면 찾을 때마다 오래 걸립니다. 그렇다면 찾을 때마다 그 사람을 위쪽으로 옮겨 두면 어떨까요? 이렇게 요청을 처리하면서 목록이 스스로 순서를 바꾸는 방법을 자기 조직화 리스트(self-organizing list)라고 합니다. 이 글에서는 순차 탐색의 비용이 찾는 값의 위치에 따라 정해진다는 점에서 출발해, 순서를 바꾸는 세 가지 규칙을 실제 요청열에 돌려 보며 비교합니다.

순차 탐색의 비용은 위치가 정한다

순차 탐색(linear search)은 목록의 왼쪽부터 하나씩 목표와 같은지 비교합니다. 목표가 인덱스 i에 있으면 i + 1번 비교한 뒤 멈추고, 목표가 없으면 n개를 모두 비교한 뒤에야 없다고 답할 수 있습니다. 그래서 같은 목록이라도 무엇을 찾느냐에 따라 비용이 달라지며, 많이 찾는 값이 앞쪽에 있을수록 전체 비용이 줄어듭니다.

예를 들어 [A, B, C, D]에서 네 값을 똑같이 자주 찾는다면 한 번에 평균 (1 + 2 + 3 + 4) / 4 = 2.5번을 비교합니다. 그런데 요청의 절반이 D이고 나머지 절반을 A, B, C가 똑같이 나누어 가진다면 사정이 달라집니다. 이 순서에서는 평균 비교 횟수가 (1 + 2 + 3) / 6 + 4 × 1/2 = 3번이지만, D를 맨 앞으로 옮긴 [D, A, B, C]에서는 1 × 1/2 + (2 + 3 + 4) / 6 = 2번으로 줄어듭니다.

이처럼 요청의 빈도를 미리 안다면 많이 찾는 값부터 늘어놓는 것이 가장 좋습니다. 문제는 빈도를 미리 모르거나, 시간이 지나면서 많이 찾는 값이 바뀌는 경우입니다. 자기 조직화 리스트는 지금까지 들어온 요청을 보고 순서를 조금씩 고쳐 나가며 이 문제에 대응합니다.

순서를 바꾸는 세 가지 규칙

가장 널리 알려진 규칙은 세 가지입니다. move-to-front는 찾은 원소를 맨 앞으로 옮깁니다. transpose는 찾은 원소를 바로 앞 원소와 맞바꾸어 한 칸만 앞으로 옮깁니다. 빈도 정렬(frequency count)은 원소마다 요청 횟수를 세어 두고, 찾은 원소의 횟수를 1 늘린 뒤 바로 앞 원소의 횟수보다 커져 있는 동안 한 칸씩 앞으로 옮깁니다. 횟수가 같으면 옮기지 않으므로, 횟수가 같은 원소끼리는 먼저 앞에 있던 원소가 그대로 앞에 남습니다.

아무 요청도 받지 않은 [A, B, C, D]에서 C를 한 번 찾으면 목록은 다음과 같이 바뀝니다.

세 규칙은 요청 한 번에 반응하는 정도가 다릅니다. move-to-front는 한 번의 요청만으로 맨 앞까지 가므로 최근 요청을 가장 크게 반영하고, transpose는 한 칸씩만 움직이므로 여러 번 요청되어야 앞으로 나옵니다. 빈도 정렬은 요청이 최근에 왔는지 오래전에 왔는지와 상관없이 누적 횟수만 봅니다. 이 차이가 요청열의 모양에 따라 어떤 결과로 이어지는지 직접 돌려 보겠습니다.

요청열에 돌려 보기

아래 코드는 네 가지 방법을 같은 모양의 함수로 만듭니다. 각 함수는 목록, 요청 하나, 요청 횟수를 담은 딕셔너리를 받아 목록을 그 자리에서 고치고, 그 요청에 든 비교 횟수를 돌려줍니다. 요청 횟수는 빈도 정렬만 쓰지만, 모든 함수를 같은 방식으로 부를 수 있도록 다른 함수도 받게 했습니다. values.insert(0, values.pop(index))는 index 위치의 원소를 빼서 맨 앞에 다시 넣는 식입니다.

total_cost는 시작 목록을 복사한 뒤 요청열의 글자를 하나씩 요청으로 처리하고, 비교 횟수의 합과 마지막 목록을 함께 돌려줍니다. 마지막 반복문의 [0]은 그중 비교 횟수의 합만 꺼냅니다.

def find(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


def keep(values, target, counts):
    index = find(values, target)
    return index + 1 if index >= 0 else len(values)


def move_to_front(values, target, counts):
    index = find(values, target)
    if index < 0:
        return len(values)
    values.insert(0, values.pop(index))
    return index + 1


def transpose(values, target, counts):
    index = find(values, target)
    if index < 0:
        return len(values)
    if index > 0:
        values[index - 1], values[index] = values[index], values[index - 1]
    return index + 1


def frequency(values, target, counts):
    index = find(values, target)
    if index < 0:
        return len(values)
    cost = index + 1
    counts[target] = counts.get(target, 0) + 1
    while index > 0 and counts.get(values[index - 1], 0) < counts[target]:
        values[index - 1], values[index] = values[index], values[index - 1]
        index -= 1
    return cost


def total_cost(strategy, start, requests):
    values = list(start)
    counts = {}
    total = 0
    for target in requests:
        total += strategy(values, target, counts)
    return total, values


start = ["A", "B", "C", "D"]
strategies = [keep, move_to_front, transpose, frequency]
for requests in ["DDDDCCCC", "DCDCDCDC", "ABCDABCD"]:
    print(requests, [total_cost(s, start, requests)[0] for s in strategies])

DDDDCCCC [28, 14, 20, 17]
DCDCDCDC [28, 20, 32, 17]
ABCDABCD [20, 26, 21, 20]

각 줄의 숫자는 그대로 두기, move-to-front, transpose, 빈도 정렬의 순서로 요청 여덟 번의 비교 횟수를 모두 더한 값입니다.

첫 번째 요청열은 D를 네 번 몰아서 찾은 뒤 C를 네 번 몰아서 찾습니다. 같은 값이 잇달아 요청되는 이런 성질을 지역성(locality)이라고 하며, 여기서는 move-to-front가 14번으로 가장 적습니다. 첫 요청 한 번에 맨 앞으로 옮겨 두고 나머지 세 번을 비교 한 번씩으로 처리하기 때문입니다. transpose는 맨 앞까지 오는 데 요청이 여러 번 필요해서 20번이 들었습니다.

두 번째 요청열은 목록 끝의 D와 C를 번갈아 찾습니다. 이번에는 transpose가 32번으로, 순서를 그대로 둔 28번보다도 나쁩니다. 아래 표처럼 D를 찾으면 D와 C가 자리를 바꾸고, 이어서 C를 찾으면 다시 자리를 바꾸어 두 값이 끝의 두 칸을 끝없이 오가기 때문입니다.

move-to-front는 처음 두 번에 D와 C를 앞쪽으로 가져온 뒤로는 매번 2번만 비교합니다. 빈도 정렬은 17번으로 가장 적습니다. D와 C가 앞의 두 칸에 자리 잡은 뒤에는 먼저 요청된 D의 횟수가 늘 C보다 적지 않아서 둘이 자리를 바꾸지 않고, 그래서 D는 1번, C는 2번 비교로 찾기 때문입니다.

세 번째 요청열은 A, B, C, D를 차례로 돌아가며 두 번 찾습니다. 이번에는 move-to-front가 26번으로 가장 나쁩니다. 방금 찾은 값을 맨 앞에 두면 다음에 찾을 값이 한 칸씩 뒤로 밀려서, 첫 바퀴가 지난 뒤로는 찾을 값이 늘 맨 끝에 있게 되기 때문입니다. 원래 순서가 이미 요청 순서와 잘 맞아서 그대로 두기와 빈도 정렬이 20번으로 가장 적습니다.

세 결과를 모으면 어느 규칙도 모든 요청열에서 이기지 못합니다. 요청이 몰려서 오면 move-to-front가, 몇 개의 값이 꾸준히 자주 요청되면 빈도 정렬이 유리하고, 요청이 고르게 돌아가면 순서를 바꾸는 것 자체가 손해일 수 있습니다. 그래서 실제로 쓸 때는 예상되는 요청열로 직접 재 보고 고릅니다.

더 깊이: move-to-front가 크게 손해 보지 않는 이유

앞으로 어떤 요청이 올지 모르는 채로 그때그때 결정을 내리는 알고리즘을 온라인 알고리즘(online algorithm)이라고 합니다. 세 규칙은 모두 지금까지의 요청만 보고 순서를 바꾸므로 온라인 알고리즘입니다. 이런 알고리즘은 요청열 전체를 미리 알고 가장 좋게 재배치하는 가상의 방법과 비용을 비교해 평가하는데, 이것을 경쟁 분석(competitive analysis)이라고 합니다.

Sleator와 Tarjan은 1985년 논문 「Amortized Efficiency of List Update and Paging Rules」에서, 어떤 요청열에서든 move-to-front의 총비용이 그런 가상의 최선 방법이 드는 비용의 대략 두 배를 넘지 않는다는 것을 증명했습니다. 반면 transpose와 빈도 정렬에는 이런 상수 배의 한계가 없다는 것도 같은 논문에서 보였습니다. 앞의 번갈아 요청이 transpose에 그런 예입니다. 목록 길이가 n이면 transpose는 요청마다 n번을 비교하지만, move-to-front는 처음 두 번이 지나면 요청마다 2번만 비교하므로 n이 클수록 차이가 벌어집니다. 다만 이것은 가장 나쁜 요청열을 기준으로 한 이야기라서, 실제 요청의 모양을 안다면 그 모양으로 직접 재 보는 편이 더 정확합니다.

순서를 바꿔도 찾는 결과는 같다

재배치 규칙이 올바르려면 두 가지가 지켜져야 합니다. 첫째, 목록에 든 원소의 종류와 개수가 바뀌면 안 됩니다. move-to-front는 pop으로 뺀 원소를 그대로 insert로 다시 넣고, transpose와 빈도 정렬은 이웃한 두 원소를 맞바꾸기만 하므로 이 조건이 지켜집니다. 둘째, 각 요청의 탐색 결과가 맞아야 합니다. 탐색은 재배치하기 전에 순차 탐색으로 하므로, 목표가 있으면 찾고 없으면 끝까지 비교한 뒤 없다고 답합니다. 순차 탐색은 순서와 상관없이 모든 원소를 볼 수 있으므로, 순서는 결과에는 영향을 주지 않고 비용에만 영향을 줍니다.

목표를 찾지 못했을 때는 순서를 바꾸지 않습니다. 세 함수가 index < 0을 먼저 확인하는 것은 이 때문인데, 이 확인을 빠뜨리면 어떤 일이 생기는지는 연습 문제 2에서 다룹니다. 또 재배치 뒤에는 원소의 위치가 바뀌므로, 탐색이 돌려준 인덱스를 저장해 두었다가 나중에 쓰면 다른 원소를 가리킬 수 있습니다. 자기 조직화 리스트에서는 위치 대신 찾은 값이나 그 값에 딸린 정보를 돌려주는 편이 안전합니다.

재배치에 드는 비용과 쓰임

재배치는 공짜가 아닙니다. Python 리스트에서 values.insert(0, values.pop(index))를 하면, 앞 글에서 본 것처럼 pop이 뒤쪽 원소를 앞으로 당기고 insert가 다시 모든 원소를 뒤로 밀어 O(n)이 듭니다. 앞쪽 index개만 한 칸씩 뒤로 밀도록 직접 옮기면 O(index)로 줄일 수 있지만, 어느 쪽이든 요청 한 번의 비용이 최악의 경우 O(n)이라는 사실은 바뀌지 않습니다. 원소들을 다음 원소의 참조로 이어 둔 연결 리스트(linked list)를 쓰면 찾은 원소를 떼어 맨 앞에 붙이는 일이 O(1)이라서, 자기 조직화 리스트는 흔히 연결 리스트로 설명합니다. transpose의 교환은 어느 쪽이든 O(1)이고, 빈도 정렬은 요청 횟수를 기억할 O(n) 공간이 더 필요합니다.

목록이 길고 같은 목록에서 여러 번 찾는다면, 재배치보다 딕셔너리로 바로 찾거나 정렬해 두고 이진 탐색을 쓰는 편이 대개 낫습니다. 자기 조직화는 목록이 짧을 때, 키로 바로 찾을 수 없는 조건이라 하나씩 훑어야 할 때, 최근에 쓴 것이 곧 다시 쓰이는 경향이 강할 때 쓸모가 있습니다. 최근에 쓴 것을 앞에 두는 생각은 캐시(cache)에서 가장 오래 쓰지 않은 것부터 버리는 LRU(least recently used) 규칙과 같은 뿌리이고, bzip2 압축 프로그램은 move-to-front 변환을 압축 과정의 한 단계로 씁니다.

정리

• 순차 탐색은 인덱스 i의 값을 i + 1번 비교로 찾고, 없는 값은 n번을 모두 비교합니다. 많이 찾는 값이 앞에 있을수록 전체 비용이 줄어듭니다.
• move-to-front는 찾은 원소를 맨 앞으로, transpose는 한 칸 앞으로 옮기고, 빈도 정렬은 누적 요청 횟수가 큰 순서를 유지합니다.
• 어느 규칙도 모든 요청열에서 가장 좋지는 않습니다. 몰려 오는 요청에는 move-to-front가, 꾸준히 치우친 요청에는 빈도 정렬이 유리하고, 고르게 돌아가는 요청에서는 재배치가 오히려 손해일 수 있습니다.
• 재배치는 원소를 빼서 다시 넣거나 이웃끼리 맞바꾸기만 하므로 원소의 종류와 개수가 그대로이고, 탐색 결과는 순서와 상관없이 정확합니다.

연습 문제

1. transpose를 두 번 적용하기

[A, B, C, D]에서 D를 두 번 연속 요청하고 매번 transpose를 적용합니다. 각 요청 뒤의 목록과 두 요청의 비교 횟수 합을 구하세요.

2. 없는 값을 요청했을 때

[A, B, C, D]에서 목록에 없는 X를 요청하면 본문의 transpose는 몇 번 비교하고 목록을 어떻게 남기나요? 또 index < 0 확인 없이 바로 교환하면 어떻게 될까요?

def find(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


values = ["A", "B", "C", "D"]
index = find(values, "X")
values[index - 1], values[index] = values[index], values[index - 1]
print(index, values)

-1 ['A', 'B', 'D', 'C']

3. 재배치가 손해인 요청열

[A, B, C, D]에서 시작해 요청열 BABABA를 처리합니다. 그대로 두기, move-to-front, transpose의 비교 횟수 합을 손으로 구하고, 순서를 바꾸는 쪽이 왜 손해인지 설명하세요.

다음 글 반열린 구간으로 첫 이진 탐색 만들기에서는 목록이 정렬되어 있다는 조건을 이용해, 하나씩 보지 않고 비교 한 번마다 후보를 절반으로 줄이는 방법을 다룹니다.