Come controllare se un valore è presente in nessuna delle date set

Question

dire che ho diversi set (che devono essere diversi, non riesco a unirsi a loro come per il tipo di dati che sto lavorando con):

r = set([1,2,3]) 
s = set([4,5,6]) 
t = set([7,8,9]) 

Qual è il modo migliore per verificare se una determinata variabile è presente in uno di essi?

sto usando:

if myvar in r \ 
    or myvar in s \ 
    or myvar in t: 

Ma mi chiedo se questo può essere ridotto in qualche modo utilizzando set 's proprietà come union.

le seguenti opere, ma non trovo un modo per definire più sindacati:

if myvar in r.union(s) 
    or myvar in t: 

E sto anche chiedendo se questa unione influenzerà in qualche modo le prestazioni, dal momento che immagino sarà creata una temporanea set al volo.

Answer 1

Basta usare qualsiasi:

if any(myvar in x for x in (r,s,t)) 

set le ricerche sono 0(1) creando così un'unione per verificare se la variabile è in ogni set è del tutto inutile invece di controllare semplicemente utilizzando in con any che si interrompe non appena viene trovata una corrispondenza e non crea una nuova serie.

E mi chiedo anche se questa unione influenzerà in qualche modo performance del

Sì, certo unioning i set influisce sulle prestazioni, si aggiunge alla complessità, si sta creando un nuovo insieme ogni volta che è O(len(r)+len(s)+len(t)) in modo da possiamo dire addio al vero punto di utilizzo di set che sono ricerche efficienti.

Così la linea di fondo è che è si desidera mantenere le ricerche efficienti si dovrà unione il set una volta e tenere in memoria la creazione di una nuova variabile quindi utilizzando quella di fare la tua ricerca per myvar così la creazione iniziale sarà 0(n) e le ricerche saranno 0(1) in seguito.

Se non si desidera effettuare una ricerca prima di creare l'unione, non si avrà una soluzione lineare nella lunghezza di r+s+t -> set.union(*(r, s, t)) rispetto alle peggiori tre ricerche costanti (in media). Ciò significa anche aggiungere o rimuovere sempre elementi dal nuovo set unione aggiunti/rimossi da r,s o t.

Alcune tempi realistici su insiemi moderatamente grandi dimensioni mostrano esattamente la differenza:

In [1]: r = set(range(10000)) 

In [2]: s = set(range(10001,20000)) 

In [3]: t = set(range(20001,30000)) 

In [4]: timeit any(29000 in st for st in (r,s,t)) 
1000000 loops, best of 3: 869 ns per loop 

In [5]: timeit 29000 in r | s | t 
1000 loops, best of 3: 956 µs per loop 

In [6]: timeit 29000 in reduce(lambda x,y :x.union(y),[r,s,t]) 
1000 loops, best of 3: 961 µs per loop 

In [7]: timeit 29000 in r.union(s).union(t) 
1000 loops, best of 3: 953 µs per loop 

Timing gli spettacoli sindacali che praticamente tutto il tempo è speso nelle chiamate sindacali:

In [8]: timeit r.union(s).union(t) 
1000 loops, best of 3: 952 µs per loop 

Utilizzando più grande imposta e ottenere l'elemento in ultimo set:

In [15]: r = set(range(1000000)) 

In [16]: s = set(range(1000001,2000000)) 

In [17]: t = set(range(2000001,3000000)) 


In [18]: timeit any(2999999 in st for st in (r,s,t)) 
1000000 loops, best of 3: 878 ns per loop 

In [19]: timeit 2999999 in reduce(lambda x,y :x.union(y),[r,s,t]) 
1 loops, best of 3: 161 ms per loop 

In [20]: timeit 2999999 in r | s | t 
10 loops, best of 3: 157 ms per loop 

C'è l non importa, non importa quanto grande sia il set che usa any ma man mano che le dimensioni del set crescono, così il tempo di esecuzione viene utilizzato con union.

L'unico modo per renderlo più veloce sarebbe quella di attenersi a or ma ci stanno prendendo la differenza di poche centinaia di nanosecondi, che è il costo della creazione del generatore di espressione e la chiamata di funzione:

