Lets have a little style review, before some code refactoring, and finish off with some performance comparison.
Style and code review
I suggest you read up on PEP8, which is the official style guide for Python.
- Not using
snake_case for variable and function names - You are using mostly camelCase, and in some cases one letter variables
- Good use of singular vs plural – I like combinations like
for route in routes. They make sense
- Good use of
if __name__ ... - This is good construct
- Many temporary variables – You have a little too many temporary variables, which are only used once. These can often be skipped
- Avoid using indexes in loops – In general, it is better to avoid using indexes in loops, rather than looping on the elements themself. Especially bad is it when you use
str(i) to get the index, when the Nodes list should have used pure integers directly as keys.
- Avoid building large lists in memory – Your code builds the
routes list in memory. When calling this for a route length of 9, your original code uses approx 6.7MB to store the routes. My optimised routine below, uses 0.02MB because it uses generators instead...
- Avoid recalculating distances – Python can memoize the output from a function for each given input by using decorators. This means that you can calculate the distance between two points once, and the next time you need it the memoize function picks your previous calculation of the result.
- Use docstrings instead of ordinary comment to document functions – If you use docstrings, some of the editors will provide interactive help when you use your functions, and it is according the style guide.
Performance comparison
I made some variants of the code, both of your original, the one by SuperBiasedMan (with some correction as his code currently has a bug), some versions using only generators, itertools, sum and min, and finally a version using for loops instead of list comprehension and a slightly alternate optimisation to find the minimum.
I used the following version of memoize, which most likely can be further optimised:
def memoize(f):
""" Memoization decorator for functions taking one or more arguments. """
class memodict(dict):
def __init__(self, f):
self.f = f
def __call__(self, *args):
return self[args]
def __missing__(self, key):
ret = self[key] = self.f(*key)
return ret
return memodict(f)
@memoize
def distance(p1, p2):
"""Calculates distance between two points, memoizes result"""
d = (((p2[0] - p1[0])**2) + ((p2[1] - p1[1])**2)) **.5
return int(d)
One version taking it to the extreme regarding list comprehension and generators are this one:
def route_generator(route_length):
"""Generate all possible routes of length route_length, starting at 1."""
for route in permutations(xrange(2, route_length+1)):
yield (1, ) + route
def main_holroy_v2(instance_size=INSTANCE_SIZE):
print min((sum(distance(NODES[start], NODES[stop])
for start, stop in pairwise(route)), route)
for route in route_generator(instance_size))
I made the Nodes into a global dict with integers as key, named NODES. After some testing I found that the extreme variant was slower than expected, so I fumbled around and found this to be the fastest in my environment:
def find_shortest_route3(nodes, route_length):
"""Find shortest route of length route_length from nodes."""
minimum_distance = None
for route in permutations(xrange(2, route_length+1)):
current_distance = 0
prev = nodes[1]
for next in route:
current_distance += distance(prev, nodes[next])
prev = nodes[next]
if minimum_distance and current_distance > minimum_distance:
break
else:
if not minimum_distance or current_distance < minimum_distance:
minimum_distance = current_distance
minimum_route = route
return minimum_distance, minimum_route
def main_minimum3(instance_size=INSTANCE_SIZE):
distance.clear()
cost, route = find_shortest_route3(NODES, instance_size)
print('Shortest route: {}'.format((1, ) + route))
print('Travel cost : {}'.format(cost))
Some comments on this code:
- It turns out that list comprehensions are slightly slower than plain for loops in this case
- Instead of completing the sum for a route, I break out of the inner loop if the sum has crossed an earlier minimum. The current route is then not interesting any more
- The actual route returned does not include the starting point. This can easily be added, as done in the
print statement. This eliminates the need for either adding in the starting point to all routes, or to remove all routes not starting at the correct point. In short, it is more efficient
- If the inner
for loop completes ordinarily (no breaks), then it goes into the else block of the for loop. A slightly strange construct, but for this purpose ideal, as we then can compare the minimum distance versus the current route distance
- The
distance.clear() is used to reset the memoisation between test run done using timeit in IPython. Memory profiling was done using a module name memory_profiler.
Here are some of the timing results I got:
In [325]: %timeit main_org_str(9) # Your original code
1 loops, best of 3: 529 ms per loop
In [326]: %timeit main_org(9) # Using int as keys
1 loops, best of 3: 304 ms per loop
In [327]: %timeit main_holroy_v2(9)
1 loops, best of 3: 420 ms per loop
In [328]: %timeit main_superbiasedman(9)
1 loops, best of 3: 362 ms per loop
In [330]: %timeit main_minimum3(9)
10 loops, best of 3: 146 ms per loop
In [330]: %timeit main_minimum3(9) # After removing `**0.5`
10 loops, best of 3: 116 ms per loop
As can be seen here your original version took around 0.5 seconds, but only changing into using ints as keys and memoisation, shaved off 0.2 seconds. My extreme version and version by SuperBiasedMan, actually uses longer time than your version when optimised. But still the fastest version is the minimum3 version, clocking in at 146 milliseconds. (The last number, 116 ms, comes if you remove the **0.5 in distance(). Taking the square root is somewhat expensive.)
So there you have it, your code is not too bad timewize, but it used way too much memory. When coding according to the most pythonic ways, using generators, list comprehensions and sum and min you lower the memory consumption, changes the readability, but don't always gain that much in reduced time.
Of the alternatives I tested, the optimal combination for a brute force approach runs in approximately 30% of the time, and uses almost none memory. Some other timings for my optimal method: (10: 1.26 seconds, 11: 11.7 seconds, 12: 1 min 54 seconds). So better algorithms should be applied if wanting to calculate the shortest route for routes longer than 11/12 nodes.
