Enorme differenza di tempo tra l'ordinamento di un set e l'ordinamento di un elenco in Python

Question

Mi chiedevo se avrei dovuto avere la mia struttura dati come un set o una lista. Principalmente farò operazioni di set, ma alla fine avrò bisogno di ordinarlo.

Mi chiedevo se avrei dovuto prima creare un elenco e quindi utilizzare sorted(list(my_set)) o semplicemente ordinare immediatamente il set sorted(my_set). Probabilmente, potrei considerare una fase generale di "elencare", poiché avere un iterabile ordinato in quel momento potrebbe avere comunque senso.

Quindi ho deciso di testarlo, aspettandomi che una lista fosse più veloce.

Benchmarker:

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

dati:

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

Mi resi conto allora che potrebbe avere a che fare con il fatto che gli elementi sono già in atto, e ricordato this amazing question & answer.

Poi, ho provato un po 'di dati casuali:

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

Con i risultati:

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

differenza enorme, che cosa sta succedendo?

Bonus: appare anche in un istante di un minuto, che sorted(set(a_list)) è notevolmente più veloce di sorted(a_list).

Infatti nel secondo caso, possono esserci duplicati che verrebbero filtrati e quindi accelerano l'ordinamento.

Answer 1

ho esteso il codice un po 'e spero che questo vi darà indicazioni su ciò che sta accadendo:

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 

Questo stampa:

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

Questo è a causa della collisione nel caso gamma

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) 

numero dà come output:

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) 

Che b2 sarebbe più veloce perché ci sono meno elementi è logico, ma che questo è ancora più veloce se per prima cosa una lista del set deve avere qualche motivo. Che sia di nuovo più lento se si rimescola quell'elenco è di nuovo logico e il risultato mescolato è piuttosto vicino al risultato di a2 quando compensato per la lunghezza degli elenchi.

Quindi, consente di provare a mettere qualcosa di diverso nella lista:

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) 

dà (sarei stato un po 'sorpreso di avere meno di 1000 elementi):

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

quindi deve avere qualcosa a che fare con con numero nel set:

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

print '\nOrdered', ordered 

ti dà:

Ordered True 

Invece di iterazione, un set ha una funzione pop() si può provare ed impiego:

pop()

rimuove e restituisce un elemento arbitrario dal set. Solleva KeyError se il set è vuoto.

così lascia arbitrariamente recuperare elementi dal set b2 e vedere se c'è qualcosa di speciale:

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

print '\nOrdered', ordered 

dà lo stesso risultato:

Ordered True 

Così arbitrariamente recuperando elementi del set di numero recupera quei numeri in ordine, indipendente dall'ordine di come questi numeri sono stati messi in. Poiché l'iterazione è il modo in cui la creazione di elenchi recupera un elemento alla volta da aggiungere all'elenco, il risultato di list(b2) è un elenco ordinato e viene ordinato abbastanza velocemente utilizzando l'algoritmo Timsort utilizzato in Python.