순차 탐색과 자기 조직화

정렬되지 않은 작은 목록에서는 하나씩 보는 방법이 가장 명확합니다. 자주 찾는 항목을 앞에 둔다면 이후 탐색은 달라질까요? 목표는 탐색과 목록 재배치가 서로 다른 작업임을 이해하는 것입니다. 원본 복사와 첫 위치 반환 약속을 복습하세요.

개념과 약속

순차 탐색은 왼쪽부터 같음을 비교합니다. 자기 조직화는 과거 요청을 사용해 목록 순서를 바꾸는 전략입니다. move-to-front는 찾은 항목을 맨 앞으로, transpose는 바로 앞 항목과 한 칸 교환합니다. 빈도 정렬은 누적 요청 횟수가 큰 항목을 앞에 놓습니다. 과거 요청이 앞으로도 비슷하게 반복된다는 가정이 있어야 이 변화가 유리합니다.

아래 구현들은 설명을 쉽게 비교하려고 원본을 복사해 새 목록을 반환합니다. 찾지 못하면 순서는 그대로입니다. 빈도 동률은 원래 순서를 보존합니다. 요청 횟수 사전은 외부에서 누적했다고 가정하며 이 함수가 자동으로 횟수를 늘리지 않습니다.

손으로 상태 추적하기

직후에 A만 반복해서 찾는다면 앞으로 이동은 A를 한 칸 밀어 비용을 늘립니다. 현재 요청 하나에서 이득이 났다고 전체 요청열에서도 이득이 난다는 보장은 아닙니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

result.pop(index)는 그 위치 원소를 빼서 반환하고 insert(0, ...)는 맨 앞에 넣습니다. counts.get(value, 0)는 기록이 없으면 0을 씁니다. lambda value: ...는 그 값의 정렬 기준을 계산하는 짧은 함수이며 음수 빈도를 써 큰 빈도가 먼저 오게 합니다.

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


def move_to_front(values, target):
    result = list(values)
    index = linear_search(result, target)
    if index >= 0:
        result.insert(0, result.pop(index))
    return result


def transpose(values, target):
    result = list(values)
    index = linear_search(result, target)
    if index > 0:
        result[index - 1], result[index] = result[index], result[index - 1]
    return result


def frequency_order(values, counts):
    return sorted(values, key=lambda value: -counts.get(value, 0))


items = ["A", "B", "C", "D"]
print(linear_search(items, "C"))
print(move_to_front(items, "C"))
print(transpose(items, "C"))
print(frequency_order(items, {"A": 2, "B": 1, "C": 5, "D": 1}))
print(items)

실행 결과:

2
['C', 'A', 'B', 'D']
['A', 'C', 'B', 'D']
['C', 'A', 'B', 'D']
['A', 'B', 'C', 'D']

왜 맞고 언제 끝나는가

첫 일치 이전에는 목표가 없다는 순차 탐색의 사실이 유지됩니다. 재배치는 원소 하나를 빼고 같은 원소를 다른 위치에 넣으므로 원소의 개수와 종류를 보존합니다. 각 함수는 유한한 탐색·복사·정렬을 하므로 종료합니다.

비용과 적용 범위

탐색과 원본 복사는 O(n)입니다. move-to-front는 앞 삽입 때문에 O(n) 이동도 필요합니다. transpose의 교환 자체는 O(1)이지만 이 구현 전체는 복사와 탐색 때문에 O(n)입니다. 빈도 정렬은 일반적으로 O(n log n) 비교 기반 정렬을 사용합니다. 요청열 전체 성능은 별도로 측정해야 합니다.

스스로 풀어 보기

1. [A,B,C,D]에서 D를 두 번 연속 요청해 매번 transpose를 적용한 목록을 쓰세요.
2. 없는 항목 X를 요청할 때 반환 목록과 첫 위치는 무엇인가요?

힌트

1. 요청 한 번마다 한 칸만 움직입니다.
2. -1을 잘못 마지막 인덱스로 사용하지 않아야 합니다.

해설

1. 먼저 [A,B,D,C], 다음 [A,D,B,C]입니다.
2. 목록은 그대로이고 탐색 반환값은 -1입니다. index > 0 또는 index >= 0 검사가 없는 코드는 마지막 항목을 잘못 바꿀 수 있습니다.

흔한 오해

자주 찾는 값이 항상 맨 앞이라고 가정하면 안 됩니다. 빈도와 최근 요청은 다른 정보이며 어느 전략이 좋은지는 실제 요청 패턴에 달렸습니다.

복습과 다음 연결

다음 이진 탐색은 정렬이라는 강한 조건을 사용해 후보를 절반씩 줄입니다.