Performance Optimization Under Resource Constraints Questions

import hashlib
import math

class CountMinSketch:
    def __init__(self, width: int, depth: int):
        """
        Initialize Count-Min Sketch.
        width: number of columns per row (w)
        depth: number of hash functions / rows (d)

        Error bounds (probabilistic):
        If w = ceil(e / ε) and d = ceil(ln(1/δ)),
        then with probability >= 1-δ: estimate(item) <= true_count(item) + ε * total_count.
        Space: O(w * d). Update and query: O(d).
        """
        self.w = width
        self.d = depth
        self.tables = [[0] * width for _ in range(depth)]
        self.total = 0
        # use simple different salts as hash functions
        self.salts = [str(i).encode() for i in range(depth)]

    def _hash(self, item, i):
        # deterministic hash combining salt and item bytes
        h = hashlib.sha256(self.salts[i] + b"|" + str(item).encode()).digest()
        return int.from_bytes(h[:8], 'big') % self.w

    def add(self, item, count: int = 1):
        """Add `count` occurrences of item to the sketch."""
        for i in range(self.d):
            idx = self._hash(item, i)
            self.tables[i][idx] += count
        self.total += count

    def estimate(self, item) -> int:
        """Return the estimated count (overestimate or exact)."""
        vals = []
        for i in range(self.d):
            idx = self._hash(item, i)
            vals.append(self.tables[i][idx])
        return min(vals)

# Usage example with width=1000 and depth=5
if __name__ == "__main__":
    cms = CountMinSketch(width=1000, depth=5)
    stream = ["alpha", "beta", "alpha", "gamma", "alpha", "beta"]
    for s in stream:
        cms.add(s)
    print("est alpha:", cms.estimate("alpha"))   # expect 3
    print("est beta:", cms.estimate("beta"))     # expect 2
    print("est gamma:", cms.estimate("gamma"))   # expect 1
    print("total:", cms.total)