도구스개발

HyperLogLog 정확도·메모리 계산기

정밀도 p에서 HyperLogLog의 레지스터 수·표준오차·메모리를 계산하고, 목표 오차에 필요한 p를 거꾸로 찾습니다. 레지스터를 4배 늘려야 오차가 절반이 되는 관계를 표로 확인할 수 있습니다.

레지스터 수는 2^p입니다. 레디스는 14를 씁니다.

p
개

오차를 «개수»로 환산하고, 정확히 셀 때와 견주는 데 씁니다.

표준오차

0.813%

레지스터 16,384개 · 12KB

레지스터 수 (2^p)16,384개
메모리12KB
68% 구간 (±1σ)9,918,750 ~ 10,081,250
95% 구간 (±2σ)9,837,500 ~ 10,162,500
정확히 세면 (항목당 8바이트)76.3MB
몇 분의 1인가6,510분의 1
오차가 «상대»오차입니다. 표준오차 1.04/√m은 개수가 아니라 비율이라, 고유값이 1만 개든 100억 개든 0.813%로 같습니다. 메모리도 개수와 무관하게 12KB로 고정입니다 — 그래서 개수가 커질수록 이득이 커집니다. 지금 개수를 정확히 세려면 최소 76.3MB가 드니 약 6,510분의 1입니다.
레지스터를 4배로 늘려야 오차가 절반이 됩니다. √m이 분모라서입니다. p를 1만 올리면 메모리는 두 배인데 오차는 √2인 1.41분의 1로만 줄어듭니다. 지금 p=14에서 p=16로 가면 오차가 0.813%에서 0.406%로 절반이 되지만 메모리는 12KB에서 48KB가 됩니다. 정확도를 조금 올리는 데 메모리가 크게 드는 구조입니다.
p레지스터메모리표준오차이 개수의 ±1σ
8256192바이트6.5%±650,000
101,024768바이트3.25%±325,000
124,0963KB1.63%±162,500
1416,38412KB0.813%±81,250
1665,53648KB0.406%±40,625
18262,144192KB0.203%±20,313

이 오차를 지키는 가장 작은 p를 고릅니다.

오차 1% 이내에 필요한 pp=14 · 레지스터 16,384개
그때의 실제 오차와 메모리0.813% · 12KB
레지스터가 6비트인 이유가 있습니다. 64비트 해시에서 앞 p비트를 떼면 50비트가 남고, 0이 연달아 나오는 길이는 그보다 클 수 없습니다. 6비트면 63까지 담으니 넉넉합니다. 1바이트로 두면 다루기는 쉬워도 메모리가 정확히 3분의 4배로 늡니다 — 지금 설정에서 12KB와 16KB의 차이입니다.
고유값이 40,960개보다 적으면 다른 식으로 갈아탑니다. 원 추정식은 개수가 적을 때 레지스터 대부분이 비어 조화평균이 왜곡되기 때문입니다. 추정값이 2.5m보다 작으면 빈 레지스터 수 V를 세어 선형 계수 m·ln(m/V)로 답합니다. 지금 넣은 개수는 이 임계 위라 원 추정식을 씁니다.
여기 나오는 것은 표준오차입니다. 실제 한 번의 추정은 이보다 좋을 수도 나쁠 수도 있으며, 대략 3분의 2가 ±1σ 안에, 20번에 19번쯤이 ±2σ 안에 듭니다. 결과를 «10,000,000개»가 아니라 «9,837,500~10,162,500개로 추정됩니다»로 읽는 편이 맞습니다. 여러 HLL을 합쳐도(레지스터마다 최댓값을 취하면 됩니다) 오차 특성이 유지되는 것이 이 자료구조의 큰 장점입니다.

사용 방법

  1. 1정밀도 p를 고릅니다. 레지스터 수가 2^p가 됩니다.
  2. 2레지스터 하나를 6비트로 쓸지 1바이트로 쓸지 고릅니다.
  3. 3세려는 고유값 개수를 넣으면 오차가 개수로 환산되고, 정확히 셀 때와 견줄 수 있습니다.
  4. 4목표 오차를 고르면 그 오차를 지키는 가장 작은 p가 거꾸로 나옵니다.

