Qual è il modo più efficiente per cercare elenchi nidificati in python?

Question

Ho una lista che contiene elenchi annidati e ho bisogno di sapere il modo più efficiente per cercare all'interno di quegli elenchi annidati.

esempio, se ho

[['a','b','c'], 
['d','e','f']] 

e devo cercare l'intera lista di cui sopra, qual è il modo più efficace per trovare 'd'?

Answer 1

Utilizzando list comprehension, data:

mylist = [['a','b','c'],['d','e','f']] 
'd' in [j for i in mylist for j in i] 

rendimenti:

True 

e questo potrebbe anche essere fatto con un generatore (come mostrato da @AshwiniC haudhary)

aggiornamento basato sul commento qui sotto:

Qui è la stessa di lista, ma utilizzando i nomi delle variabili più descrittivi:

'd' in [elem for sublist in mylist for elem in sublist] 

I costrutti di loop nella parte di lista è equivalente a

for sublist in mylist: 
    for elem in sublist 

e genera una lista che dove 'd' può essere testato contro il 012.operatore.

Answer 2

utilizzare un'espressione generatore, qui la lista non verrà spostato come generatore generare risultati uno per uno:

>>> lis = [['a','b','c'],['d','e','f']] 
>>> 'd' in (y for x in lis for y in x) 
True 
>>> gen = (y for x in lis for y in x) 
>>> 'd' in gen 
True 
>>> list(gen) 
['e', 'f'] 

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in (y for x in lis for y in x)" 
    100000 loops, best of 3: 2.96 usec per loop 

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in [y for x in lis for y in x]" 
    100000 loops, best of 3: 7.4 usec per loop 

Answer 3

Se gli array vengono sempre ordinati come mostrato, in modo che a[i][j] <= a[i][j+1] e a[i][-1] <= a[i+1][0] (l'ultimo elemento di un array sia sempre minore o uguale al primo elemento nell'array successivo), è possibile eliminare molti confronti facendo qualcosa di simile:

a = # your big array 

previous = None 
for subarray in a: 
    # In this case, since the subarrays are sorted, we know it's not in 
    # the current subarray, and must be in the previous one 
    if a[0] > theValue: 
     break 
    # Otherwise, we keep track of the last array we looked at 
    else: 
     previous = subarray 

return (theValue in previous) if previous else False 

Questo tipo di ottimizzazione è utile solo se si hanno un sacco di array e tutti hanno un sacco di elementi però.

Answer 4

>>> lis=[['a','b','c'],['d','e','f']] 
>>> any('d' in x for x in lis) 
True 

espressione generatore utilizzando any

$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "any('d' in x for x in lis)" 
1000000 loops, best of 3: 1.32 usec per loop 

generatore di espressione

$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in (y for x in lis for y in x)" 
100000 loops, best of 3: 1.56 usec per loop 

di lista

$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in [y for x in lis for y in x]" 
100000 loops, best of 3: 3.23 usec per loop 

Che ne dici se l'elemento è vicino alla fine o non è presente affatto? any è più veloce rispetto alla lista di comprensione

$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" 
    "'NOT THERE' in [y for x in lis for y in x]" 
100000 loops, best of 3: 4.4 usec per loop 

$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" 
    "any('NOT THERE' in x for x in lis)" 
100000 loops, best of 3: 3.06 usec per loop 

Forse, se la lista è 1000 volte più a lungo?any è ancora più veloce

$ python -m timeit -s "lis=1000*[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" 
    "'NOT THERE' in [y for x in lis for y in x]" 
100 loops, best of 3: 3.74 msec per loop 
$ python -m timeit -s "lis=1000*[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" 
    "any('NOT THERE' in x for x in lis)" 
100 loops, best of 3: 2.48 msec per loop 

Sappiamo che i generatori prendere un po 'di impostare, in modo dalle migliori possibilità per la LC per vincere è un breve elenco

$ python -m timeit -s "lis=[['a','b','c']]" 
    "any('c' in x for x in lis)" 
1000000 loops, best of 3: 1.12 usec per loop 
$ python -m timeit -s "lis=[['a','b','c']]" 
    "'c' in [y for x in lis for y in x]" 
1000000 loops, best of 3: 0.611 usec per loop 

E any usa meno memoria troppo