# SpaceSaving frequent item counter in Python

In the code below, I implemented the SpaceSaving frequency estimation algorithm described in this paper. Given a parameter eps, the algorithm finds all elements of a data stream of length n that occur more than n/eps times (with high probability). Here's a screenshot from the paper with the pseudocode: I would appreciate any feedback on my implementation: style, performance, etc.

import math, heapq

class SpaceSavingCounter:
def __init__(self, eps):
self.k = math.ceil(1/eps)
self.n = 0
self.counts = dict()
self.queue = []

def inc(self, x):
# increment total elements seen
self.n += 1

# x is being watched
if x in self.counts:
self.counts[x] += 1

# x is not being watched
else:
# make room for x
if self.n > self.k:
while True:
count, tstamp, key = self.pop()
assert self.counts[key] >= count
if self.counts[key] == count:
del self.counts[key]
break
else:
self.push(self.counts[key], tstamp, key)
else:
count = 0

# watch x
self.counts[x] = count + 1
self.push(count, self.n, x)

def push(self, count, tstamp, key):
heapq.heappush(
self.queue,
(count, tstamp, key)
)

def pop(self):
return heapq.heappop(self.queue)

def test_SpaceSavingCounter():
seq = [1,5,3,4,2,7,7,1,3,1,3,1,3,1,3]
counter = SpaceSavingCounter(1 / 1.9)
for x in seq:
counter.inc(x)
assert counter.counts.keys() == {1,3}

• It's fine if you're just implementing this for fun/school/practice, but if you're in Python 3+ (based on your tag), why not just use functools.lru_cache? It's not identical (and maybe that's the reason), but in many cases it serves the same purpose, and it's built-in (aka, fast and reliable) – scnerd Oct 8 '18 at 15:17