luizfelipe - 1 year ago 65

Python Question

I'm learning python and I've implemented a quicksort algorithm (kind of). I do know that python's sort() method would be faster but I wanted to know by how much, so I've used the timeit module for comparison.

I created a 'wrapper' function for the sort() method so it works with the same syntax as my implementation (and stops being an in-place sort) and called

`timeit.repeat(3, 2000)`

Here are the results for my function:

`[0.00019502639770507812, 0.00037097930908203125, 0.00013303756713867188]`

And for python's sort():

`[0.0001671314239501953, 0.0001678466796875, 0.00016808509826660156]`

As you can see, python's algorithm has execution times much more consistent than my own's. Does anyone know why?

`import timeit`

import random

def quick(lst):

if not lst:

return []

else:

first, rest = lst[0], lst[1:]

great = []

less = []

for item in rest:

great.append(item) if item >= first else less.append(item)

return quick(less) + [first] + quick(great)

def sort(lst):

lst.sort()

return lst

x = [random.randint(1, 10000) for i in xrange(1, 1000)]

quick_t = timeit.Timer("'quick(x)'")

print quick_t.repeat(3, 2000)

sort_t = timeit.Timer("'sort(x)'")

print sort_t.repeat(3, 2000)

Answer Source

Your timing is horribly wrong in multiple ways. First, your `sort`

wrapper still mutates its input instead of returning a new list:

```
>>> x = [2, 1]
>>> sort(x)
[1, 2]
>>> x
[1, 2]
```

Second, you're not timing either sort at all. You're timing the evaluation of the string literal `'quick(x)'`

or `'sort(x)'`

. No sorting actually takes place.

Here's how you'd *actually* perform the timing:

```
>>> x = [random.randint(1, 10000) for i in xrange(1, 1000)]
>>> print timeit.repeat('quick(x)', 'from __main__ import quick, x', repeat=3, number=500)
[1.1500223235169074, 1.0714474915748724, 1.0657452245240506]
>>> print timeit.repeat('sorted(x)', 'from __main__ import quick, x', repeat=3, number=500)
[0.0944752552401269, 0.10085532031979483, 0.09799135718691332]
```