Skip to content

Instantly share code, notes, and snippets.

@aojea
Created October 7, 2017 16:22
Show Gist options
  • Save aojea/7a6330cbc6227a36abdf6d2ad1745200 to your computer and use it in GitHub Desktop.
Save aojea/7a6330cbc6227a36abdf6d2ad1745200 to your computer and use it in GitHub Desktop.
Data structure for topN
class topN():
""" Implements an efficient data structure to return the top N elements
It increments the elements passed as parameter
"""
def __init__(self, N=10):
self.list = {}
self.N = N
self.topN = []
def add(self, key):
if key in self.list:
self.list[key] += 1
else:
self.list[key] = 1
self._updateTop(key)
return
def top(self):
return self.topN
def _updateTop(self, key):
if key in self.topN:
for i in range(len(self.topN)):
if self.list[key] > self.list[self.topN[i]]:
posKey = self.topN.index(key)
self.topN[posKey], self.topN[i] = self.topN[i], self.topN[posKey]
break
else:
if len(self.topN) < self.N:
self.topN.append(key)
elif self.list[key] > self.list[self.topN[-1]]:
self.topN[-1] = key
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment