LoadBalancingProblem ¶
----
~python ##1h 11m import copy class SuperComputer: def __init__(self): self.numOfCPU = 0 self.eachWork = list() self.minWork = 0 self.maxWork = 0 def computeMinMaxWork(self): self.minWork = self.eachWork[0] self.maxWork = self.eachWork[0] for i in range( 1, self.numOfCPU): if self.minWork > self.eachWork[i]: self.minWork = self.eachWork[i] if self.maxWork < self.eachWork[i]: self.maxWork = self.eachWork[i] def isCompelte(self): if self.maxWork - self.minWork > 1: return False return True def input(self, aNumOfCPU, aEachWorks): self.numOfCPU = aNumOfCPU self.eachWork = copy.deepcopy(aEachWorks) self.computeMinMaxWork() def isThisOverWork(self, aID): self.computeMinMaxWork() if self.getWork(aID) > self.minWork: return True return False def shareWork( self, aID ): if aID != 1: self.decreaseWork(aID) self.increaseWork(aID-1) if aID != self.numOfCPU: self.decreaseWork(aID) self.increaseWork(aID+1) def getWork(self, aID): assert 0 < aID <= self.numOfCPU return self.eachWork[aID-1] def decreaseWork(self, aID): assert 0 < aID <= self.numOfCPU self.eachWork[aID-1] = self.eachWork[aID-1] - 1 def increaseWork(self, aID): assert 0 < aID <= self.numOfCPU self.eachWork[aID-1] = self.eachWork[aID-1] + 1 def run(self): round = 0 while not self.isCompelte(): for id in range( 1, self.numOfCPU+1 ): if self.isThisOverWork(id): self.shareWork(id) print self.eachWork round = round + 1 print self.eachWork print "??" print round #################################################################### import unittest class SuperComputerTestCase(unittest.TestCase): def testIsComplete(self): com = SuperComputer() numOfCPU = 3 eachWork = [0,0,0] com.input( numOfCPU, eachWork ) self.assertEqual( com.isCompelte(), True ) numOfCPU = 3 eachWork = [0,99,3] com.input( numOfCPU, eachWork ) self.assertEqual( com.isCompelte(), False ) def testShareWork(self): com = SuperComputer() numOfCPU = 8 eachWork = [16, 17, 15, 0, 20, 1, 1, 2] com.input( numOfCPU, eachWork ) id = 1 com.shareWork( id ) expected = 15 self.assertEqual( com.getWork(id), expected) id = 2 expected = 18 self.assertEqual( com.getWork(id), expected) def testIsThisOverWork(self): com = SuperComputer() numOfCPU = 10 eachWork = [0, 0, 100, 0, 0, 0, 0, 0, 0, 0] com.input( numOfCPU, eachWork ) id = 3 self.assertEqual( com.isThisOverWork(id), True ) id = 1 self.assertEqual( com.isThisOverWork(id), False ) def testRun(self): com = SuperComputer() numOfCPU = 10 eachWork = [0, 0, 100, 0, 0, 0, 0, 0, 0, 0] com.input( numOfCPU, eachWork ) com.run() if __name__ == '__main__': unittest.main()