Влияет ли передача reverse = True при сортировке списка в Python на эффективность?

Question

При вызове sort() для списка в Python передача cmp=f замедляет сортировку. Влияет ли передача reverse=True на эффективность сортировки каким-либо образом (или идентична сортировке без реверса)?

Answer 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 %

Answer 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) и получил согласованные результаты.

Answer 3

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

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

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

Answer 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 непосредственно во втором случае и, таким образом, сохранить дополнительный вызов с помощью лямбда-функции. Но если у вас более выраженное выражение, это может окупиться.

Answer 5

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