자주 묻는 질문

표준오차 = 1.04 ÷ √m이며, m은 레지스터 수 2^p입니다. p=14면 레지스터 16,384개에 오차 0.81%, p=16이면 65,536개에 0.41%입니다. 상대오차라서 고유값이 1만 개든 100억 개든 오차 비율이 같습니다.

레지스터 하나에 6비트씩, 모두 m × 6 ÷ 8 바이트입니다. 레디스가 쓰는 p=14는 16,384 × 6 ÷ 8 = 12,288바이트, 곧 12KB입니다. 고유값 개수와 무관하게 이 크기로 고정이라, 1000만 개를 정확히 세려고 8바이트 해시만 담아도 80MB가 드는 것과 비교하면 6천분의 1 남짓입니다.

네 배 듭니다. 오차가 1.04/√m이라 √m이 두 배가 되어야 오차가 절반이 되고, 그러려면 레지스터가 4배여야 합니다. p를 1만 올리면 메모리는 두 배인데 오차는 √2인 1.41분의 1로만 줄어듭니다. 정확도를 조금 올리는 데 메모리가 크게 드는 구조입니다.

추정값이 2.5m보다 작으면 다른 식으로 갈아탑니다. 개수가 적으면 레지스터 대부분이 비어 원 추정식의 조화평균이 왜곡되기 때문입니다. 이 구간에서는 빈 레지스터 수 V를 세어 선형 계수 m·ln(m/V)로 답하며, 실제 구현은 대부분 이 전환을 자동으로 합니다.

p=14, 곧 레지스터 16,384개에 6비트씩 쓰기 때문입니다(16,384 × 6 ÷ 8 = 12,288바이트). 이때 표준오차가 0.81%로, 대부분의 집계 용도에 충분하면서 키 하나가 12KB를 넘지 않는 지점입니다. 개수가 아주 적을 때는 희소 표현으로 더 작게 담다가 커지면 이 조밀 표현으로 바꿉니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.

알아두면 좋은 점

  • 1.04/√m은 표준오차입니다. 한 번의 추정이 이 안에 든다는 보장이 아니라, 대략 3분의 2가 ±1σ, 20번에 19번쯤이 ±2σ 안에 든다는 뜻입니다.
  • 상수 1.04와 전환 임계 2.5m은 Flajolet 외(2007)의 HyperLogLog 원 논문 값입니다. 구글의 HyperLogLog++는 편향보정표와 64비트 해시로 작은 개수 구간을 더 개선했으므로 실제 구현의 오차는 조금 다를 수 있습니다.
  • 정확히 셀 때의 메모리는 항목당 8바이트(64비트 해시만 담는 최소치)로 잡은 값입니다. 실제 해시셋은 포인터와 빈 칸까지 있어 두세 배 더 듭니다 — 절약 배수는 보수적으로 본 값입니다.
  • 레지스터가 6비트인 것은 64비트 해시를 전제로 합니다. 32비트 해시를 쓰면 5비트로 충분한 대신 고유값이 수억을 넘을 때 해시 충돌로 값이 주저앉습니다.
  • HyperLogLog는 두 집합의 합집합 개수를 레지스터마다 최댓값을 취하는 것만으로 구할 수 있습니다. 반면 교집합은 포함배제로만 되고 오차가 크게 불어나므로 권하지 않습니다.

함께 보면 좋은 도구

블룸 필터원소 수와 목표 오탐률을 넣으면 필요한 비트 배열 크기와 해시 함수 개수를 계산합니다.카운트민 스케치허용 오차 ε와 실패확률 δ를 넣으면 카운트-민 스케치의 폭·깊이와 메모리를 계산합니다.ID 충돌 확률UUID·nanoid 같은 랜덤 ID를 몇 개까지 만들어도 안전한지 생일 문제로 계산합니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.

마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.