python - Pythonでネストされたリストを検索する最も効率的な方法は何ですか？

Question

ネストされたリストを含むリストがあり、それらのネストされたリスト内を検索する最も効率的な方法を知る必要があります。

たとえば、私が持っている場合

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

上記のリスト全体を検索する必要がありますが、「d」を見つける最も効率的な方法は何ですか？

Answer 1

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

を使用したジェネレータ式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

ジェネレータ式

$ 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

リスト内包

$ 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

アイテムが終わりに近づいているか、まったく存在しない場合はどうですか？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]]"
    "'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

おそらく、リストが1000倍長い場合はどうでしょうか。anyまだ速い

$ 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

ジェネレーターのセットアップには時間がかかることがわかっているので、LCが勝つための最良のチャンスは非常に短いリストです

$ 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

またany、メモリの使用量も少なくなります

Answer 2

リスト内包表記を使用して、与えられた：

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

収量：

True

これはジェネレーターを使用して行うこともできます（@AshwiniChaudharyで示されています）

以下のコメントに基づいて更新します。

これは同じリスト内包表記ですが、よりわかりやすい変数名を使用しています。

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

リスト内包部分のループ構造は、

for sublist in mylist:
   for elem in sublist

'd'を演算子でテストできるリストを生成しますin。

Answer 3

ジェネレータ式を使用します。ここでは、ジェネレータが結果を1つずつ生成するため、リスト全体がトラバースされません。

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

配列が常に表示どおりに並べ替えられている場合、a[i][j] <= a[i][j+1]およびa[i][-1] <= a[i+1][0]（1つの配列の最後の要素が常に次の配列の最初の要素以下である）、次のようにすることで多くの比較を排除できます。

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

この種の最適化は、配列がたくさんあり、それらすべてに要素がたくさんある場合にのみ価値があります。

Answer 5

要素がリストにあるかどうかを知りたいだけの場合は、リストを文字列に変換して確認することでこれを行うことができます。よりネストされたリストのこれを拡張できます。[[1]、'a'、'b'、'd'、['a'、'b'、['c'、1]]]のよう に 、このメソッドは、ネストされたリストのレベルがわからない場合に役立ちます。検索可能なアイテムが存在するかどうかを知りたい。

    search='d'
    lis = [['a',['b'],'c'],[['d'],'e','f']]
    print(search in str(lis))