# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

# Problem: "Compute which (if any) value makes up a majority of the stream, or more generally, the set of items that constitute some fixed fraction of the stream" from wiki
#
# - exact $\phi$-frequent items: return the set $\{i| f_i > \phi n\}$ where $n$ is the length of the stream
# - $\epsilon$-approximate $\phi$-frequent items: return the set $\{i|f_i>(\phi-\epsilon)n\}$ and there is no $j$ not in the set s.t. $f_j>\phi n$
# - frequency estimation problem: for any $i$, an $\hat{f}_i$ is returned satisfying $\hat{f}_i \leq f_i \leq \hat{f}_i + \epsilon n$
#
# Reference:
# - https://en.wikipedia.org/wiki/Misra-Gries_summary
# - https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf
# - http://www.cs.toronto.edu/~bor/2420f17/L11.pdf

# Misra-Gries Summary: Every item which occurs at least $n/k$ times is guaranteed to appear in the output array.
# - solve the frequency estimate problem by setting $k = 1/\epsilon$
# - Every 𝑘-heavy hitter is definitely covered in 𝐴. Although,
# some other elements might be present too. A second pass can be used to eliminate false positives. Cannot solve exact $\phi$-frequent items in a single pass.
#
# To solve $\epsilon$-approximate $\phi$-frequent items in a single pass, use Misra-Gries with $k = 1/\epsilon$. Then return all $v \in A$ s.t. $\hat{f}_i \geq (\phi-\epsilon)m$. 

# +
k = 3
s = [1,1,2,1,3,1,3,2,1,5,1,4,1,3,1,2,3,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
m = max(s) # event type / domain size
n = len(s)

# first pass. Space: O(k(log m + log n)). log m for key. log n for count.
A = {}
for i in s:
  if i in A:
    A[i] += 1 # increment the freq of value i
  elif len(A.keys())< k-1:
    A[i] = 1 # initialize the freq of value i
  else:
    for key in A.keys(): # there are already k values in A
      A[key] -= 1 # decrement the freqency for the k values in A
      if A[key] == 0: # pop infrequent value
        A.pop(key)
# -

print "Output: ", A
print "Frequent items: ", A.keys()

# The time cost depends on the dictionary operations. Possible implementations are:
# - balanced search tree
# - hash table
# - offsets + linked lists

StarcoderdataJupyterScriptsDedupFiltered