如何对Python列表进行深度搜索？

Question

我想在Python中的列表中进行深度搜索。例如，我想知道5是否在my_list中。

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

我该怎么做呢？

Answer 1

如果您有一个列表列表，则可以使用此方法

>>> 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-loops更好的方法了……

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

你也可以用它来扁平化多嵌套列表：

Recursive generator for flattening nested lists

Answer 3

您可以将flatten function (将其视为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的堆栈限制。