Ogromna różnica w czasie pomiędzy sortowaniem zestawu a sortowaniem listy w Pythonie

Question

Zastanawiałem się, czy powinienem mieć swoją strukturę danych jako zestaw lub listę. Przeważnie wykonam operacje setowe, ale ostatecznie będę musiał je posortować.

Zastanawiam się, czy powinienem najpierw ustawić zestaw, a następnie użyć sorted(list(my_set)), lub po prostu posortować zestaw natychmiast sorted(my_set). Prawdopodobnie mógłbym rozważyć ogólną fazę "listowania", ponieważ posiadanie uporządkowanej iteracji w tym momencie może i tak mieć sens.

Postanowiłem przetestować to, oczekując, że lista będzie szybsza.

Benchmarker:

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

danych:

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

Później zrozumiałem, to może mieć do czynienia z faktem, że elementy są już na swoim miejscu, a pamiętał this amazing question & answer.

Następnie próbowałem jakieś losowe dane:

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

z rezultatów:

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

ogromna różnica, co się dzieje?

Bonus: Pojawia się nawet w czasie jednej minuty, że sorted(set(a_list)) jest imponująco szybszy niż sorted(a_list).

Rzeczywiście w drugim przypadku mogą występować duplikaty, które zostaną przefiltrowane, a co za tym idzie przyspieszenie sortowania.

Answer 1

I rozszerzony kod nieco i mam nadzieję, że to daje wgląd w to, co się dzieje:

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 

ten wypisuje:

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

To właśnie z powodu kolizji w losowo Zakres numerów

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) 

daje na wyjściu:

To, że b2 będzie szybsze, ponieważ jest mniej elementów, jest logiczne, ale jest to jeszcze szybsze, jeśli po raz pierwszy zestawienie zestawu musi mieć jakiś powód. To znowu jest wolniejsze, jeśli przetasowanie tej listy jest ponownie logiczne, a wynik losowy jest raczej zbliżony do wyniku dla a2, gdy jest rekompensowany długością list.

Więc spróbujmy umieścić coś innego w liście:

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) 

daje (byłbym raczej zaskoczony, aby mieć mniej niż 1000 elementów):

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

Więc to musi mieć coś zrobić z konieczności numerów w zestawie:

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

print '\nOrdered', ordered 

daje:

Ordered True 

Zamiast iteracji, A set ma pop() funkcji można spróbować użyć:

pop()

Wyjmij i powrócić z dowolnego elementu zestawu. Powoduje podniesienie KeyError, jeśli zestaw jest pusty.

Więc pozwala arbitralnie odzyskać elementy z zestawu b2 i sprawdzić, czy jest coś specjalnego:

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

print '\nOrdered', ordered 

daje ten sam wynik:

Ordered True 

więc dowolnie odbieraniem elementy z zestawu liczba pobiera te numery w kolejności, niezależnie od zamawiania, w jaki sposób numery te zostały umieszczone w. Ponieważ iteracja polega na tym, że tworzenie listy pobiera element w czasie dołączania do listy, wynikiem list(b2) jest uporządkowana lista, która zostaje posortowana dość szybko przy użyciu algorytmu Timsort używanego w języku Python.