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

я нашел это 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)) медленнее, чем (O(nlogn))?

3 90
python python-internals sorting max

3 ответа:

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

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

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

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

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

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

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

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

123

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

однако, кроме того, ваши тесты не являются справедливыми. Вы используете 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

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

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

88

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

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

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

31