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 的回答下评论的那样，我认为您的解决方案无法处理 1000 或更多左右的深度列表是无关紧要的。一开始甚至不应该有这样的清单。如果有，那是一个应该改正的错误。如果列表也可以变宽，就像你的情况一样，并且是平衡的，那么即使分支因子仅为 2，你也会在深度远低于 100 的情况下耗尽内存，并且不会接近 1000。如果列表不能变宽，然后嵌套列表是错误的数据结构选择，而且您首先不会对索引路径感兴趣。如果它可以走得更远但是没有，那么我会说应该改进创建算法（例如，如果它代表一个排序的树，添加平衡）。

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

• 您很少会看到enumerate对象存储在某处。通常它们只是直接在 loops&Co 中使用，比如for i, x in enumerate(l):.
• 具有path[-1]现场准备，并写入到它for path[-1], x in ...。
• 使用for带有立即数break和else分支的-loop来迭代下一个单个值并在没有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']]。这不是一件坏事。我最近广泛地写了这篇文章。

一个堆栈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:]

Answer 2

从直接递归和具有默认值的状态变量开始，

\n\n

def flatten (l, i = 0, path = (), acc = []):\n  if not l:\n    return acc\n  else:\n    first, *rest = l\n    if isinstance (first, list):\n      return flatten (first, 0, path + (i,), acc) + flatten (rest, i + 1, path, [])\n    else:\n      return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ])\n\nprint (flatten (L))\n# [ (1, (0, 0, 0))\n# , (2, (0, 0, 1))\n# , (3, (0, 0, 2))\n# , (4, (0, 1, 0))\n# , (5, (0, 1, 1))\n# , (6, (1, 0))\n# , (7, (2, 0))\n# , (8, (2, 1, 0))\n# , (9, (2, 1, 1))\n# , (10, (3,))\n# ]\n

\n\n

上面的程序与你的程序有同样的弱点；对于深度列表来说并不安全。我们可以使用延续传递风格使其尾部递归 \xe2\x80\x93 更改为粗体

\n\n

def identity (x):\n  return x\n\n# tail-recursive, but still not stack-safe, yet\ndef flatten (l, i = 0, path = (), acc = [], cont = identity):\n  if not l:\n    return cont (acc)\n  else:\n    first, *rest = l\n    if isinstance (first, list):\n      return flatten (first, 0, path + (i,), acc, lambda left:\n        flatten (rest, i + 1, path, [], lambda right:\n          cont (left + right)))\n    else:\n      return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ], cont)\n\n\nprint (flatten (L))\n# [ (1, (0, 0, 0))\n# , (2, (0, 0, 1))\n# , (3, (0, 0, 2))\n# , (4, (0, 1, 0))\n# , (5, (0, 1, 1))\n# , (6, (1, 0))\n# , (7, (2, 0))\n# , (8, (2, 1, 0))\n# , (9, (2, 1, 1))\n# , (10, (3,))\n# ]

\n\n

最后，我们用我们自己的机制替换递归调用call。这可以有效地对递归调用进行排序，现在它适用于任何大小和任何嵌套级别的数据。这种技术称为蹦床\xe2\x80\x93 变化以粗体显示

\n\n

def identity (x):\n  return x\n\ndef flatten (l):\n  def loop (l, i = 0, path = (), acc = [], cont = identity):  \n    if not l:\n      return cont (acc)\n    else:\n      first, *rest = l\n      if isinstance (first, list):\n        return call (loop, first, 0, path + (i,), acc, lambda left:\n          call (loop, rest, i + 1, path, [], lambda right:\n            cont (left + right)))\n      else:\n        return call (loop, rest, i + 1, path, acc + [ (first, path + (i,)) ], cont)\n\n  return loop (l) .run ()\n\nclass call:\n  def __init__ (self, f, *xs):\n    self.f = f\n    self.xs = xs\n\n  def run (self):\n    acc = self\n    while (isinstance (acc, call)):\n      acc = acc.f (*acc.xs)\n    return acc\n\nprint (flatten (L))\n# [ (1, (0, 0, 0))\n# , (2, (0, 0, 1))\n# , (3, (0, 0, 2))\n# , (4, (0, 1, 0))\n# , (5, (0, 1, 1))\n# , (6, (1, 0))\n# , (7, (2, 0))\n# , (8, (2, 1, 0))\n# , (9, (2, 1, 1))\n# , (10, (3,))\n# ]

\n\n

为什么更好？客观地说，这是一个比较完整的程序。仅仅因为它看起来更复杂并不意味着它的效率较低。

\n\n

当输入列表嵌套深度超过 996 层时（在 python 3.x 中），问题中提供的代码将失败

\n\n

depth = 1000\nL = [1]\nwhile (depth > 0):\n  L = [L]\n  depth = depth - 1\n\nfor x in flatten (L):\n  print (x)\n\n# Bug in the question\'s code:\n# the first value in the tuple is not completely flattened\n# ([[[[[1]]]]], (0, 0, 0, ... ))\n

\n\n

更糟糕的是，当depth增加到 2000 左右时，问题中提供的代码会生成运行时错误GeneratorExitException。

\n\n

使用我的程序时，它适用于任何大小的输入、嵌套到任何深度，并且始终产生正确的输出。

\n\n

depth = 50000\nL = [1]\nwhile (depth > 0):\n  L = [L]\n  depth = depth - 1\n\nprint (flatten (L))\n# (1, (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49990 more...))\n\nprint (flatten (range (50000)))\n# [ (0, (0,))\n# , (1, (1,))\n# , (2, (2,))\n# , ...\n# , (49999, (49999,))\n# ]\n

\n\n

谁会有这么深的清单呢？一种常见的情况是创建深层树状结构的链表

\n\n

my_list = [ 1, [ 2, [ 3, [ 4, None ] ] ] ]\n

\n\n

这种结构很常见，因为最外面的对使我们可以轻松访问我们关心的两个语义部分：第一项和其余项。链表也可以使用元组或字典来实现。

\n\n

my_list = ( 1, ( 2, ( 3, ( 4, None ) ) ) )\n\nmy_list = { "first": 1\n          , "rest": { "first": 2\n                    , "rest": { "first": 3\n                              , "rest": { "first": 4\n                                        , "rest": None\n                                        }\n                              }\n                    }\n          }\n

\n\n

从上面我们可以看到，合理的结构可能会产生显着的深度。在 Python 中，[]、()、 和{}允许您无限嵌套。为什么我们的泛型要flatten限制这种自由？

\n\n

我认为，如果您要设计一个像 一样的通用函数flatten，我们应该选择在大多数情况下有效且意外最少的实现。仅仅因为使用了某种（深层）结构而突然失败的结构是不好的。我的答案中使用flatten的不是最快的^[1]，但它不会因为奇怪的答案或程序崩溃而让程序员感到惊讶。

\n\n

^[1]除非性能很重要，否则我不会测量性能，因此我没有做任何flatten上面的调整。我的程序的另一个低调的优点是您可以调整它，因为我们编写了 \xe2\x80\x93 另一方面，如果for,enumerate和yield导致您的程序出现问题，您会如何“修复”它？我们怎样才能让它更快呢？我们如何让它适用于更大尺寸或深度的输入？法拉利绕了一棵树之后还有什么用呢？

\n