Jaki jest najbardziej skuteczny sposób wyszukiwania zagnieżdżonych list w python?

Question

Mam listę, która zawiera zagnieżdżone listy i potrzebuję znać najbardziej efektywny sposób wyszukiwania w tych zagnieżdżonych listach.

przykład jeśli mam

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

i muszę przeszukać całą listę powyżej, co jest najbardziej skutecznym sposobem na znalezienie „d”?

Answer 1

za pomocą list comprehension, Dane:

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

Wynik:

True 

i można to również zrobić za pomocą generatora (jak pokazano w @AshwiniC haudhary)

Aktualizacja oparta na komentarz poniżej:

Oto ta sama lista ze zrozumieniem, ale przy bardziej opisowe nazwy zmiennych:

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

The typami pętli konstruktów w części lista Rozumienie jest równoważna

for sublist in mylist: 
    for elem in sublist 

i generuje listę, w której można testować "d" w odniesieniu doOperator.

Answer 2

użycie wyrażenia generującego tu cały lista będzie ruch jako generator wygenerowania wyników pojedynczo:

>>> 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

Jeśli twoje tablice są zawsze sortowane tak, jak pokazujesz, to a[i][j] <= a[i][j+1] i a[i][-1] <= a[i+1][0] (ostatni element jednej tablicy jest zawsze mniejszy lub równy pierwszemu elementowi w następnej tablicy), możesz wyeliminować wiele porównań robiąc coś takiego:

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 

Ten rodzaj optymalizacji jest tylko warto, jeśli masz wiele tablic i wszystkie one mają wiele elementów chociaż.

Answer 4

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

wyrażenie generator używając 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 

generator wyraz

$ 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 

listowego

$ 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 

Co powiesz na to, czy przedmiot jest bliski końca, czy w ogóle go nie ma? any jest szybszy niż listowego

$ 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 

Być może, jeśli lista jest 1000 razy dłuższe?any jeszcze szybciej

$ 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 

Wiemy, że generatory potrwać do skonfigurowania, więc najlepsza szansa dla LC na wygraną jest bardzo krótka lista

$ 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 

I any zużywa mniej pamięci zbyt