Verificare se gli elenchi condividono qualsiasi elemento in python

Question

Voglio verificare se qualsiasi degli elementi in un elenco sono presenti in un altro elenco. Posso farlo semplicemente con il codice qui sotto, ma ho il sospetto che ci possa essere una funzione di libreria per farlo. In caso contrario, esiste un metodo più pitioso per ottenere lo stesso risultato.

In [78]: a = [1, 2, 3, 4, 5] 

In [79]: b = [8, 7, 6] 

In [80]: c = [8, 7, 6, 5] 

In [81]: def lists_overlap(a, b): 
    ....:  for i in a: 
    ....:   if i in b: 
    ....:    return True 
    ....:  return False 
    ....: 

In [82]: lists_overlap(a, b) 
Out[82]: False 

In [83]: lists_overlap(a, c) 
Out[83]: True 

In [84]: def lists_overlap2(a, b): 
    ....:  return len(set(a).intersection(set(b))) > 0 
    ....: 

Answer 1

Risposta breve: usare not set(a).isdisjoint(b), è generalmente il più veloce.

Esistono quattro metodi comuni per verificare se due elenchi a e condividono qualsiasi elemento. La prima opzione è quella di convertire sia ai set e verificare la loro intersezione, come ad esempio:

bool(set(a) & set(b)) 

Perché set sono memorizzati utilizzando una tabella hash in Python, cercando loro è O(1) (vedi here per ulteriori informazioni sulla complessità operatori in Python). Teoricamente, questo è O(n+m) in media per gli oggetti n e m negli elenchi a e b. Ma 1) deve prima creare degli insiemi dagli elenchi, che possono richiedere un tempo non trascurabile, e 2) suppone che le collisioni di hash siano sparse tra i tuoi dati.

Il secondo modo per farlo utilizza un generatore di espressione eseguire iterazione sugli elenchi, ad esempio:

any(i in a for i in b) 

Questo permette di verificare sul posto, quindi non nuova memoria viene allocata per le variabili intermedie. Si salva anche sul primo ritrovamento. Ma l'operatore in è sempre sugli elenchi (vedere here).

Un'altra opzione proposta è un iterare hybridto attraverso uno della lista, convertire l'altro in un set e di test per l'adesione su questo set, in questo modo:

a = set(a); any(i in a for i in b) 

Un quarto approccio è quello di approfittare di il metodo isdisjoint() dei set (congelati) (vedi here), ad esempio:

not set(a).isdisjoint(b) 

Se gli elementi di ricerca sono vicino all'inizio di un array (ad esempio, è ordinato), il generatore di espressione è favorita, come gli insiemi si incrociano THOD devono allocare nuova memoria per le variabili intermedie:

from timeit import timeit 
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000) 
26.077727576019242 
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000) 
0.16220548999262974 

Ecco un grafico del tempo di esecuzione di questo esempio in funzione della dimensione della lista:

noti che entrambi gli assi sono logaritmica. Questo rappresenta il caso migliore per l'espressione del generatore. Come si può vedere, il metodo isdisjoint() è migliore per elenchi di dimensioni molto piccole, mentre l'espressione del generatore è migliore per elenchi di dimensioni più grandi.

D'altra parte, poiché la ricerca inizia con l'inizio per l'espressione ibrida e generatore, se l'elemento condiviso è sistematicamente alla fine dell'array (o entrambi gli elenchi non condividono alcun valore), disgiunti e imposta gli approcci di intersezione sono quindi molto più veloci rispetto all'espressione del generatore e all'approccio ibrido.

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000)) 
13.739536046981812 
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000)) 
0.08102107048034668 

E 'interessante notare che l'espressione generatore è il modo più lento per le taglie più grandi della lista. Questo è solo per 1000 ripetizioni, anziché 100000 per la figura precedente. Questa configurazione si approssima anche quando non sono condivisi elementi ed è il caso migliore per gli approcci di intersezione disgiunti e impostati.

Qui ci sono due analisi utilizzando numeri casuali (invece di brogli il setup di favorire una tecnica o di un altro):

un'alta probabilità di condivisione: elementi sono presi a caso da [1, 2*len(a)]. Scarse possibilità di condivisione: gli elementi sono presi a caso da [1, 1000*len(a)].

Fino ad ora, questa analisi supponeva che entrambi gli elenchi abbiano le stesse dimensioni.Nel caso di due elenchi di diverse dimensioni, per esempio a è molto più piccolo, isdisjoint() è sempre più veloce:

