Why is max slower than sort?

Question

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))?

Solution 1

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.

Solution 2

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.

Solution 3

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).

Comments

[Frerich Raabe]

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. :-}

[Karoly Horvath]

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.

[Duncan]

@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.

[marcospereira]

@KarolyHorvath maybe branch prediction can explain why repeatedly sorting a sorted array is faster: stackoverflow.com/a/11227902/4600

[JuniorCompressor]

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?

[Frerich Raabe]

@JuniorCompressor 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.

[Reti43]

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.

[jpmc26]

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.

[Duncan]

@jpmc26, yes I was using sequence colloquially, but I've corrected it.

[martineau]

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.

[skyking]

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).