Python中搜索嵌套列表的最有效方法是什么？

Question

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

例如，如果我有：

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

如果我必须在整个列表中查找'd'，那么最有效的方法是什么？

- fdsa

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也使用更少的内存

- John La Rooy

---

我会谨慎地泛化关于基于搜索'd'（即相对靠近列表前面的东西）的内容。如果您查看我和@Ashwini在他的答案下进行的讨论，您会发现在列表中选择“目标”的选择会产生重大差异。在我们的试验中，如果目标位于中间或末尾，LC击败了生成器。如果目标靠近前面，生成器则“获胜”。我认为最终结果非常依赖于特定的数据集和所寻找的目标。 - Levon

@Levon，我非常清楚这种权衡。然而，在这种情况下，即使项目根本不存在，any仍然比LC更快。 - John La Rooy

我并不是要暗示你不是这样的人..而且在你提出之前，我甚至没有想到要使用“any”，所以这对我以后的使用有所启示。 - Levon

@Levon，LC 更快的唯一场景是对于非常短的列表。除非您希望列表始终很短，否则最好不要在此处使用列表推导式。 - John La Rooy

@gnibbler 如何确定使用gen、LC还是any()？ 因为在这种情况下，any()更快，在我发布的另一个链接中，gen比any()更快。我完全知道any()，但在这里没有使用它，因为我看到了那个问题的结果，而这次any()提供了更快的解决方案。 - Ashwini Chaudhary

@AshwiniChaudhary，我认为确定的唯一方法就是尝试。此外，不同实现/版本的Python之间相对时间可能会更加复杂。通常情况下，除非需要列表（用于切片、反转等），否则我不会使用列表推导式。生成器表达式是一个很好的第一选择，尽管在某些情况下，它们可以被itertools等使用所击败。 - John La Rooy

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

并生成一个列表，可以使用in运算符测试'd'。

- Levon

---

为了让我理解正在发生的事情，你能澄清一下j和i分别代表什么吗？ - fdsa

@fdsa 我会更新我的答案，添加一个“详细”版本（更具描述性的变量名称）。 - Levon

感谢您抽出时间，我很感激。 - fdsa

@Downvoter .. 能否请您解释一下？这是对 OP 问题的一个功能性解决方案。没有解释的负评对任何人都没有帮助（包括 OP、SO 或我）。如果是因为我没有使用生成器，您可以从与 Ashwini 的讨论中看到，生成器解决方案并不总是更快的。 - Levon

我会认为“最有效”的措辞是表明OP实际上有大量数据需要搜索，否则他们就会简单地省略这些词。 - Gabe

Answer 3

使用生成器表达式，在此情况下整个列表不会被遍历，因为生成器将逐个生成结果：

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

- Ashwini Chaudhary

---

“整个列表不会被遍历”是什么意思？..如果你没有提前终止，那么你必须在某个时候生成所有的值，对吗？措辞似乎暗示相反的意思。 - Levon

所以它的行为就像一个短路布尔表达式？我不知道呢，很棒。谢谢，我学到了新东西。 - Levon

@Levon 是的，完全正确，并且一旦找到值就终止，但有趣的是，timeit 的结果表明您的解决方案更好。 - Ashwini Chaudhary

@Levon 这次我搜索了11，这次LC比生成器快多了。o.O - Ashwini Chaudhary

这次我们得到了相同的结果，我搜索了10 :-)和18，而LC每次都击败了生成器，尽管对于“d”，LC速度较慢。 - Levon

Answer 4

如果你只想知道你的元素是否在列表中存在，那么你可以将列表转换为字符串并进行检查。你可以扩展这种方法到更多嵌套的列表中。例如：[[1],'a','b','d',['a','b',['c',1]]]。如果你不知道嵌套列表的级别，但想知道可搜索项是否存在，则此方法很有帮助。

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

- sahasrara62

---

这个工作得非常好！感谢Sahasraru(1K)。如果这是C语言，我会有一个指针ptr，如果我执行*ptr = z，那么列表将看起来像这样lis = [['a'，['b']，'c']，[['z']，'e'，'f']]。那么在这一点上，你如何用Python替换元素？谢谢。 - Santhosh Kumar

Answer 5

如果您的数组总是按照您所展示的方式排序，即 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

只有在您拥有大量数组并且它们都具有大量元素的情况下，这种优化才是值得的。

- Gordon Bailey

---

谢谢您的建议 - 我之前没有考虑过排序，但由于它们将经常使用，所以我会考虑进行排序。 - fdsa

没问题 - 我不知道你将拥有多少数据或者你的确切用例是什么，但如果你确实有大量数据，那么值得研究一下 Python 的collections模块，它具有高性能的数据结构，适用于特定的任务。 - Gordon Bailey

如果它们总是排序的，最好使用bisect模块。 - John La Rooy