Python метод sort () в списке против встроенной функции sorted ()

Question

Я знаю, что функция __builtin__ sorted () работает на любой итерации. Но может ли кто-нибудь объяснить эту огромную (в 10 раз) разницу в производительности между anylist.sort () и sorted (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 () и sorted (list). Приведенный выше фрагмент кода показал кое-что интересное: функция сортировки python работает очень хорошо для уже отсортированных данных. Как указывает Anurag, в первом случае метод sort работает с уже отсортированными данными, а во втором - с новым, чтобы снова и снова выполнять работу.

Итак, я написал это для проверки, и да, они очень близки.

"""
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

О, я вижу Алекса Мартелли с ответом, когда я набираю этот ... (я оставлю правку, поскольку это может быть полезно).

Answer 1

Ваша ошибка в измерении следующая: после вашего первого вызова test_list1.sort() этот объект списка IS отсортирован - и сортировка Python, также известная как 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 против sorted per se! -)

Answer 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

Answer 3

Ну, метод списков .sort() сортирует список на месте, а sorted() создает новый список. Поэтому, если у вас большой список, часть разницы в производительности будет связана с копированием.

Тем не менее, разница на порядок больше, чем я ожидал. Возможно, list.sort() имеет какую-то специальную оптимизацию, которую sorted() не может использовать. Например, поскольку класс list уже имеет внутренний массив Py_Object*[] правильного размера, возможно, он может выполнять перестановки более эффективно.

Редактировать : Алекс и Анураг правы, разница в порядке значений вызвана тем, что вы случайно отсортировали отсортированный список в своем тестовом примере. Однако, как показывают тесты Алекса, list.sort() примерно на 2% быстрее, чем sorted(), что имеет смысл из-за затрат на копирование.