Perché utilizzare un set per il confronto di elenchi?

Question

Ho appena letto un'altra domanda degli utenti mentre cercavo un modo per calcolare le differenze in due elenchi.

Python, compute list difference

mia domanda è perché vorrei fare

def diff(a,b): 
    b = set(b) 
    return [aa for aa in a if aa not in b] 

piuttosto che fare

def diff(a,b): 
    tmp = [] 
    for i in a: 
     if(i not in b): 
      tmp.append(i) 
return tmp 

Edit: appena notato la seconda funzione diff effettivamente restituito le somiglianze. Dovrebbe essere corretto ora.

Answer 1

solo dal punto di vista algoritmico, richiede O(n) costruire il set e O(n) fare lista comprensione (dal test se un elemento è contenuto in un insieme è O(1)). Tuttavia, nel secondo esempio, occorrerebbe O(n^2) per eseguire il ciclo di entrambi gli elenchi. Quindi, indipendentemente dal linguaggio di programmazione, il primo approccio è superiore.

Inoltre, le list comprehensions in python sono intrinsecamente più veloci di un ciclo for. Questo riduce il fattore costante ancora di più (e anche in modo significativo). Il motivo per cui si può riassumere in this post che cito qui:

Il fatto che list comprehensions può essere composto solo di espressioni, non dichiarazioni, è un fattore notevole, tanto meno lavoro è tenuto dietro le quinte per ogni iterazione. Un altro fattore è che il meccanismo di iterazione sottostante per la comprensione delle liste è molto più vicino a un ciclo C rispetto all'esecuzione di un ciclo for.

Answer 2

La comprensione degli elenchi è generalmente considerata più efficiente rispetto all'utilizzo di operazioni di elenco regolari durante la creazione di un elenco. Se la memoria è un problema, puoi usare un generatore.

This fornisce un po 'di informazioni re performance di for -loops, map e list comprehension. @benhoyt ha anche fornito un utile link confrontando i loop vs la comprensione degli elenchi.

Tuttavia, si noti che se le prestazioni sono un problema specifico, potrebbe valere la pena dedicare tempo/benchmark alle varie opzioni per selezionare l'opzione migliore per le proprie esigenze specifiche.

Answer 3

L'utilizzo del set è in genere più veloce perché deve essere ripetuto una sola volta per b, mentre l'esempio deve iterare una volta per ogni elemento in a.

Answer 4

La differenza principale tra le due opzioni è che quella che utilizza set è asintoticamente molto più efficiente.

In condizioni ragionevolmente favorevoli, la ricerca di un articolo in un set può essere effettuata nel tempo O(1); cercare un elemento in una lista richiede tempo O(n).

La seconda differenza, meno significativa, è che una versione utilizza una comprensione di lista mentre l'altra utilizza un ciclo for. La comprensione delle liste tende a produrre un codice più compatto. Inoltre tendono ad essere più efficienti (anche se se le prestazioni sono un problema, l'unico modo per ottenere un'immagine accurata è l'esecuzione di benchmark).

Answer 5

ho fatto alcuni test:

test_lists.py

a = range(1, 1000) 
b = range(2, 1002) 

tmp = [] 
for i in a: 
    if(i not in b): 
     tmp.append(i) 

test_set_list_comprehensions.py

a = range(1, 1000) 
b = range(2, 1002) 

b = set(b) 
[aa for aa in a if aa not in b] 

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b))) 

Ed è quello che timeit dice:

~$ python -m timeit 'import test_lists' 
1000000 loops, best of 3: 0.671 usec per loop 
~$ python -m timeit 'import test_set_list_comprehension' 
1000000 loops, best of 3: 0.766 usec per loop 
~$ python -m timeit 'import test_set' 
1000000 loops, best of 3: 0.656 usec per loop 

Quindi il migliore sembra essere:

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b)))