Assicurarsi che l'elenco a è il più piccolo, in caso contrario le prestazioni diminuisce. In questo esperimento, la dimensione dell'elenco a è stata impostata su 5.

In sintesi:

• Se le liste sono molto piccole (< 10 elementi), not set(a).isdisjoint(b) è sempre il più veloce.
• Se gli elementi negli elenchi sono ordinati o hanno una struttura regolare che è possibile sfruttare, l'espressione del generatore any(i in a for i in b) è la più veloce in elenchi di dimensioni grandi;
• Verificare l'intersezione impostata con not set(a).isdisjoint(b), che è sempre più veloce di bool(set(a) & set(b)).
• L'ibrido "iterate through list, test on set" a = set(a); any(i in a for i in b) è generalmente più lento di altri metodi.
• L'espressione del generatore e l'ibrido sono molto più lenti degli altri due approcci quando si tratta di elenchi senza elementi di condivisione.

Nella maggior parte dei casi, utilizzando il metodo isdisjoint() è l'approccio migliore come espressione generatore vorrà molto più tempo per eseguire, in quanto è molto inefficiente quando non elementi sono condivisi.

Answer 2

def lists_overlap3(a, b): 
    return bool(set(a) & set(b)) 

Nota: È possibile che questo presuppone che si desidera un valore booleano come la risposta. Se tutto ciò che serve è un'espressione da utilizzare in un if dichiarazione, basta usare if set(a) & set(b):

Answer 3

Si potrebbe anche usare any con la lista di comprensione:

any([item in a for item in b]) 

Answer 4

È possibile utilizzare il qualsiasi costruita nel espressione generatore di funzioni/wa:

def list_overlap(a,b): 
    return any(i for i in a if i in b) 

Come John e Lie hanno sottolineato questo dà risultati non corretti quando per ogni i condiviso dai due bool liste (i) == false. Dovrebbe essere:

return any(i in b for i in a) 

Answer 5

def lists_overlap(a, b): 
    sb = set(b) 
    return any(el in sb for el in a) 

Questo è asintoticamente ottimale (caso peggiore O (n + m)), e potrebbe essere migliore rispetto all'approccio intersezione causa any s' corto circuito.

Esempio:

lists_overlap([3,4,5], [1,2,3]) 

restituirà true, non appena si arriva a 3 in sb

EDIT: Un'altra variante (con grazie a Dave Kirby):

def lists_overlap(a, b): 
    sb = set(b) 
    return any(itertools.imap(sb.__contains__, a)) 

Questo si basa su imap L'iteratore, che è implementato in C, piuttosto che un generatore di comprensione. Utilizza anche sb.__contains__ come funzione di mappatura. Non so quanta differenza di prestazioni questo faccia. Sarà ancora in corto circuito.

Answer 6

in Python 2.6 o versione successiva che si può fare:

return not frozenset(a).isdisjoint(frozenset(b)) 

Answer 7

Questa domanda è piuttosto vecchia, ma ho notato che mentre le persone discutevano serie contro liste, nessuno pensava di usarle insieme. Seguendo l'esempio di Soravux,

caso peggiore per le liste:

>>> timeit('bool(set(a) & set(b))', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
100.91506409645081 
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
19.746716022491455 
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
0.092626094818115234 

E il caso migliore per le liste:

>>> timeit('bool(set(a) & set(b))', setup="a=list(range(10000)); b=list(range(10000))", number=100000) 
154.69790101051331 
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000) 
0.082653045654296875 
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000) 
0.08434605598449707 

Quindi, anche più veloce di iterazione attraverso due liste è l'iterazione se una lista per vedere se è in un set, il che ha senso dal momento che verificare se un numero è in un set richiede tempo costante mentre il controllo tramite iterazione attraverso un elenco richiede tempo proporzionale alla lunghezza della lista.

Quindi, la mia conclusione è che itera su un elenco e controlla se si trova in un set.

Answer 8

se non ti interessa quale potrebbe essere l'elemento che si sovrappone, puoi semplicemente controllare lo len della lista combinata rispetto agli elenchi combinati come un insieme. Se ci sono elementi sovrapposti, il set sarà più breve:

len(set(a+b+c))==len(a+b+c) restituisce Vero, se non c'è sovrapposizione.

Answer 9

mi butto un altro in uno stile di programmazione funzionale:

any(map(lambda x: x in a, b)) 

Spiegazione:

map(lambda x: x in a, b) 

restituisce un elenco di booleani in cui si trovano in a elementi di b. Tale elenco viene quindi passato a any, che restituisce semplicemente True se uno qualsiasi degli elementi è True.