Почему Макс медленнее, чем сортировка?

Я обнаружил, что max работает медленнее, чем функция sort в Python 2 и 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

Почему max (O(n)) медленнее, чем функция sort (O(nlogn))?

Ответ 1

Вы должны быть очень осторожны при использовании модуля timeit в Python.

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

Здесь код инициализации запускается один раз для создания рандомизированного массива a. Затем остальная часть кода выполняется несколько раз. Первый раз он сортирует массив, но каждый раз вы вызываете метод sort на уже отсортированном массиве. Возвращается только самое быстрое время, поэтому вы на самом деле определяете, сколько времени требуется Python для сортировки уже отсортированного массива.

Часть алгоритма сортировки Python заключается в обнаружении, когда массив уже частично или полностью отсортирован. Когда он полностью сортируется, он просто должен сканировать один раз через массив, чтобы обнаружить это, а затем он останавливается.

Если вместо этого вы попытались:

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

то сортировка происходит в каждом цикле синхронизации, и вы можете видеть, что время для сортировки массива действительно намного длиннее, чем просто найти максимальное значение.

Изменить: @skyking answer объясняет ту часть, которую я оставил необъяснимой: a.sort() знает, что она работает над списком, поэтому можно напрямую получить доступ элементы. max(a) работает с любым произвольным итерабельным, поэтому он должен использовать общую итерацию.

Ответ 2

Прежде всего, обратите внимание, что max() использует протокол итератора, а list.sort() использует ad-hoc code. Ясно, что использование итератора является важным накладным расходами, поэтому вы наблюдаете эту разницу в таймингах.

Однако, кроме того, ваши тесты несправедливы. Вы используете a.sort() в одном и том же списке более одного раза. Алгоритм используемый Python, специально разработан для быстрой (частично) сортировки данных. В ваших тестах говорится, что алгоритм хорошо выполняет свою работу.

Это честные тесты:

$ 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

Здесь я каждый раз создаю копию списка. Как вы можете видеть, порядок величин результатов различен: микроволны миллисекунд, как и следовало ожидать.

И помните: big-Oh указывает верхнюю границу! Нижняя граница алгоритма сортировки Python равна Ω (n). Будучи O (n log n), автоматически не означает, что каждый пробег занимает время, пропорциональное n log n. Это даже не означает, что он должен быть медленнее, чем алгоритм O (n), но это другая история. Важно понимать, что в некоторых благоприятных случаях алгоритм O (n log n) может выполняться в O (n) времени или меньше.

Ответ 3

Это может быть потому, что l.sort является членом list, а max является общей функцией. Это означает, что l.sort может полагаться на внутреннее представление list, в то время как max должен пройти общий протокол итератора.

Это означает, что каждый элемент fetch для l.sort быстрее, чем каждый выборка элемента, который делает max.

Я предполагаю, что если вы вместо этого используете sorted(a), вы получите результат медленнее, чем max(a).