Python:用索引展平嵌套列表

Question

给定一个任意大小的任意深度嵌套列表的列表，我想要一个对树中所有元素的平面、深度优先迭代器，但也有路径索引，这样:

for x, y in flatten(L), x == L[y[0]][y[1]]...[y[-1]]. 

那是

L = [[[1, 2, 3], [4, 5]], [6], [7,[8,9]], 10]
flatten(L)

应该产生:

(1, (0, 0, 0)),
(2, (0, 0, 1)),
(3, (0, 0, 2)),
(4, (0, 1, 0)),
(5, (0, 1, 1)),
(6, (1, 0)),
(7, (2, 0)),
(8, (2, 1, 0)),
(9, (2, 1, 1)),
(10, (3,))

我使用带有 yield 的生成器为此做了一个递归实现。声明:

def flatten(l):
    for i, e in enumerate(l):
        try:
            for x, y in flatten(e):
                yield x, (i,) + y
        except:
            yield e, (i,)

但我认为它不是一个好的或负责任的实现，是否有任何方法可以更普遍地使用内置函数或 std lib 之类的东西，例如 itertools ?

Answer 1

我认为你自己的解决方案没问题，没有什么比这更简单的了，Python 的标准库也无济于事。但无论如何，这是另一种方式，它以迭代方式而不是递归方式工作，因此它可以处理非常深的嵌套列表。

def flatten(l):
    stack = [enumerate(l)]
    path = [None]
    while stack:
        for path[-1], x in stack[-1]:
            if isinstance(x, list):
                stack.append(enumerate(x))
                path.append(None)
            else:
                yield x, tuple(path)
            break
        else:
            stack.pop()
            path.pop()

我将当前“事件”列表保存在 enumerate 的堆栈中迭代器，并将当前索引路径作为另一个堆栈。然后在 while 循环中，我总是尝试从当前列表中取出下一个元素并适本地处理它:

如果下一个元素是一个列表，那么我推送它的 enumerate堆栈上的迭代器，并为索引路径堆栈上的更深索引腾出空间。

如果下一个元素是一个数字，那么我将它连同它的路径一起生成。

如果当前列表中没有下一个元素，那么我从堆栈中删除它(或者更确切地说它的迭代器)和它的索引点。

演示:

>>> L = [[[1, 2, 3], [4, 5]], [6], [7,[8,9]], 10]
>>> for entry in flatten(L):
        print(entry)

(1, (0, 0, 0))
(2, (0, 0, 1))
(3, (0, 0, 2))
(4, (0, 1, 0))
(5, (0, 1, 1))
(6, (1, 0))
(7, (2, 0))
(8, (2, 1, 0))
(9, (2, 1, 1))
(10, (3,))

请注意，如果您像打印一样即时处理条目，那么您可以按照列表的形式生成路径，即使用 yield x, path .演示:

>>> for entry in flatten(L):
        print(entry)

(1, [0, 0, 0])
(2, [0, 0, 1])
(3, [0, 0, 2])
(4, [0, 1, 0])
(5, [0, 1, 1])
(6, [1, 0])
(7, [2, 0])
(8, [2, 1, 0])
(9, [2, 1, 1])
(10, [3])

这样，迭代器在整个迭代中只需要 O(n) 时间，其中 n 是结构中对象的总数(列表和数字)。当然，打印增加了复杂性，就像创建元组一样。但那是在生成器和打印的“错误”之外，或者你对每条路径所做的任何事情。例如，如果您只查看每个路径的长度而不是其内容，这需要 O(1)，那么整个事情甚至实际上是 O(n)。

说了这么多，我认为你自己的解决方案没问题。显然比这更简单。就像我在@naomik 下评论的 answer ，我认为您的解决方案无法处理大约 1000 或更多的深度列表是无关紧要的。一开始甚至不应该有这样的 list 。如果有，那是一个应该改正的错误。如果列表也可以扩展，就像您的情况一样，并且是平衡的，那么即使分支因子仅为 2，您也会在远低于 100 的深度处耗尽内存，并且不会接近 1000。如果列表不能变宽，然后嵌套列表是错误的数据结构选择，而且您首先不会对索引路径感兴趣。如果它可以变宽但不能变宽，那么我会说应该改进创建算法(例如，如果它代表一棵排序树，则添加平衡)。

再次关于我的解决方案:除了它处理任意深度列表的能力和它的效率之外，我发现它的一些细节很有趣:

你很少见到 enumerate对象存储在某处。通常它们只是直接在 loops&Co 中使用，比如 for i, x in enumerate(l): .

拥有 path[-1]准备好并用 for path[-1], x in ... 写入其中.

使用 for - 立即循环 break和一个 else分支，迭代下一个值并处理优雅结束，没有 try/except并且没有 next和一些默认。

如果你这样做 yield x, path ，即不要把每条路径都变成一个元组，那么你真的需要在迭代过程中直接处理它。例如，如果你做 list(flatten(L)) ，然后你会得到 [(1, []), (2, []), (3, []), (4, []), (5, []), (6, []), (7, []), (8, []), (9, []), (10, [])] .也就是说，“所有”索引路径将为空。当然那是因为实际上只有一个路径对象我一遍又一遍地更新和产生，最后它是空的。这与 itertools.groupby 非常相似，例如 [list(g) for _, g in list(groupby('aaabbbb'))]给你[[], ['b']] .这不是一件坏事。我最近wrote about that extensively .

较短的版本，一个堆栈包含索引和 enumerate对象交替:

def flatten(l):
    stack = [None, enumerate(l)]
    while stack:
        for stack[-2], x in stack[-1]:
            if isinstance(x, list):
                stack += None, enumerate(x)
            else:
                yield x, stack[::2]
            break
        else:
            del stack[-2:]