Проходит ли обращение reverse = True при сортировке списка в Python?

Ответ 1

Из моих тестов, похоже, существует небольшая разница:

import timeit

setup = """
import random
random.seed(1)
l = range(10000)
random.shuffle(l)
"""

run1 = """
sorted(l)
"""

run2 = """
sorted(l, reverse=True)
"""

n1 = timeit.timeit(run1, setup, number=10000)
n2 = timeit.timeit(run2, setup, number=10000)

print n1, n2
print (n2/n1 - 1)*100,"%"

Результаты (на моей машине):

38.8531708717 41.2889549732
6.26920286513 %

Такой же запуск, но для списка из 1000 элементов:

2.80148005486 2.74061703682
-2.17253083528 %

# ...another round...
2.90553498268 2.86594104767
-1.36270722083 %

Ответ 2

Я бы предположил, что нет замедления из-за reverse=True, так как результат может быть просто построен с обратными решениями на этом пути. При правильной оценке (спасибо Дункану) это предположение подтверждается:

In [18]: import random

In [57]: x = range(1000)

In [58]: random.shuffle(x)

In [59]: %timeit sorted(x)
1000 loops, best of 3: 341 us per loop

In [54]: x = range(1000)

In [55]: random.shuffle(x)

In [56]: %timeit sorted(x, reverse = True)
1000 loops, best of 3: 344 us per loop

Я повторил этот тест несколько раз и с разными размерами (N = 10**3, 10**4, 10**5) и получил согласованные результаты.

Ответ 3

Метод sort() является родным, т.е. реализован на языке хоста, а не на Python. Передача функции в аргументе cmp заставляет собственную реализацию вызывать эту функцию и выполнять код Python на каждой итерации. То, откуда происходит удар производительности.

С другой стороны, передача True в аргументе reverse только инструктирует собственный алгоритм сортировать элементы в обратном порядке. Если cmp не задано, будет задействован только собственный код, поэтому производительность должна быть сопоставима с обычным sort().

Конечно, бенчмаркинг наверняка скажет.

Ответ 4

Удивительно, что для сортировки списка в обратном порядке требуется больше времени. Другие ответы уже показали это с хорошими ориентирами. Я просмотрел источник и нашел объяснение в listobject.c:

/* Reverse sort stability achieved by initially reversing the list,
applying a stable forward sort, then reversing the final result. */
if (reverse) {
    if (keys != NULL)
        reverse_slice(&keys[0], &keys[saved_ob_size]);
    reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
}

Итак, чтобы получить отсортированный результат, список будет отменен перед сортировкой, затем отсортирован и, наконец, снова будет отменен. Перемещение списка - это операция O (n), поэтому вы будете платить за это больше и больше, чем больше список.

Это говорит о том, что если вы все равно создаете пользовательскую ключевую функцию, вы можете сэкономить время для больших списков, отрицая ее напрямую:

very_long_list.sort(key=lambda x, y: -cmp(x, y))

вместо reversed=True:

very_long_list.sort(key=lambda x, y: cmp(x, y), reverse=True)

В этом случае вы можете, конечно, пройти key=cmp непосредственно во втором случае и сохранить дополнительный вызов через лямбда-функцию. Но если у вас есть большее выражение, тогда это может окупиться.

Ответ 5

Обратите внимание, что встроенная функция cmp arg to list.sort и sorted устарела в Python 2.x и больше не разрешена в 3.x из-за плохой производительности, которую они дают, поскольку у вас есть заметил. Вместо этого вы должны использовать arg key для определения пользовательского порядка сортировки.