배열이 아니라 답을 이분 탐색한다

씬을 로딩할 때 에셋을 몇 개씩 묶어서 올릴지 정해야 합니다. 한 번에 많이 올리면 빨리 끝나지만 프레임이 튑니다. 적게 올리면 부드러운 대신 로딩이 깁니다. 프레임을 16ms 아래로 유지하면서 가장 크게 잡을 수 있는 묶음 크기를 찾고 싶습니다.

이건 배열에서 값을 찾는 문제가 아닙니다. 그런데도 이분 탐색이 그대로 먹힙니다. 성질 하나만 있으면 됩니다. 한 번 안 되기 시작하면 그 뒤로는 계속 안 된다는 것입니다.

되고 안 되고를 늘어놓으면 배열이 된다

묶음 크기를 1부터 올려 가며 되는지 표시하면 이렇게 생겼습니다.

묶음 크기   1  2  3  4  5  6  7  8
16ms 이하   O  O  O  O  X  X  X  X

크기를 키울수록 무거워지니 O 다음에 X 가 나오면 다시 O 로 돌아오지 않습니다. 이렇게 한 방향으로만 바뀌는 성질을 단조롭다고 합니다.

O 와 X 가 갈리는 경계를 찾는 일은, 0과 1이 늘어선 배열에서 1이 처음 나오는 자리를 찾는 것과 똑같습니다.

다른 점이 하나 있습니다. 이 배열은 메모리에 없습니다. a[mid] 를 읽는 대신 그 크기로 실제로 돌려 보고 되는지 묻습니다. 나머지 절차는 같습니다.

코드는 판정 함수 하나만 갈아 끼운다

int MinFeasible(int lo, int hi, Func<int, bool> ok) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;      // 되는 값이니 답 후보로 남긴다
        else         lo = mid + 1;  // 안 되면 이 값 이하는 전부 탈락
    }
    return lo;
}

ok 가 배열 접근 자리를 대신합니다. 여기서는 “이 묶음 크기로 올렸을 때 프레임이 16ms 이하인가” 입니다. 이렇게 답의 범위를 이분 탐색하는 것에 붙은 이름이 파라메트릭 서치(parametric search) 입니다.

찾는 것이 최댓값이면 판정을 뒤집습니다. 위 예는 “무거워지는 쪽” 이라 O 가 앞에 오니, “O 인 것 중 가장 큰 값” 은 MinFeasible 이 돌려준 첫 X 자리에서 하나 뺀 값입니다. 헷갈리면 조건을 반대로 세우는 대신 찾은 경계에서 한 칸 물러나는 쪽이 실수가 적습니다.

어디에 쓰나

경계가 궁금한 설정값은 대체로 이 모양입니다.

판정 한 번이 비싸다는 것이 이 방식의 특징입니다. 배열 접근은 나노초지만 여기서는 실제로 돌려 봐야 합니다. 그래서 비교 횟수를 줄이는 것이 그대로 시간이 됩니다. 후보가 1,000가지여도 열 번만 재면 됩니다.

실수 범위는 반복 횟수로 끊는다

묶음 크기는 정수지만 사거리나 각도는 실수입니다. 실수에는 “다음 값” 이 없어서 lo < hi 로는 안 끝납니다.

float lo = 0f, hi = 100f;

for (int i = 0; i < 60; i++) {      // 횟수를 고정한다
    float mid = (lo + hi) / 2f;
    if (ok(mid)) hi = mid;
    else         lo = mid;
}

return hi;

hi - lo < 0.001f 같은 조건도 되지만 반복 횟수를 고정하는 쪽이 안전합니다. 부동소수 오차 때문에 조건이 영영 안 만족되는 경우가 생기기 때문입니다. 한 번에 절반이니 예순 번이면 어떤 범위든 충분히 좁혀집니다.

단조롭지 않으면 못 쓴다

이 방식이 성립하는 이유는 한 번 X 가 나오면 그 뒤로 전부 X 라는 보장 하나뿐입니다. 그 보장이 없으면 답이 엉뚱하게 나옵니다.

게임에서 이 전제가 깨지는 자리가 실제로 있습니다.

• 측정값으로 판정할 때. 프레임 시간은 잴 때마다 흔들립니다. 경계 근처에서 한 번 운 좋게 통과하면 그 위쪽을 통째로 버립니다
• 효과가 계단식일 때. 텍스처 크기는 2의 제곱에서 메모리가 꺾입니다. 중간값은 의미가 없습니다
• 두 자원이 반대로 움직일 때. 크게 잡으면 CPU 가 편해지고 GPU 가 힘들어지는 식이면 하나의 판정으로 안 됩니다

측정으로 판정할 때는 한 번 재고 넘어가지 말고 여러 번 재서 중앙값을 쓰거나, 경계에 여유를 두는 편이 낫습니다. 16ms 를 기준으로 하면서 실제로는 14ms 로 잡는 식입니다. 노이즈가 신호보다 크면 이분 탐색이 아니라 측정을 먼저 고쳐야 합니다.

정리

찾는 대상이 배열 안에 없어도 이분 탐색을 쓸 수 있습니다. 필요한 것은 판정이 한 방향으로만 바뀐다는 성질입니다.

• 되는 값과 안 되는 값을 늘어놓으면 0과 1이 늘어선 배열이 되고, 경계를 찾는 일은 첫 1을 찾는 일과 같습니다
• 배열 접근 자리에 판정 함수를 넣습니다. 판정이 비쌀수록 이 방식이 이득입니다
• 실수 범위에서는 조건 대신 반복 횟수를 고정합니다
• 판정이 흔들리면 쓰면 안 됩니다. 측정으로 판정할 때는 노이즈부터 줄이고 시작합니다