2 Replies - 319 Views - Last Post: 07 January 2013 - 03:45 PM Rate Topic: -----

#1 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,689
  • Joined: 13-March 10

Refactoring the method.

Posted 04 January 2013 - 12:32 PM

I am solving the Travelling Salesman Problem. I have a cost matrix and i want to find the cost of a tour.
Method i have written works but my question is whether it is written in a Pythonic style. Any suggestions to improve the style are welcome.

def findTourCost(self, tour):
        total = 0
        for index, value in enumerate(tour):
            if index == len(tour) - 1:
                total = total + self.costMatrix[value][tour[0]]
                break
            
            total = total + self.costMatrix[value][tour[index + 1]]
    
        return total



Is This A Good Question/Topic? 0
  • +

Replies To: Refactoring the method.

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Refactoring the method.

Posted 04 January 2013 - 01:16 PM

This looks fine, but there's two things I would do differently if it was me:

total = total + self.costMatrix[value][tour[0]]
total = total + self.costMatrix[value][tour[index + 1]]



These two lines are the same except for the second index. To get rid of this duplication, I'd simply put the second index in a variable nextIndex that's set in an if and then use that variable outside the if. I'd also consider introducing another variable nextValue just to shorten the line a bit (and achieve some symmetry with value and nextValue). Like this:

if index == len(tour) - 1:
    nextIndex = 0
else:
    nextIndex = index + 1

nextValue = tour[nextIndex]
total = total + self.costMatrix[value][nextValue]



This also gets rid of the break.

The second thing I might change is that I'd use sum to do the summing rather than a for loop. For this I'd first put the logic to find an edge's weight into its own function and then use that function with sum. Like this:

def findTourCost(self, tour):
    def edgeWeight(node, index):
        """
        Given a node of the tour and the index of that node,
        return the weight between the node and its successor
        in the tour.
        Note that the successor of the tour's last node is the
        tour's first node.
        """

        if index == len(tour) - 1:
            nextIndex = 0
        else:
            nextIndex = index + 1

        nextValue = tour[nextIndex]
        return self.costMatrix[value][nextValue]

    return sum(edgeWeight(value, index) for value, index in enumerate(tour))



On second thought it seems a bit asymmetrical that we get the value of the current node from enumerate, but access the next one by index. So maybe I would get rid of enumerate in this case and use range instead - this will also makes the last line a bit shorter since edgeWeight only needs to take on argument this way:

def findTourCost(self, tour):
    def edgeWeight(index):
        """
        Given the index of a node in the tour, return the weight between
        the node and its successor
        Note that the successor of the tour's last node is the tour's
        first node.
        """

        if index == len(tour) - 1:
            nextIndex = 0
        else:
            nextIndex = index + 1

        value = tour[index]
        nextValue = tour[nextIndex]
        return self.costMatrix[value][nextValue]

    return sum(edgeWeight(index) for index in range(len(tour)))


Was This Post Helpful? 3
  • +
  • -

#3 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Refactoring the method.

Posted 07 January 2013 - 03:45 PM

I would probably have written the findTourCost method like this:
def findTourCost(self, tour):
    origin_target = zip(tour[:-1], tour[1:])
    total = sum(self.costMatrix[origin][target]
                for origin, target in origin_target)
    #go back to the start
    total += self.costMatrix[tour[-1]][tour[0]]
    return total


Probably, because in Python 2.x I may have avoided the zip. In Python 3.x zip is evaluated lazily but in Python 2.x it creates a list of tuples in memory.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1