Метод 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(), что имеет смысл из-за накладных расходов на копирование.