Метод sort() Python в списке vs встроенная функция sorted()
Я знаю, что функция __builtin__
sorted() работает на любом итерабельном. Но может ли кто-нибудь объяснить эту огромную (10x) разницу в производительности между anylist.sort() и отсортированным (anylist)? Также, пожалуйста, укажите, что я делаю что-то неправильно, так как это измеряется.
"""
Example Output:
$ python list_sort_timeit.py
Using sort method: 20.0662879944
Using sorted builin method: 259.009809017
"""
import random
import timeit
print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000)").repeat())
print x
print 'Using sorted builin method:',
x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000)").repeat())
print x
Как говорится в названии, мне было интересно сравнить list.sort() vs sorted (list). Вышеприведенный фрагмент показал что-то интересное, что функция сортировки python ведет себя очень хорошо для уже отсортированных данных. Как уже указывал Anurag, в первом случае метод сортировки работает с уже отсортированными данными, а во второй сортировке он работает над новой частью, чтобы делать работу снова и снова.
Итак, я написал этот тест, и да, они очень близки.
"""
Example Output:
$ python list_sort_timeit.py
Using sort method: 19.0166599751
Using sorted builin method: 23.203567028
"""
import random
import timeit
print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat())
print x
print 'Using sorted builin method:',
x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat())
print x
О, я вижу Алекс Мартелли с ответом, когда я печатаю его. (Я оставлю редактирование, поскольку это может быть полезно).
Ответы
Ответ 1
Ваша ошибка в измерении следующая: после вашего первого вызова test_list1.sort()
, этот объект списка IS отсортирован - и сортировка Python, aka timsort, злобно быстро в уже отсортированных списках!!! Это самая частая ошибка при использовании timeit
- непреднамеренно получить побочные эффекты и не учитывать их.
Здесь хороший набор измерений, используя timeit
из командной строки, как он лучше всего используется:
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
y=list(x); y.sort()'
1000 loops, best of 3: 452 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
x.sort()'
10000 loops, best of 3: 37.4 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
sorted(x)'
1000 loops, best of 3: 462 usec per loop
Как вы видите, y.sort()
и sorted(x)
- шея и шея, но x.sort()
благодаря преимуществам побочных эффектов на порядок величины - только из-за вашей ошибки измерения, хотя: это ничего не говорит о sort
vs sorted
per se! -)
Ответ 2
Так как list.sort выполняет сортировку, поэтому сначала сортируется, но в следующий раз сортирует отсортированный список.
например. попробуйте это, и вы получите те же результаты
в большинстве случаев используется большая часть времени, копирование и сортировка также делает еще одну копию
import time
import random
test_list1=random.sample(xrange(1000),1000)
test_list2=random.sample(xrange(1000),1000)
s=time.time()
for i in range(100):
test_list1.sort()
print time.time()-s
s=time.time()
for i in range(100):
test_list2=sorted(test_list2)
print time.time()-s
Ответ 3
Ну, метод списков .sort()
сортирует список на месте, а sorted()
создает новый список. Поэтому, если у вас большой список, часть разницы в производительности будет вызвана копированием.
Тем не менее различие по порядку величины кажется большим, чем я ожидал. Возможно, list.sort()
имеет некоторую специальную оптимизацию, которую sorted()
не может использовать. Например, поскольку класс list
уже имеет внутренний массив Py_Object*[]
нужного размера, возможно, он может выполнять обмены более эффективно.
Изменить: Алекс и Анураг правы, разница по порядку величины обусловлена случайной сортировкой уже отсортированного списка в тестовом примере. Однако, как показывают тесты Alex, list.sort()
примерно на 2% быстрее, чем sorted()
, что имеет смысл из-за накладных расходов на копирование.