Approximate Distinct Count in Python with HyperLogLog

import random
import string
from collections import Counter
import math

class ApproxCountDistinct:
    def __init__(self, num_buckets=16):
        self.num_buckets = num_buckets
        self.max_zeros = [0] * num_buckets
        
    def _hash(self, item):
        # Simple string hash to a 32-bit integer
        h = 0
        for c in item:
            h = (h * 31 + ord(c)) & 0xFFFFFFFF
        return h
    
    def _count_trailing_zeros(self, value):
        if value == 0:
            return 32
        return (value & -value).bit_length() - 1
    
    def add(self, item):
        h = self._hash(item)
        bucket = h % self.num_buckets
        trailing_zeros = self._count_trailing_zeros(h >> (32 // self.num_buckets)) if self.num_buckets <= 32 else 0
        trailing_zeros = self._count_trailing_zeros(h)
        self.max_zeros[bucket] = max(self.max_zeros[bucket], trailing_zeros)
    
    def estimate(self):
        # Harmonic mean-based estimate (HyperLogLog-style)
        alpha = 0.7213 / (1 + 1.079 / self.num_buckets)
        sum_inv = sum(2.0 ** (-mz) for mz in self.max_zeros)
        raw_est = alpha * self.num_buckets ** 2 / sum_inv
        if raw_est <= 2.5 * self.num_buckets:
            V = self.max_zeros.count(0)
            if V > 0:
                raw_est = self.num_buckets * math.log(self.num_buckets / V)
        return raw_est

def demo_approx_distinct():
    # Mock real distinct count vs approximate
    real_items = set()
    approx = ApproxCountDistinct(num_buckets=32)
    
    # Simulate a data stream
    for _ in range(500):
        item = ''.join(random.choices(string.ascii_lowercase, k=8))
        real_items.add(item)
        approx.add(item)
    
    print(f"Real distinct: {len(real_items)}")
    print(f"Estimated distinct: {int(approx.estimate())}")
    print(f"Error: {abs(int(approx.estimate()) - len(real_items)) / len(real_items) * 100:.2f}%")

if __name__ == "__main__":
    demo_approx_distinct()