50,000개 행 카탈로그에서 Binary Search와 Array.includes() 비교

• 10,000개의 조회(lookup)를 50,000개 행에 대해 수행했을 때, Array.includes()는 408ms가 걸린 반면, binary search는 1ms 미만이 소요되었습니다.

• 1,000개 행에서는 두 방법의 시간이 약 2.3ms로 비슷했지만, 몇천 개를 넘어서야 그 차이가 벌어지기 시작합니다.

• binary search는 정렬된 배열(sorted array)이 필요하므로, 정렬되지 않은 카탈로그(unsorted catalog)의 경우 먼저 일회성 정렬 비용(one-time sort cost)을 지불해야 합니다.

• 단순한 함수 변경만으로 408ms가 걸리던 조회 루프를 새로운 의존성 없이 1ms 미만으로 줄였습니다.

<br>A one-line swap took a 50,000-row lookup from 408 milliseconds down to under one millisecond. I didn't want to guess at that number, so I built both versions, ran them against the same data, and timed them. Here's exactly where the time goes and when the fix is worth doing.

The Setup

I built a sorted array of 50,000 numbers, the kind of shape you get from product IDs, sorted timestamps, or any list you can order once and reuse. Then I generated a batch of lookup targets, 80% of them values that actually exist in the array and 20% that don't, so neither method gets to cheat by only testing hits.

Two functions ran against the exact same targets. The first is the one everyone reaches for without thinking: catalog.includes(target). It's built in, it reads clearly, and for small arrays it's fine. The second is a plain binary search, the kind you'd write in an interview and then forget about:

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
...

I ran both at four sizes: 1,000 rows with 2,000 lookups, 10,000 rows with 2,000 lookups, 50,000 rows with 2,000 lookups, and 50,000 rows with 10,000 lookups. Same hardware, same process, back to back, no warmup tricks either way.

I also logged the hit count for every run. Not for performance, just as a sanity check. If includes() and binary search ever disagreed on how many targets matched, I'd know one of them had a bug before I trusted a single timing number.

They never disagreed. Good, that's what you want from a sanity check.

What the Numbers Actually Showed

행 수가 1,000개일 때, includes()는 2,000번의 검색에 대해 2.50ms가 걸렸고 바이너리 서치(binary search)는 2.29ms가 걸렸습니다. 오타가 아닙니다. 이 정도 크기에서는 차이가 미미하며, 이렇게 작은 리스트를 검색하는 것이라면 코드를 다시 작성할 가치가 없습니다.

곡선은 그 이후 급격하게 휘어집니다. 행 수가 10,000개일 때, includes()는 18.12ms로 치솟은 반면 바이너리 서치는 0.30ms에 머물러 60배의 차이를 보였습니다. 동일한 2,000번의 검색으로 행 수가 50,000개일 때, includes()는 63.95ms를 기록했고 바이너리 서치는 0.30ms로 212배가 넘는 차이를 보였습니다. 이 검색 횟수를 10,000번으로 늘리고 동일한 50,000개 행을 대상으로 하면 includes()는 408.21ms까지 상승하는 반면 바이너리 서치는 0.94ms로 거의 움직이지 않습니다. 이는 432배의 차이이며, 빠릿빠릿했던 필터가 작동하지 않는 것처럼 느껴지게 만드는 종류의 수치입니다.

그 이유는 눈으로 보면 간단합니다. Array.includes()는 일치하는 항목을 찾거나 공간이 부족해질 때까지 배열을 앞에서부터 순회(walks)하기 때문에, 그 비용은 배열 크기에 비례하여 직선적으로 증가합니다. 반면 바이너리 서치는 비교할 때마다 남은 공간의 절반을 버리기 때문에, 배열을 두 배로 늘려도 단계가 하나만 추가될 뿐입니다.

이것이 핵심 원리입니다. 절반으로 나누고(Halve), 비교하고, 다시 절반으로 나눕니다(halve again).

작은 크기에서는 그 차이가 감지할 만큼 중요하지 않습니다. 하지만 수만 개의 행에 이르러서는 이것이 전체 이야기이며, 배열이 커질수록 그 격차는 계속 벌어집니다. 여기서는 백만 개 행을 테스트하지 않았지만, 곡선의 모양으로 보아 훨씬 더 불균형하게 나타날 것이라고 예상됩니다.

