from random import random
from math import log, ceil
class Node(object):
__slots__ = 'value', 'next', 'width'
def __init__(self, value, next, width):
self.value, self.next, self.width = value, next, width
class End(object):
'Sentinel object that always compares greater than another object'
def __cmp__(self, other):
return 1
NIL = Node(End(), [], []) # Singleton terminator node
class IndexableSkiplist:
'Sorted collection supporting O(lg n) insertion, removal, and lookup by rank.'
def __init__(self, expected_size=100):
self.size = 0
self.maxlevels = int(1 + log(expected_size, 2))
self.head = Node('HEAD', [NIL]*self.maxlevels, [1]*self.maxlevels)
def __len__(self):
return self.size
def __getitem__(self, i):
node = self.head
i += 1
for level in reversed(range(self.maxlevels)):
while node.width[level] <= i:
i -= node.width[level]
node = node.next[level]
return node.value
def insert(self, value):
# find first node on each level where node.next[levels].value > value
chain = [None] * self.maxlevels
steps_at_level = [0] * self.maxlevels
node = self.head
for level in reversed(range(self.maxlevels)):
while node.next[level].value <= value:
steps_at_level[level] += node.width[level]
node = node.next[level]
chain[level] = node
# insert a link to the newnode at each level
d = min(self.maxlevels, 1 - int(log(random(), 2.0)))
newnode = Node(value, [None]*d, [None]*d)
steps = 0
for level in range(d):
prevnode = chain[level]
newnode.next[level] = prevnode.next[level]
prevnode.next[level] = newnode
newnode.width[level] = prevnode.width[level] - steps
prevnode.width[level] = steps + 1
steps += steps_at_level[level]
for level in range(d, self.maxlevels):
chain[level].width[level] += 1
self.size += 1
def remove(self, value):
# find first node on each level where node.next[levels].value >= value
chain = [None] * self.maxlevels
node = self.head
for level in reversed(range(self.maxlevels)):
while node.next[level].value < value:
node = node.next[level]
chain[level] = node
if value != chain[0].next[0].value:
raise KeyError('Not Found')
# remove one link at each level
d = len(chain[0].next[0].next)
for level in range(d):
prevnode = chain[level]
prevnode.width[level] += prevnode.next[level].width[level] - 1
prevnode.next[level] = prevnode.next[level].next[level]
for level in range(d, self.maxlevels):
chain[level].width[level] -= 1
self.size -= 1
def __iter__(self):
'Iterate over values in sorted order'
node = self.head.next[0]
while node is not NIL:
yield node.value
node = node.next[0]
from collections import deque
from itertools import islice
class RunningMedian:
'Fast running median with O(lg n) updates where n is the window size'
def __init__(self, n, iterable):
self.it = iter(iterable)
self.queue = deque(islice(self.it, n))
self.skiplist = IndexableSkiplist(n)
for elem in self.queue:
self.skiplist.insert(elem)
def __iter__(self):
queue = self.queue
skiplist = self.skiplist
midpoint = len(queue) // 2
yield skiplist[midpoint]
for newelem in self.it:
oldelem = queue.popleft()
skiplist.remove(oldelem)
queue.append(newelem)
skiplist.insert(newelem)
yield skiplist[midpoint]
if __name__ == '__main__':
#########################################################################
# Demonstrate the RunningMedian() class
# Compare results to alternative class implemented using a regular list
from bisect import insort
from random import randrange
class RunningMedianSlow:
'Slow running-median with O(n) updates where n is the window size'
def __init__(self, n, iterable):
self.it = iter(iterable)
self.queue = deque(islice(self.it, n))
self.sortedlist = sorted(self.queue)
def __iter__(self):
queue = self.queue
sortedlist = self.sortedlist
midpoint = len(queue) // 2
yield sortedlist[midpoint]
for newelem in self.it:
oldelem = queue.popleft()
sortedlist.remove(oldelem)
queue.append(newelem)
insort(sortedlist, newelem)
yield sortedlist[midpoint]
M, N, window = 5000, 8000, 1001
data = [randrange(M) for i in range(N)]
result = list(RunningMedian(window, data))
expected = list(RunningMedianSlow(window, data))
assert result == expected
print 'Successful test of RunningMedian() with', N,
print 'items and a window of size', window, '\n'
#########################################################################
# Demonstrate and test the IndexableSkiplist() collection class
from random import shuffle
demo = list('FOURSQUARE')
excluded = list('XZ')
print 'Building an indexable skiplist containing %r:' % ''.join(demo)
s = IndexableSkiplist(len(demo)) # exercise __init__()
shuffle(demo)
for char in demo:
s.insert(char) # check insert()
print 'Adding: ', char, list(s), len(s)
for char in excluded:
print 'Attempting to remove:', char, '-->',
try:
s.remove(char) # check remove() item not in skiplist
except KeyError:
print 'Successfully not found'
assert len(s) == len(demo) # check __len__()
assert list(s) == sorted(demo) # check __iter__()
assert [s[i] for i in range(len(s))] == sorted(demo) # check __getitem__()
shuffle(demo)
for char in demo:
s.remove(char) # check remove() item in skiplist
print 'Removing: ', char, list(s), len(s)
assert list(s) == [] and len(s) == 0
#############################################################################
# Show the IndexableSkiplist's internal structure and describe its invariants
def iter_levels(skiplist, level):
'Iterate through nodes on a given level.'
node = skiplist.head
while node is not NIL:
yield node
node = node.next[level]
demo = list('HOPSCOTCH') # create a sample skiplist
s = IndexableSkiplist(len(demo))
for char in demo:
s.insert(char)
print '\nStructure of an indexable skiplist containing %r:' % ''.join(demo)
for i in reversed(range(s.maxlevels)): # show the link structure on each level
print 'Level %d: ' % i,
line = ''
for n in iter_levels(s, i):
line += '%s%d %s' % (n.value, n.width[i], ' ' * (n.width[i] - 1))
print line + 'NIL'
print '\nNote the following structure invariants:'
print '* Level 0 has widths all equal to one.'
print '* The sum of widths on each level == len(skiplist)+1.'
print '* Entries on higher levels are subsets of the lower levels.'
print '* Widths of entries on higer levels sum to the widths below.'
print ' For example, a P --> T link of two steps on one level'
print ' corresponds to P --> S --> T links of one step each on level 0.'
