93

I've found that max is slower than the sort function in Python 2 and 3.

Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

Python 3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

Why is max (O(n)) slower than the sort function (O(nlogn))?

martineau
  • 119,623
  • 25
  • 170
  • 301
WeizhongTu
  • 6,124
  • 4
  • 37
  • 51
  • 10
    `a.sort()` works inplace. Try `sorted(a)` – Andrea Corbellini Jan 26 '16 at 13:35
  • 1
    @AndreaCorbellini but sorted(a) need `O(n)` memory and max(a) needs only one – WeizhongTu Jan 26 '16 at 13:39
  • 3
    @WeizhongTu but `sort` sorts, and then `a` is sorted forever – njzk2 Jan 26 '16 at 17:16
  • Also worth noting: python uses Timsort. This algorithm does `n-1` comparisons on an already sorted list, which is the same number as `max` has to do. In fact Timsort will do O(n) comparisons even when the input is "partially sorted". Other algorithms may require O(nlogn) time even in the sorted case. – Bakuriu Jan 26 '16 at 22:27

3 Answers3

126

You have to be very careful when using the timeit module in Python.

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

Here the initialisation code runs once to produce a randomised array a. Then the rest of the code is run several times. The first time it sorts the array, but every other time you are calling the sort method on an already sorted array. Only the fastest time is returned, so you are actually timing how long it takes Python to sort an already sorted array.

Part of Python's sort algorithm is to detect when the array is already partly or completely sorted. When completely sorted it simply has to scan once through the array to detect this and then it stops.

If instead you tried:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

then the sort happens on every timing loop and you can see that the time for sorting an array is indeed much longer than to just find the maximum value.

Edit: @skyking's answer explains the part I left unexplained: a.sort() knows it is working on a list so can directly access the elements. max(a) works on any arbitrary iterable so has to use generic iteration.

Community
  • 1
  • 1
Duncan
  • 92,073
  • 11
  • 122
  • 156
  • 11
    Good catch. I never realised that the interpreter state is retained across the code runs. Now I wonder how many faulty benchmarks I produced in the past. :-} – Frerich Raabe Jan 26 '16 at 13:42
  • 1
    That much was obvious to me. But notice that even if you sort an already sorted array you have to check all the elements. Which is just as much work as getting the max.... To me this looks like a half-answer. – Karoly Horvath Jan 26 '16 at 13:43
  • 2
    @KarolyHorvath, you are correct. I think @skyking got the other half of the answer: `a.sort()` knows it is working on a list so can directly access the elements. `max(a)` works on an arbitrary sequence to has ot use generic iteration. – Duncan Jan 26 '16 at 13:45
  • 1
    @KarolyHorvath maybe branch prediction can explain why repeatedly sorting a sorted array is faster: http://stackoverflow.com/a/11227902/4600 – marcospereira Jan 26 '16 at 13:45
  • I'm curious why sorting an sorted array is faster than finding the maximum. Finding the maximum is a straightforward list scanning. Determining if an array is sorted needs at least checking each element. Is it because sorting is implemented in c? Or there is a flag that the array is sorted? – JuniorCompressor Jan 26 '16 at 13:47
  • 1
    @JuniorCompressor [`listsort.txt`](http://svn.python.org/projects/python/trunk/Objects/listsort.txt) explains "It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1)" and then goes on to explain all kinds of gory optimizations. I suppose it can make a lot of assumptions which `max` can't, i.e. sorting is not asymptotically faster. – Frerich Raabe Jan 26 '16 at 13:49
  • I think you misused the word "sequence" in the last sentence. Unless I have remembered completely incorrectly, "sequence" refers to something that implements `__getitem__` to accept indices starting with 0 and implements `__len__`. E.g., `tuple` is a sequence and so is `list`. I believe `max` can take any iterable. – jpmc26 Jan 27 '16 at 23:41
  • 1
    @jpmc26, yes I was using sequence colloquially, but I've corrected it. – Duncan Jan 28 '16 at 08:55
87

First off, note that max() uses the iterator protocol, while list.sort() uses ad-hoc code. Clearly, using an iterator is an important overhead, that's why you are observing that difference in timings.

However, apart from that, your tests are not fair. You are running a.sort() on the same list more than once. The algorithm used by Python is specifically designed to be fast for already (partially) sorted data. Your tests are saying that the algorithm is doing its job well.

These are fair tests:

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a[:])'
1000 loops, best of 3: 227 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a[:].sort()'
100 loops, best of 3: 2.28 msec per loop

Here I'm creating a copy of the list every time. As you can see, the order of magnitude of the results are different: micro- vs milliseconds, as we would expect.

And remember: big-Oh specifies an upper bound! The lower bound for Python's sorting algorithm is Ω(n). Being O(n log n) does not automatically imply that every run takes a time proportional to n log n. It does not even imply that it needs to be slower than a O(n) algorithm, but that's another story. What's important to understand is that in some favorable cases, an O(n log n) algorithm may run in O(n) time or less.

Andrea Corbellini
  • 17,339
  • 3
  • 53
  • 69
31

This could be because l.sort is a member of list while max is a generic function. This means that l.sort can rely on the internal representation of list while max will have to go through generic iterator protocol.

This makes that each element fetch for l.sort is faster than each element fetch that max does.

I assume that if you instead use sorted(a) you will get the result slower than max(a).

skyking
  • 13,817
  • 1
  • 35
  • 57
  • 5
    That assumption is only a one-liner-timing away to becoming more concrete. Not questioning your knowledge, just that such an addition is trivial for the demonstration of those who don't know it. – Reti43 Jan 26 '16 at 15:54
  • You're correct that `sorted(a)` is slower than `max(a)`. Not surprisingly It's about the same speed as `a.sort()`, but your conjecture as to the reason why isn't—it's because the OP made a mistake in their testing as pointed out in the accepted answer. – martineau Nov 15 '16 at 21:26
  • The point was that there's a possibility that the generic iterator protocol has enough overhead to offset the `log(n)` factor in the complexity. That is an `O(n)` algorithm is only guaranteed to be faster than an `O(nlogn)` algorithm for sufficiently large `n` (for example because the time for each operation may differ between the algorithms - `nlogn` fast steps may be faster than `n` slow steps). Exactly where the break even is wasn't considered in this case (but one should be aware that the `log n` factor is not a very big factor for smallish `n`). – skyking Nov 16 '16 at 08:31