408ms라는 숫자를 사람들이 실제로 체감하는 수치와 비교해 보세요. 사용자가 느끼는 반응성(perceived responsiveness)에 대한 연구에 따르면 '즉각적'이라고 느껴지는 경계선은 오랫동안 100ms 근처에 위치했으며, 이 시간을 넘어서면 반응이라기보다는 지연으로 인식되기 시작합니다. 408ms는 충돌이나 정지 상태는 아니지만, 필터나 검색 상자가 응답하기보다 생각하는 것처럼 느껴질 만큼 충분히 긴 시간입니다. 1ms 미만이라면 아무것도 느낄 수 없습니다.

이 테스트는 브라우저 탭이 아닌 Node에서 실행했으므로, 절대 밀리초 값은 Chrome이나 Safari에서 볼 결과에 대한 약속이라기보다는 상대적인 비교로 간주해 주세요. 두 방법의 비율이 중요한 부분입니다. 즉, 배열 크기와 조회 비용 사이의 관계는 JavaScript 엔진이 바뀌었기 때문에 변하는 것이 아니라, 그 앞에 붙는 상수(constant)만 달라지는 것입니다.

아무도 언급하지 않는 함정

Binary search는 정렬된 배열에서만 작동합니다. 이것이 트레이드오프(trade-off)이며 공짜가 아닙니다. 만약 데이터가 정렬되지 않은 상태로 도착한다면, 한 번의 정렬 비용을 지불해야 합니다. 50,000개의 숫자 항목에 대한 Array.sort()도 실제 밀리초를 소모합니다. 물론 생각하는 것보다는 훨씬 적고, 피하려는 408ms에는 훨씬 못 미칩니다.

진짜 함정은 데이터가 자주 변경될 때 나타납니다. 정렬된 배열에 항목을 삽입할 때마다 올바른 위치를 찾고 그 뒤의 모든 것을 이동시켜야 하는데, 이것 자체가 O(n) 비용이 발생합니다. 만약 새로운 행을 지속적으로 추가하고 검색은 드물게 한다면, 간단하게 유지하고 includes()를 사용하는 것이 좋습니다. 반면에 데이터가 이미 정렬되어 있어 (예: 순서대로 할당된 ID처럼), 한 번만 정렬한 후 여러 번 검색한다면, binary search가 매번 압도적인 우위를 차지합니다.

과소평가하기 쉬운 가독성 비용(readability cost)도 있습니다. 주니어 개발자나 6개월 뒤의 당신이 catalog.includes(x)를 보면 그것이 무엇을 하는지 정확히 알고 있습니다. 반면, 직접 구현한 binary search는 주석, 테스트, 그리고 그 이유가 필요합니다.

저는 주석을 작성했습니다. 또한 빈 배열, 단일 항목, 모든 값보다 작은 대상값, 모든 값보다 큰 대상값을 확인하는 엣지 케이스(edge case)에 대한 테스트도 작성했습니다.

이러한 테스트를 건너뛰면, 세트 내에서 가장 작거나 가장 큰 값에서만 나타나는 off-by-one 오류를 배포하게 될 수 있습니다. 이는 데모에서는 통과하지만 3주 후에 프로덕션 환경에서 실패하는 바로 그 종류의 버그입니다. mid = (lo + hi) >> 1 라인은 hi가 빈 배열에서 음수가 되어 루프가 실행되지 않고, 기대했던 곳에 크게 충돌(crash loudly)할 것이 아니라 조용히

세 번째 옵션으로 거의 빠뜨릴 뻔했던 것이 있습니다: Set입니다. 이 역시 동일한 50,000행 카탈로그로 만들고 같은 10,000건의 조회 테스트를 실행했습니다. 결과는 2.61ms였는데, 이는 바이너리 서치(binary search)와 비슷한 수준이며 여전히 includes()보다 훨씬 빠릅니다. Set이나 Map은 값을 해싱하여 O(1) 시간 복잡도로 조회가 가능하므로 크기가 거의 중요하지 않습니다.

하지만 Set의 단점은 사람들이 예상하는 것보다 더 좁습니다. 오직 '이 정확한 값이 존재하는가'라는 질문에만 답할 수 있을 뿐, 다른 것은 아무것도 할 수 없습니다. 바이너리 서치는 또한 '이 값보다 크거나 같은 첫 번째 행은 무엇인가'라는 질문에도 답할 수 있는데, 이는 범위(range), 가격대(price bracket) 또는 정확한 일치(exact match) 대신 '가장 근접한 일치(closest match)'가 필요할 때 중요해집니다. 또한 Set은 이미 가지고 있는 배열을 재사용하는 것이 아니라 자체 해시 테이블을 구축하기 때문에 메모리 비용도 더 많이 듭니다. 순수한 멤버십 체크(membership check) 목적이라면 Set을 한 번만 만들고 다시는 사용하지 마십시오. 순서와 관련된 어떤 작업이 필요하다면 바이너리 서치가 여전히 올바른 도구입니다.

