在尝试回答这样的问题时,您确实需要给出您作为解决方案提出的代码的限制。如果只是关于表演,我不会太介意,但作为解决方案提出的大多数代码(包括接受的答案)都无法展平任何深度大于 1000 的列表。
当我说大多数代码时,我的意思是所有使用任何形式的递归(或调用递归的标准库函数)的代码。所有这些代码都失败了,因为对于每个递归调用,(调用)堆栈都会增长一个单位,并且(默认)python 调用堆栈的大小为 1000。
如果您对调用堆栈不太熟悉,那么以下内容可能会有所帮助(否则您可以滚动到Implementation)。
调用堆栈大小和递归编程(地牢类比)
寻找宝藏并退出
想象一下,你进入一个带有编号房间的巨大地牢,寻找宝藏。你不知道这个地方,但你有一些关于如何找到宝藏的迹象。每个迹象都是一个谜(难度各不相同,但你无法预测它们会有多难)。你决定考虑一下节省时间的策略,你做了两个观察:
- 找到宝藏很难(很长时间),因为您必须解决(可能很难)谜题才能到达那里。
- 一旦找到宝藏,回到入口可能很容易,你只需要在另一个方向使用相同的路径(虽然这需要一些记忆来回忆你的路径)。
进入地牢时,您会注意到这里有一个小笔记本。你决定用它来写下你在解决一个谜语后离开的每个房间(进入一个新房间时),这样你就可以回到入口处。这是一个天才的想法,你甚至不会花一分钱来实施你的策略。
你进入地牢,成功解开了前 1001 个谜语,但是你没有计划好,你借来的笔记本里没有空间了。你决定放弃你的任务,因为你宁愿没有宝藏也不愿永远迷失在地牢里(这看起来确实很聪明)。
执行递归程序
基本上,这与寻找宝藏完全一样。地牢是计算机的内存,你现在的目标不是寻找宝藏,而是计算一些函数(找到给定x的f(x))。指示只是帮助您解决f(x)的子例程。您的策略与调用堆栈策略相同,笔记本是堆栈,房间是函数的返回地址:
x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected
print(' '.join(y))
你在地牢中遇到的问题在这里是一样的,调用堆栈的大小是有限的(这里是 1000),因此,如果你输入了太多的函数而没有返回,那么你将填满调用堆栈并出现一个看起来像的错误比如“亲爱的冒险者,很抱歉,你的笔记本满了”:RecursionError: maximum recursion depth exceeded
。请注意,您不需要递归来填充调用堆栈,但非递归程序不太可能调用 1000 个函数而不返回。同样重要的是要了解,一旦您从函数返回,调用堆栈就会从使用的地址中释放出来(因此名称为“堆栈”,返回地址在进入函数之前被压入并在返回时被拉出)。在简单递归的特殊情况下(一个函数f
一次调用自身——一遍又一遍——)你将f
一遍又一遍地进入,直到计算完成(直到找到宝藏),然后返回,f
直到你回到你f
最初调用的地方。调用堆栈将永远不会从任何东西中释放出来,直到它一个接一个地从所有返回地址中释放出来。
如何避免这个问题?
这实际上很简单:“如果您不知道递归可以走多深,请不要使用递归”。这并不总是正确的,因为在某些情况下,尾调用递归可以被优化 (TCO)。但在python中,情况并非如此,即使“写得很好”的递归函数也不会优化堆栈的使用。Guido 有一篇关于这个问题的有趣帖子:Tail Recursion Elimination。
有一种技术可以用来使任何递归函数迭代,我们可以称这种技术为自带笔记本。例如,在我们的特定情况下,我们只是在探索一个列表,进入一个房间就相当于进入一个子列表,你应该问自己的问题是我怎样才能从一个列表返回到它的父列表?答案并不复杂,重复以下直到stack
为空:
- 当进入一个新的子列表时,将当前列表
address
和index
in a推stack
入(注意列表地址+索引也是一个地址,因此我们只使用调用堆栈使用的完全相同的技术);
- 每次找到一个项目时,
yield
它(或将它们添加到列表中);
- 完全探索列表后,使用
stack
return address
(and index
)返回父列表。
另请注意,这等效于树中的 DFS,其中一些节点是子列表A = [1, 2]
,而一些节点是简单项:0, 1, 2, 3, 4
(for L = [0, [1,2], 3, 4]
)。树看起来像这样:
L
|
-------------------
| | | |
0 --A-- 3 4
| |
1 2
DFS 遍历前序是:L、0、A、1、2、3、4。请记住,为了实现迭代 DFS,您还“需要”一个堆栈。我之前提出的实现导致具有以下状态(对于stack
和flat_list
):
init.: stack=[(L, 0)]
**0**: stack=[(L, 0)], flat_list=[0]
**A**: stack=[(L, 1), (A, 0)], flat_list=[0]
**1**: stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**: stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**: stack=[(L, 2)], flat_list=[0, 1, 2, 3]
**3**: stack=[(L, 3)], flat_list=[0, 1, 2, 3, 4]
return: stack=[], flat_list=[0, 1, 2, 3, 4]
在此示例中,堆栈最大大小为 2,因为输入列表(以及树)的深度为 2。
执行
对于实现,在 python 中,您可以通过使用迭代器而不是简单列表来简化一点。对(子)迭代器的引用将用于存储子列表返回地址(而不是同时具有列表地址和索引)。这没什么大的区别,但我觉得这更具可读性(而且速度也更快):
def flatten(iterable):
return list(items_from(iterable))
def items_from(iterable):
cursor_stack = [iter(iterable)]
while cursor_stack:
sub_iterable = cursor_stack[-1]
try:
item = next(sub_iterable)
except StopIteration: # post-order
cursor_stack.pop()
continue
if is_list_like(item): # pre-order
cursor_stack.append(iter(item))
elif item is not None:
yield item # in-order
def is_list_like(item):
return isinstance(item, list)
另外,请注意在is_list_like
I haveisinstance(item, list)
中,可以对其进行更改以处理更多输入类型,在这里我只想拥有最简单的版本,其中 (iterable) 只是一个列表。但你也可以这样做:
def is_list_like(item):
try:
iter(item)
return not isinstance(item, str) # strings are not lists (hmm...)
except TypeError:
return False
这将字符串视为“简单项目”,因此flatten_iter([["test", "a"], "b])
将返回["test", "a", "b"]
而不是["t", "e", "s", "t", "a", "b"]
。请注意,在这种情况下,iter(item)
每个项目都会被调用两次,让我们假设这是读者的练习,以使这个更清晰。
对其他实现的测试和评论
最后,请记住,您不能使用打印无限嵌套列表L
,print(L)
因为在内部它将使用对__repr__
( RecursionError: maximum recursion depth exceeded while getting the repr of an object
) 的递归调用。出于同样的原因,flatten
涉及的解决方案str
将失败并显示相同的错误消息。
如果你需要测试你的解决方案,你可以使用这个函数来生成一个简单的嵌套列表:
def build_deep_list(depth):
"""Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
with $depth > 1$ and $l_0 = [0]$.
"""
sub_list = [0]
for d in range(1, depth):
sub_list = [d, sub_list]
return sub_list
这给出了:build_deep_list(5)
>>> [4, [3, [2, [1, [0]]]]]
。