2
\$\begingroup\$

I wrote a 2-opt algorithm to be used in a program and noticed (using profile) that the 2-opt is eating up a lot of time. I have tried a few things to make it run faster, but I am out of ideas. Any tips on making it run faster, or a better way to write a 2-opt algo?

def twoOpt(self):
    '''Peforms 2-opt search to improve route'''
    for index, route in enumerate(self.routes):
        for element in xrange(len(route.fields)):
            i = element + 1
            k = i + 1
            while k <= len(route.fields):
                newRoute = Route(route.scout)
                for field in self.twoOptSwap(route.fields, i, k):
                    newRoute.addField(field)
                newRoute.calcRouteCost()
                if newRoute.cost < route.cost:
                    self.routes[index] = newRoute
                k += 1

def twoOptSwap(self, fields, i, k):
    start = fields[0:i]
    middle = fields[i:k]
    middle = middle[::-1]
    end = fields[k:]
    newFields = start + middle + end
    return newFields

Each route object contains a list of fields (route.fields) and route.calcRouteCost() sets route.cost with a value.

\$\endgroup\$

closed as off-topic by t3chb0t, Toby Speight, Mast, IEatBagels, Gareth Rees Oct 16 '18 at 21:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – t3chb0t, Toby Speight, Mast, IEatBagels, Gareth Rees
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    \$\begingroup\$ These appear to be two methods of a class. Could you include the whole class? Also show an example what the input data structure and the output look like. \$\endgroup\$ – 200_success Dec 10 '14 at 19:31
3
\$\begingroup\$
  • A slice of a list is a new list, so this code constructs five lists:

    start = fields[0:i]
    middle = fields[i:k]
    middle = middle[::-1]
    end = fields[k:]
    newFields = start + middle + end
    

    This is probably faster:

    newFields = fields[:]
    newFields[i:k] = fields[k-1:i-1:-1]
    
  • Instead of adding fields one by one in the code below, you could change Route to accept the list of fields in the constructor.

    newRoute = Route(route.scout)
    for field in self.twoOptSwap(route.fields, i, k):
        newRoute.addField(field)  
    

    Note also that after reversing a segment of the route, a complete recalculation of cost is not necessary. You only need to consider how the cost changes where the segments join, assuming cost does not depend on direction of travel.

  • Instead of

    for element in xrange(len(route.fields)):
        i = element + 1
    

    simply

    for i in xrange(1, len(route.fields) + 1):
    
  • Instead of a while loop

    k = i + 1
    while k <= len(route.fields):
        ...
        k += 1      
    

    a for loop

    for k in xrange(i + 1, len(route.fields) + 1):
    
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.