작은 상점의 경우 실제로 중요해지는 시점

대부분의 프론트엔드 코드는 이 차이가 중요할 만큼 큰 배열을 다루지 않습니다. 40개의 옵션이 있는 드롭다운, 수십 개의 항목이 있는 태그 목록, 설정 페이지 등은 바이너리 서치가 필요하지 않습니다. 저는 이런 것들은 그대로 두는 편입니다.

이것이 의미를 갖기 시작하는 곳은 카탈로그, 큰 태그 인덱스 또는 세션 내에서 반복적으로 쿼리하는 데이터셋을 필터링하거나 조회할 때입니다. 만약 이미 표시를 위해 데이터를 정렬하고 있다면(알파벳순, 날짜별, ID별), 가장 비용이 많이 드는 작업을 공짜로 해낸 것이며, 이때 조회 함수를 변경하는 것은 코드를 열 줄 추가하지만 검색당 1초의 일부를 되찾아줍니다.

또한 반대되는 실수를 경고합니다: 이론적으로 목록이 커질 수 있다는 이유만으로 바이너리 서치를 사용하려고 하지 마십시오. 제가 1,000행 케이스를 특별히 측정한 이유는 '언젠가 이게 클 수도 있다'는 것은 오늘 주석을 요구하는 함수를 추가하기에 나쁜 이유이기 때문입니다.

검색할 배열이 실제로 수천 개가 될 때까지 기다린 다음 변경하십시오. 그 이하에서는 내장 메서드가 가독성이 더 좋고 눈치챌 만한 비용도 들지 않습니다.

또한 해결책을 선택하기 전에 배열이 어디서 오는지도 생각해야 합니다. 만약 이 배열이 페이지 뷰마다 API 응답이나 데이터베이스 쿼리에서 새로 로드되는 경우라면, 네트워크 왕복 시간(network round trip) 비용을 이미 지불하고 있는 것이므로 도착하자마자 한 번 정렬하는 것은 거의 무료에 가깝습니다. 하지만 검색창의 키 입력마다 처음부터 다시 구축되는 경우에는, 이 모든 것이 그 근본적인 문제를 해결하기 전까지는 도움이 되지 않습니다. Binary search가 매번 비싼 작업을 반복하는 것에서 당신을 구해줄 수는 없습니다.

이것은 실제로 발생한 debounce와 throttle 호출 횟수를 세는 과정을 거치는 이유와 같습니다. 어느 것이 맞는지 들리는 대로 믿기보다는, 또는 버그가 언제 시작되었는지에 대한 직감만 믿기보다는 1000개의 실제 커밋에 걸쳐 git bisect를 실행하는 과정을 거치는 이유와 같습니다. 성능에 대한 추측은 단지 포맷만 좋은 의견일 뿐입니다.

어떤 함수를 배포해야 하는지 알 수 있는 유일한 방법은 둘 다 실행해 보고 시계를 보는 것입니다. 15분 정도 걸리며, 느낌이 아니라 실제 숫자를 얻게 됩니다.

결론

몇천 줄 이하의 행(rows)에서는 Array.includes()와 binary search가 인간이 인지할 수 있는 시간, 즉 아무런 시간이 소요되지 않는 비용을 소비합니다. 그 이후부터는 격차가 빠르게 벌어지고 계속 커져서, 제 테스트에서는 50,000개 행에 대해 10,000번 조회했을 때 432배의 차이를 보였습니다.

만약 데이터가 한 번 정렬되고 자주 검색된다면, 이 전환은 코드 10줄과 짧은 테스트 파일로 가능하며, 필터링이나 조회가 느리다고 느껴지는 날에 시도할 가치가 있습니다. 하지만 데이터가 끊임없이 변하고 검색이 드물다면, 건너뛰세요. 정렬 및 삽입 오버헤드가 이득을 보기 전에 그 이득분을 모두 소모해 버릴 것입니다.

앞으로 제가 따를 규칙은 다음과 같습니다: 배열이 커진 후에 누군가가 느리다고 불평하기 전에 측정하는 것입니다. 스톱워치가 추측보다 항상 우세하며, 어떤 함수가 실제로 배포될 자격이 있는지 알아내는 데는 단 15분밖에 걸리지 않습니다.