Traffic하고 Configuration을 각각 2차원 행렬로 표현했다. Traffic은 ( origin, destination )에 따른 traffic양이고, Configuration은 origin에서 destination 까지 떨어진 거리를 저장한 행렬이다. 전체 트래픽은 행렬에서 같은 위치에 있는 원소끼리 곱하도록 되어있다. 입출력 부분은 제외하고 전체 트래픽 구하는 기능까지만 구현했다.
매우 데이터에 의존적인 프로그램이라는 생각이 든다. 만약 석천이형 생각대로 요구사항이 바뀐다면 지금 프로그램은 감당해낼 수 있을까?
리팩토링 할 것.
현재 요구사항에 맞추더라도 행렬에 해당하는 기능을 정리하고, 트래픽이나 거리 계산에는 행렬을 이용하는 식이 되어야 할 것이다. 지금처럼 상속받을 까닭이 없다.
행렬 곱셈 연산을 정의하면 이를 이용하기 위해서는 트래픽이나 거리 행렬 중 어느 한 쪽은 전치행렬이 되어야 한다. 그러려면 전치 행렬 연산도 있어야겠다.
거리를 계산하는 더 좋은 알고리즘이 있을까? 지금은 O(num of city^2).
행렬 곱셈 연산을 정의하면 이를 이용하기 위해서는 트래픽이나 거리 행렬 중 어느 한 쪽은 전치행렬이 되어야 한다. 그러려면 전치 행렬 연산도 있어야겠다.
거리를 계산하는 더 좋은 알고리즘이 있을까? 지금은 O(num of city^2).
~cpp
#1h 48m
import unittest
class Matrix:
def __init__(self, numofGates):
self.matrix = []
for i in range( numofGates ):
self.matrix.append([0]*numofGates)
def getElement( self, origin, destination ):
return self.matrix[origin-1][destination-1]
class DistanceMatrix(Matrix):
def __init__(self, numofGates):
Matrix.__init__(self, numofGates)
def construct( self, origins, destinations ):
for o in origins:
for d in destinations:
self.matrix[o-1][d-1] = abs( origins.index(o)
- destinations.index(d) ) + 1
def getDistance( self, origin, destination ):
return self.getElement( origin, destination )
class TrafficMatrix(Matrix):
def __init__(self, numofGates):
Matrix.__init__(self, numofGates)
def construct( self, origin, traffics ):
for traffic in traffics:
self.matrix[origin-1][traffic.destination-1] = traffic.load
def getLoad( self, origin, destination ):
return self.getElement( origin, destination )
class Traffic:
def __init__(self, destination, load):
self.destination = destination
self.load = load
def total( traffic, distance ):
result = 0
for origin in range( 1, MAX+1 ):
for dest in range( 1, MAX+1 ):
result += distance.getDistance(origin, dest)\
* traffic.getLoad(origin, dest)
return result
MAX = 25
class TestDistance(unittest.TestCase):
def setUp(self):
self.distMatrix = DistanceMatrix(MAX)
self.traffic = TrafficMatrix(MAX)
def testOneToOneDistance(self):
self.distMatrix.construct( origins = range(1,MAX+1),
destinations= range(1,MAX+1) )
for i in range( 1, MAX+1 ):
self.assertEquals( 1, self.distMatrix.getDistance(i, i) )
def testReversalDistance(self):
self.distMatrix.construct( origins = range(1,MAX+1),
destinations= range(MAX,0,-1) )
self.assertEquals( 1, self.distMatrix.getDistance( 1, MAX ) )
self.assertEquals( MAX, self.distMatrix.getDistance( 1, 1 ) )
self.assertEquals( 1, self.distMatrix.getDistance( MAX/2+1,# middle
MAX/2+1 ) )
def testTraffic(self):
self.traffic.construct( origin = 1,
traffics = [Traffic(1,100),
Traffic(2,50)] )
self.assertEquals( 100, self.traffic.getLoad( origin = 1,
destination= 1 ) )
self.assertEquals( 50, self.traffic.getLoad( origin = 1,
destination= 2 ) )
def testTotal(self):
self.traffic.construct( origin = 1,
traffics = [Traffic(2,100)])
self.traffic.construct( origin = 2,
traffics = [Traffic(1,200)])
self.distMatrix.construct( origins = [1,2],
destinations = [1,2] )
self.assertEquals( 600, total( self.traffic, self.distMatrix ) )
self.distMatrix.construct( origins = [1,2],
destinations = [2,1] )
self.assertEquals( 300, total( self.traffic, self.distMatrix ) )
def testReal(self):
self.traffic.construct( origin = 1,
traffics = [Traffic(2,10), Traffic(3,15)])
self.traffic.construct( origin = 2,
traffics = [Traffic(3,10)])
self.traffic.construct( origin = 3,
traffics = [Traffic(1,12), Traffic(2,20)])
self.distMatrix.construct( origins = [1,2,3],
destinations = [2,3,1] )
self.assertEquals( 122, total( self.traffic, self.distMatrix ) )
self.distMatrix.construct( origins = [2,3,1],
destinations = [3,2,1] )
self.assertEquals( 119, total( self.traffic, self.distMatrix ) )
if __name__ == "__main__":
unittest.main()
