如何深度搜索Python列表？

Question

我想在Python中对一个列表进行深度搜索。比如，我想知道数字5是否在my_list这个列表里。

my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]

我该怎么做呢？

Answer 1

你可以把flatten函数（可以把它想象成是itertools.chain的递归版本）和Python的标准in操作符结合起来使用（在生成器上，这个操作符会进行线性搜索），这样就能得到以下效果：

>>> def flatten(nested):
    try:
        for sublist in nested:
            for element in flatten(sublist):
                yield element
    except TypeError:
        yield nested


>>> my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]
>>> 5 in flatten(my_list)
True

根据链接问题中的评论，如果你要搜索的内容是可迭代的（比如元组），你可能需要对flatten的代码进行一些调整，因为元组会像列表一样被展开。而且如果你在搜索字符串时，代码会递归运行，直到达到Python的堆栈限制。

Answer 2

不太确定有没有快速的方法来处理多层嵌套，但可以用递归算法来解决这个问题：

def nestedSearch(nested, v):
    for element in nested:
        if isinstance(element, list):
            if nestedSearch(element, v):
                return True
        elif element == v:
            return True
    return False

你也可以看看这个方法，用来把多层嵌套的列表变平：

递归生成器，用于扁平化嵌套列表

Answer 3

如果你有一个列表里面又包含了很多列表，你可以用这种方法。

>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> [item for sublist in l for item in sublist]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 5 in [item for sublist in l for item in sublist]
True

这个方法首先会把所有的列表合并成一个平坦的列表，然后用O(n)的方式去查找。

如果你的列表像你举的例子那样，我想不出其他方法可以做到这一点，除了使用for循环……

如何深度搜索Python列表？

6 个回答

撰写回答