Summary Quantile Mock Sketch in Python

import random
import statistics
from collections import Counter

class SummaryQuantileSketch:
    """
    A simple sketch that stores a fixed-size summary of data (min, max, deciles)
    using sorted bins, then answers approximate quantile queries.
    """
    def __init__(self, bins=10):
        self.bins = bins
        self.data = []
        self.summary = []

    def update(self, value):
        self.data.append(value)
        # Rebuild summary every 100 updates (mock sketch behavior)
        if len(self.data) % 100 == 0:
            self._build_summary()

    def _build_summary(self):
        if not self.data:
            self.summary = []
            return
        sorted_data = sorted(self.data)
        n = len(sorted_data)
        step = max(1, n // self.bins)
        # Pick representative points at even spacing
        self.summary = [sorted_data[i * step] for i in range(self.bins)]
        # Always include min and max
        self.summary[0] = sorted_data[0]
        self.summary[-1] = sorted_data[-1]

    def quantile(self, q):
        if not self.summary:
            return None
        if q <= 0:
            return self.summary[0]
        if q >= 1:
            return self.summary[-1]
        # Map quantile to index in summary
        idx = q * (len(self.summary) - 1)
        lower = int(idx)
        upper = min(lower + 1, len(self.summary) - 1)
        weight = idx - lower
        return self.summary[lower] * (1 - weight) + self.summary[upper] * weight

    def median(self):
        return self.quantile(0.5)

    def __repr__(self):
        return f"SummaryQuantileSketch(summary={self.summary})"

if __name__ == "__main__":
    random.seed(42)
    sketch = SummaryQuantileSketch(bins=5)

    # Feed 500 random numbers
    for _ in range(500):
        sketch.update(random.uniform(0, 100))

    # Force final summary
    sketch._build_summary()

    print("Summary points:", sketch.summary)
    print("Median (mock):", round(sketch.median(), 2))
    print("75th percentile (mock):", round(sketch.quantile(0.75), 2))
    print("Exact median:", round(statistics.median(sketch.data), 2))