In [22]: timeit 2999999 in r or 2999999 in s or 2999999 in t 
10000000 loops, best of 3: 152 ns per loop 

Per set sindacali set.union (* (r, s, t)) è anche il più veloce come non costruire set di intermedie:

In [47]: timeit 2999999 in set.union(*(r,s,t)) 
10 loops, best of 3: 108 ms per loop 
In [49]: r | s | t == set.union(*(r,s,t)) 
Out[49]: True 

Answer 2

È possibile utilizzare reduce funzione per applicare la funzione di due argomenti, agli elementi di iterable:

>>> r = set([1,2,3]) 
>>> s = set([4,5,6]) 
>>> t = set([7,8,9]) 
>>> 
>>> reduce(lambda x,y :x.union(y),[r,s,t]) 
set([1, 2, 3, 4, 5, 6, 7, 8, 9]) 

E per il controllo della appartenenza a una di esse è possibile utilizzare un generatore di espressione all'interno di any che è più efficiente qui perché python usa hash table per archiviare i set e controllare che la nave membro abbia O (1) in tali strutture dati come i dizionari o frozenset. Anche per controllare l'appartenenza a tutti i set usi all.

if any(i in item for item in [r,s,t]): 
    #do stuff 

Ma in questo caso (Non per grandi insiemi) utilizzando or operatore è più veloce.

value in r|s|t 

Questo è un punto di riferimento in tutti i modi:

~$ python -m timeit "r = set([1,2,3]);s = set([4,5,6]);t = set([7,8,9]);3 in reduce(lambda x,y :x.union(y),[r,s,t])" 
1000000 loops, best of 3: 1.55 usec per loop 
~$ python -m timeit "r = set([1,2,3]);s = set([4,5,6]);t = set([7,8,9]);3 in r|s|t" 
1000000 loops, best of 3: 1.11 usec per loop 
~$ python -m timeit "r = set([1,2,3]);s = set([4,5,6]);t = set([7,8,9]);any(3 in item for item in [r,s,t])" 
1000000 loops, best of 3: 1.24 usec per loop 
~$ python -m timeit "r = set([1,2,3]);s = set([4,5,6]);t = set([7,8,9]);3 in r.union(s).union(t)" 
1000000 loops, best of 3: 1.19 usec per loop 

Nota che, come accennato @Padraic Cunningham per grandi insiemi usando un any è molto efficiente!

Answer 3

È possibile utilizzare integrato any:

r = set([1,2,3]) 
s = set([4,5,6]) 
t = set([7,8,9]) 
if any(myvar in x for x in [r,s,t]): 
    print "I'm in one of them" 

any sarà corto circuito sulla prima condizione che restituisce True in modo da poter andare in giro la costruzione di una potenzialmente enorme union o il controllo un sacco di set per l'inclusione potenzialmente.

E mi chiedo anche se questa unione influirà in qualche modo sulle prestazioni, dal momento che immagino che un set temporaneo verrà creato al volo.

Secondo wiki.python.coms|t è mentre le ricerche sono O(1).

Per n insiemi con l elementi ciascuno, facendo union iterativamente per costruire il set comporterà:

a.union(b).union(c).union(d) .... .union(n) 

che equivale a O(l+l) per a.union(b) e O(2l+2l+l)a.union(b).union(c) e così via, che riassume a O(n*(n+1)/2)*l).

O(n^2*l) è quadratico e annulla il vantaggio prestazionale dell'utilizzo di set.

La ricerca in n set con any si esibirà al O(n)

Answer 4

si può semplicemente fare

if myvar in r.union(s).union(t)

E non è necessario preoccuparsi delle prestazioni qui. Sì, crea un set temporaneo al volo ma, poiché non viene memorizzato, raccoglie i rifiuti.

Answer 5

| è un operatore unione di sets in python. È possibile definire l'unione su più delle formazioni con | come:

>>> r = set([1,2,3]) 
>>> s = set([4,5,6]) 
>>> t = set([7,8,9]) 
>>> r | s | t 
set([1, 2, 3, 4, 5, 6, 7, 8, 9])