¿Cuál es la forma más eficiente de buscar listas anidadas en python?

Question

Tengo una lista que contiene listas anidadas y necesito saber la forma más eficiente de buscar dentro de esas listas anidadas.

por ejemplo, si tengo

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

y tengo que buscar toda la lista anterior, lo que es la forma más eficaz de encontrar 'd'?

Answer 1

Usando list comprehension, teniendo en cuenta:

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

rendimientos:

True 

y esto también podría hacerse con un generador (como se muestra en @AshwiniC haudhary)

actualización basada en comentarios a continuación:

Esta es la misma lista por comprensión, pero utilizando nombres de las variables más descriptivos:

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

Las construcciones de bucle en la parte lista por comprensión es equivalente a

for sublist in mylist: 
    for elem in sublist 

y genera una lista en la que 'd' se puede probar con el in operador.

Answer 2

utilizar una expresión generador, aquí toda la lista no se desplaza como generador generar resultados uno por 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

Si sus matrices están siempre ordenadas como se muestran, de modo que a[i][j] <= a[i][j+1] y a[i][-1] <= a[i+1][0] (el último elemento de una matriz es siempre menor o igual que el primer elemento en la siguiente matriz), puede eliminar muchas comparaciones haciendo algo como:

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 

Este tipo de optimización es sólo vale la pena si usted tiene una gran cantidad de matrices y todos ellos tienen una gran cantidad de elementos de embargo.

Answer 4

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

expresión generadora usando 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 

expresión generadora

$ 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 

lista por comprensión

$ 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 

¿Qué tal si el artículo está cerca del final o no está presente en absoluto? any es más rápido que la lista por comprensión

$ 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 

Tal vez si la lista es 1000 veces más largos?any es todavía más rápido

$ 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 

Sabemos que los generadores de tomar un tiempo para configurar, por lo que la mejor oportunidad para la LC de ganar es una lista muy corta

$ 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 

Y any utiliza menos memoria demasiado