HyperLogLog 與基數估計

基數 (Cardinality) 指的是一個集合中不同元素的數量。例如：今天訪問網站的不同 IP 數。

傳統做法是用 HashSet 儲存所有 IP，但如果有 1000 萬個不同 IP，HashSet 需要數 GB 的記憶體。

HyperLogLog (HLL) 可以在只使用 1-2 KB 記憶體的情況下，以 2% 以下的誤差估計基數。

實作 HyperLogLog

import math
import mmh3
from bitarray import bitarray

class HyperLogLog:
    def __init__(self, b=10):
        """
        b: 精度參數（建議 10-16）
        記憶體使用量 = 2^b bytes
        b=10 → 1 KB, 誤差 ~3.25%
        b=14 → 16 KB, 誤差 ~0.81%
        """
        self.b = b
        self.m = 1 << b  # 暫存器數量
        self.registers = [0] * self.m
        self.alpha = self._get_alpha()
    
    def _get_alpha(self):
        """計算修正係數"""
        if self.m == 16:
            return 0.673
        elif self.m == 32:
            return 0.697
        elif self.m == 64:
            return 0.709
        else:
            return 0.7213 / (1 + 1.079 / self.m)
    
    def _hash(self, item):
        """計算 32-bit hash"""
        return mmh3.hash(str(item)) & 0xFFFFFFFF
    
    def _count_leading_zeros(self, x):
        """計算前導零的數量"""
        if x == 0:
            return 32
        return (x.bit_length() ^ 31) + 1
    
    def add(self, item):
        """加入元素"""
        x = self._hash(item)
        # 前 b 個 bit 決定暫存器索引
        idx = x & (self.m - 1)
        # 剩餘 bit 計算前導零
        w = x >> self.b
        self.registers[idx] = max(
            self.registers[idx],
            self._count_leading_zeros(w) + 1
        )
    
    def count(self):
        """估計基數"""
        # 調和平均數
        sum_inv = sum(2.0 ** -r for r in self.registers)
        estimate = self.alpha * self.m * self.m / sum_inv
        
        # 小範圍修正
        if estimate <= 2.5 * self.m:
            # 很多暫存器還是 0
            zeros = self.registers.count(0)
            if zeros:
                estimate = self.m * math.log(self.m / zeros)
        
        # 大範圍修正
        elif estimate > (1 << 32) / 30:
            estimate = -(1 << 32) * math.log(1 - estimate / (1 << 32))
        
        return int(estimate)

# 測試
hll = HyperLogLog(b=14)  # 16 KB
print(f"暫存器數量: {hll.m}")
print(f"記憶體使用: {hll.m} bytes ~ {hll.m/1024:.1f} KB")

# 加入 100 萬個不同的元素
for i in range(1000000):
    hll.add(f"user_{i}_session_{i*2}")

print(f"\n估計基數: {hll.count():,}")
print(f"實際基數: 1,000,000")
print(f"誤差率: {abs(hll.count() - 1000000) / 1000000:.4%}")

使用情境

• 網站 UV 統計：每天數億次訪問，只需 16 KB 就能即時統計
• 資料庫 Query 最佳化：預估 SELECT DISTINCT 的結果數量
• 網路流量監控：統計不同 IP 的連線數
• 爬蟲去重：快速判斷 URL 是否已爬過