在python中搜索嵌套列表的最有效方法是什麼？

Question

我有一個包含嵌套列表的列表，我需要知道在這些嵌套列表中搜索的最有效方法。

例如，如果我有

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

，我要上面搜索整個列表，什麼是要找到「d」的最有效方法是什麼？

Answer 1

使用list comprehension，：

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

產量：

True 

這也可以用發生器完成（如@AshwiniC所示haudhary）根據下面的評論

更新：

下面是相同的列表理解，但是使用更具描述性的變量名：

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

列表理解部分的循環結構相當於

for sublist in mylist: 
    for elem in sublist 

並生成一個列表，其中'd'可以用in運營商。

Answer 2

用生成器表達式，這裏的整個列表將不會被橫移爲發電機產生的結果逐一：給

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

如果你的陣列始終排序爲你展示，讓a[i][j] <= a[i][j+1]和a[i][-1] <= a[i+1][0]（一個數組的最後一個元素始終小於或等於下一個數組中的第一個元素），那麼你就可以消除很多的比較通過執行類似：

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 4

>>> 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使用較少的內存也