Огромная разница во времени между сортировкой набора и сортировкой списка в Python

Question

Мне было интересно, должна ли я иметь свою структуру данных в виде набора или списка. В основном я буду делать операции над множествами, но в конце мне нужно будет их отсортировать.

Я задавался вопросом, должен ли я сначала составить список, а затем использовать sorted(list(my_set))или сразу же отсортировать набор sorted(my_set), Возможно, я мог бы рассмотреть общую фазу "для составления списка", так как в любом случае имеет смысл иметь упорядоченную итерацию в тот момент времени.

Поэтому я решил проверить это, ожидая, что список будет быстрее.

Benchmarker:

import time
def sorter(x):
    t1 = time.time()
    for i in range(1000000):
        sorted(x)
    return time.time() - t1

Данные:

one = range(1000)
a1 = list(one)
b1 = set(one)
sorter(a1)
# time: 16.5 s 
sorter(b1)
# time: 20.7 s

Затем я понял, что это может быть связано с тем, что элементы уже на месте, и вспомнил этот удивительный вопрос и ответ.

Затем я попробовал некоторые случайные данные:

two = numpy.random.randint(1, 1000, 1000)
a2 = list(two)
b2 = set(two)

С результатами:

sorter(a2)
# time: 4min 49s
sorter(b2)
# time: 18.9 s

Огромная разница, что происходит?

Бонус: даже в одну минуту кажется, что sorted(set(a_list)) впечатляюще быстрее, чем sorted(a_list),

Действительно, во втором случае могут быть дубликаты, которые будут отфильтрованы, что ускорит сортировку.

Answer 1

Я немного расширил ваш код и надеюсь, что это даст вам представление о том, что происходит:

import numpy
import uuid
import random
import time

def sorter(x):
    t1 = time.time()
    for i in range(10000):
        sorted(x)
    return time.time() - t1

def pr(name, x):
    print('sorter {:<12s} {:<11} (length {:>4})'.format(
        name, '{:.8}'.format(sorter(x)), len(x)))

a2sizes = []
b2sizes = []

for x in range(1000):
    two = numpy.random.randint(1, 1000, 1000)
    a2 = list(two)
    b2 = set(two)
    a2sizes.append(len(a2))
    b2sizes.append(len(b2))

print 'average number of elements in a2', sum(a2sizes)/len(a2sizes)
n = sum(b2sizes)/len(b2sizes)
print 'average number of elements in b2', n

это распечатывает:

average number of elements in a2 1000
average number of elements in b2 632

Это из-за столкновения в диапазоне случайных чисел

print
pr('a2', a2)
# making a list of set gives you already sorted elements
y = list(b2)
pr('y', y)
random.shuffle(y)
pr('shuffled y ', y)
pr('b2', b2)

дает в качестве вывода:

sorter a2           2.492537    (length 1000)
sorter b2           0.25028086  (length  633)
sorter y            0.19689608  (length  633)
sorter shuffled y   1.4935901   (length  633)

Тот b2 было бы быстрее, потому что меньше элементов логично, но то, что это еще быстрее, если вы сначала составите список из набора, должно иметь какую-то причину. Это снова медленнее, если вы перетасовываете, что список снова логичен, а перемешанный результат довольно близок к результату для a2 при компенсации длины списков.

Итак, давайте попробуем добавить что-то еще в список:

b3 = set()
for x in range(1000):
    b3.add(uuid.uuid4())

print '\nuuid elements', len(b3)

a3 = list(b3)
pr('a3', a3)
random.shuffle(a3)
pr('shuffled a3', a3)
pr('b3', b3)

дает (я был бы довольно удивлен иметь менее 1000 элементов):

uuid elements 1000
sorter a3           32.437758   (length 1000)
sorter shuffled a3  32.178433   (length 1000)
sorter b3           32.163802   (length 1000)

Так что это должно быть связано с наличием чисел в наборе:

previous = -1
ordered = True
for popped in b2:
    if popped < previous:
        print 'popped', popped, previous
        ordered = False
    previous = popped

print '\nOrdered', ordered

дает тебе:

Ordered True

Вместо итерации набор имеет pop() функцию, которую вы можете попробовать и использовать:

поп ()

Удалить и вернуть произвольный элемент из набора. Вызывает KeyError, если набор пуст.

Так что давайте произвольно извлекать элементы из набора b2 и посмотрим, есть ли что-то особенное:

previous = -1
ordered = True
while(b2):
    popped = b2.pop()
    if popped < previous:
        print 'popped', popped, previous
        ordered = False
    previous = popped

print '\nOrdered', ordered

дает тот же результат:

Ordered True

Таким образом, произвольно извлекаемые элементы набора чисел извлекают эти числа по порядку, независимо от порядка, в котором эти числа были введены. Поскольку итерация заключается в том, как создание списка извлекает элемент за раз, чтобы добавить в список, результатом list(b2) упорядоченный список, который сортируется довольно быстро с использованием алгоритма Timsort, используемого в Python.