I'm implementing a running median algorithm in Python using two heaps. However, the heaps doesn't grow in size even if I push to it...
I suspect it's something to do with the scoping inside if/else statements. I don't really understand how to fix this.
import os
import numpy
import functools
import heapq
from heapq import heapify, heappush, heappop
@functools.total_ordering
class ReverseCompare(object):
def __init__(self, obj):
self.obj = obj
def __eq__(self, other):
return isinstance(other, ReverseCompare) and self.obj == other.obj
def __le__(self, other):
return isinstance(other, ReverseCompare) and self.obj >= other.obj
def __str__(self):
return str(self.obj)
def __repr__(self):
return '%s(%r)' % (self.__class__.__name__, self.obj)
curMedian = 0
leftHeap = map(ReverseCompare, [])
rightHeap = []
heapq.heapify(rightHeap)
heapq.heapify(leftHeap)
def runningMed(n):
#importing the global variables
global curMedian
global leftHeap
global rightHeap
#The first time
if (curMedian == 0):
curMedian = n
return curMedian
#the second +... time
# print "debug"
# print rightHeap
# print leftHeap
# heapq.heappush(leftHeap, 3)
# heapq.heappush(rightHeap, 3)
# print rightHeap
print "length of heaps"
print len(rightHeap)
print len(leftHeap)
if (len(rightHeap) > len(leftHeap) + 2):
print "Debug long right heap"
if(n >= curMedian):
heapq.heappush(leftHeap, curMedian)
curMedian = heapq.heappop(rightHeap)
heappop.heappush(rightHeap, n)
else:
heapq.heappush(leftHeap, n)
elif (len(leftHeap) > len(rightHeap) + 2):
print "Debug long"
if(n <= curMedian):
heapq.heappush(rightHeap, curMedian)
curMedian = heapq.heappop(leftHeap)
heappop.heappush(leftHeap, n)
else:
heapq.heappush(rightHeap,n)
else:
print "Debug curMedian"
print n
print curMedian
if (n > curMedian):
heapq.heappush(rightHeap, n)
else:
heapq.heappush(leftHeap,n)
#TReturn the median:
if (len(leftHeap) == len(rightHeap)):
return curMedian
elif (len(leftHeap) > len(rightHeap)):
return (heapq.heappop(leftHeap) + curMedian)/2
else:
return (heapq.heappop(rightHeap) + curMedian)/2
if __name__ == "__main__":
#TODO: Input/output names must be changed
inputFile = open('numbers.txt', 'r')
outputFile = open('output.txt', 'w')
for line in inputFile:
num = int(line.rstrip('\n'))
med = runningMed(num)
outputFile.write(str(med) + '\n')
inputFile.close()
outputFile.close()
Aucun commentaire:
Enregistrer un commentaire