vendredi 8 mai 2015

python global scope inside if/else, heapq

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