很遗憾,您不被允许使用内置函数
zip
,必须使用递归。这很不幸。您的教授或导师(如果这不是学术项目,则道歉假设)正在强制您错误地应用递归。这就像试图用香槟瓶而不是灭火器灭火一样。当您完成课程后,请使用内置函数和迭代!
一般来说,在Python中对列表进行操作时,迭代几乎总是正确的工具。有其他问题
递归实际上是合适的,比如遍历树,因为递归步骤通过亚线性因子将问题分解。这里没有分治。
递归是迭代的不良替代品的一些原因:
- 每次递归调用都需要额外的计算工作来分配和销毁调用帧,而循环则没有这个问题。
- 默认情况下,CPython 的递归限制约为 1000,因此如果您的列表长度超过了这个值(对于任何非平凡应用程序都会出现这种情况),程序将崩溃。您不能无限地扩展调用堆栈大小,因此
sys.setrecursionlimit
是一种不安全的 hack。
- 调用帧之间不共享状态,因此您被迫做一些丑陋的事情,比如在参数中添加索引或在每次调用时使用切片复制整个列表(就像您正在做的那样),最坏的情况下会导致不必要的二次复杂度(就像这里一样),或者只是笨拙的代码(例如,如果您想构建一个结果列表,就像这里一样)。
一些语言支持尾递归优化,适合编写这样的算法,但Python不是其中之一。
话虽如此,我理解这是一个教学练习,所以让我们一起玩耍并学习递归的知识。
我还想在深入讨论之前提供一些通用的编程技巧。
当你陷入算法的困境时,尝试简化问题。看看是否可以合并两个长度相等的列表,一旦这样做成功后,再添加列表长度不同的额外要求。这会消除检查一个列表为空而另一个不为空的情况,并且通常会使问题更容易理解。当你着手解决完整的问题时,你已经有了一个子问题的最小工作代码以及从解决较小问题空间中获得的经验和模式。
这里的代码似乎是你已经跳过去了,在没有测试的情况下编写出来,并做出了一系列单独看起来不合理的决定和假设。采取更小的步骤。
打印(或使用调试器)来检查每个框架中的值。在小例子中解决算法问题。
必读文章:
Eric Lippert - 如何调试小程序。
让我们检查一些代码中的小问题,并逐步解决大问题。
elif
的顺序重要吗?
如果分支条件都是不相交的,那么顺序就不重要了,例如:
if foo == "a": return 0
if foo == "b": return 1
if foo == "c": return 2
由于foo
不能同时是"a"
、"b"
和"c"
,因此这些分支是互斥的。当您可以得到它时,这是一个很好的简化假设(上面的代码可以重构为表格查找,完全删除条件链)。
但是如果您有依赖检查,例如
if len(l1) == 0:
pass
elif len(l2) == 0:
pass
elif len(l1) == 0 and len(l2) == 0:
pass
那么顺序很重要。首先应该检查两个都为空的情况(你可以使用Pythonic的 if lst:
和 if not lst:
来检查它们的空值)。
考虑其中一个列表为空的情况:
if len(l1) == 0:
return l2[0] + zippa(l1,l2[1:])
此时,您只需
return l2
- 当一个列表为空时,您只需要返回非空列表而不是逐个删除它。由于分支的顺序,
l2
不能保证有一个元素 - 它可能为空。
接下来,代码
elif len(l1) == 0 and len(l2) == 0:
return 0
变量类型不一致。我们试图返回一个列表,因此两个空列表的基本情况合并为一个空列表,而不是整数0。这应该是return []
,这样调用者就可以使用+
连接两个列表,而不是[] + 0
,这会引发TypeError。在类型化的语言中,您无法编写此代码,即使在动态类型的语言中,混合类型通常也是反模式,即使它能够工作。
在主递归代码中,切片l1[1:0]
始终给出一个空列表。将问题分解成小块,并在repl中尝试测试我们的假设,我们看到:
>>> [1,2,3][1:0]
[]
显然,这不是你想要的。看起来你在尝试编码“alternation”模式,所以你可能只想将第一个元素作为列表删除:
>>> [1,2,3][0:1]
[1]
>>> [1,2,3][:1]
[1]
其次,我不清楚
zippa(l1[:1],l2) + zippa(l1,l2[:1])
模式是如何工作的。一旦第一个元素在那里,任何逻辑都不会将其删除,我们就会陷入无限循环。对于线性列表算法来说,并不需要生成多个递归调用并合并结果。从两个列表中各自取出一个元素进行单次调用的合并似乎最容易——递归中没有规则禁止这样做。
回到切片问题上,那是不必要的二次复杂度——只是为了把算法塞入递归中而进行了很多额外的工作。我们可以通过传递第三个参数作为索引到递归调用中来解决复杂度和切片问题。这可以是一个默认参数,也可以是添加在内部或辅助函数上。
作为一个最终的优化点,同时也使代码更简单:每次列表上的
+
操作都会分配一个全新的列表!如果我们在每帧上都这样做,复杂度就回到了二次方。如果要用于任何
非平凡目的,合并列表只能涉及恒定数量的分配(最好是一个)。这可以通过在递归调用中传递单个结果列表来完成,在第一次调用时将其分配一次。
这是代码:
def merge_iterables(a, b, i=0, result=None):
if result is None:
result = []
if i < len(a) and i < len(b):
result.append(a[i])
result.append(b[i])
merge_iterables(a, b, i + 1, result)
else:
result.extend(a[i:])
result.extend(b[i:])
return result
如果您不想将这些参数暴露给调用者,请使用内部或帮助函数,这在递归中很典型:
def merge_iterables(a, b):
result = []
def merge(i=0):
if i < len(a) and i < len(b):
result.append(a[i])
result.append(b[i])
merge(i + 1)
else:
result.extend(a[i:])
result.extend(b[i:])
merge()
return result
请注意,尽管我在切片,但这是一次性的基本情况,因此这是恒定的复杂度(并且一个或两个切片无论如何都是空的)。您可以使用传统的
range
循环来避免这些分配,但这是一种过早的优化。
虽然这不是你的任务范围,但像这样的算法应该适用于任意数量的列表。通过添加循环来实现非常容易:
def merge_iterables(*its):
result = []
def merge(i=0):
for x in its:
if i < len(x):
result.append(x[i])
if any(i < len(x) for x in its):
merge(i + 1)
merge()
return result
这里的时间和空间复杂度是O(nm)。
最后,生成器是一种处理可迭代算法的Pythonic方式。 itertools
使用生成器来处理所有内容,跟随其步伐是很好的选择。生成器为调用者提供了最大的灵活性:它们可以使用相同的算法来合并,比如说,可迭代对象的前一半,或者在时间上、懒惰地、以内存高效的方式执行它(这些用例是你希望你的算法使用恒定空间的动机的一部分!)
def merge_iterables(*its):
def merge(i=0):
for x in its:
if i < len(x):
yield x[i]
if any(i < len(x) for x in its):
yield from merge(i + 1)
yield from merge()
if __name__ == "__main__":
print(list(merge_iterables([1,2], [4,5,6,7], "a", "xyz")))
在这之后,如果还有任何疑问,可以尝试在一个包含1000个元素的列表上运行,这仍然是递归的人为和低效用例,因此您可能想查看我在经典主题
Pythonic way to combine two lists in an alternating fashion?中提出的问题的建议解决方案。
让我们对该答案中的一些代码以及本答案中的代码以及另一个答案中给出的二次解决方案进行基准测试。
import argparse
import copy
import dis
import inspect
import random
import sys
import timeit
from itertools import zip_longest
sys.setrecursionlimit(1350)
def merge_pythonic(*its):
return [x for y in zip_longest(*its) for x in y if x is not None]
def merge_iterables(*its):
result = []
def merge(i=0):
for x in its:
if i < len(x):
result.append(x[i])
if any(i < len(x) for x in its):
merge(i + 1)
merge()
return result
def zippa(*its):
if len(its) == 0:
return []
head_list, *rest_its = its
if head_list:
head, *rest = head_list
return [head] + zippa(*rest_its, rest)
else:
return zippa(*rest_its)
if __name__ == "__main__":
parser = argparse.ArgumentParser()
parser.add_argument("--n", type=int, default=1300)
parser.add_argument("--m", type=int, default=1300)
parser.add_argument("--trials", type=int, default=1000)
parser.add_argument("--dis", action="store_true")
args = parser.parse_args()
n = args.n
m = args.m
trials = args.trials
namespace = dict(its=[random.sample(range(n), k=n) for _ in range(m)])
funcs_to_test = [x for x in locals().values()
if callable(x) and x.__module__ == __name__]
print(f"{'-' * 30}\nn = {n}, {trials} trials\n{'-' * 30}\n")
for func in funcs_to_test:
fname = func.__name__
fargs = ", ".join(inspect.signature(func).parameters)
stmt = f"{fname}({fargs})"
setup = f"from __main__ import {fname}"
time = timeit.timeit(stmt, setup, number=trials, globals=namespace)
print(inspect.getsource(globals().get(fname)))
if args.dis:
dis.dis(globals().get(fname))
print(f"time (s) => {'%.16f' % time}\n{'-' * 30}\n")
即使不幸的是,我们不能使用超过一千个元素的更大测试(啊!递归!),结果很清楚:内置函数碾压了递归方法,而二次方并没有如预期那样扩展,即使在小输入上也是如此(实际迭代器通常可以有数十万、数百万或数十亿个元素或更多):
------------------------------
n = 1300, m = 1300, 1000 trials
------------------------------
def merge_pythonic(*its):
return [x for y in zip_longest(*its) for x in y if x is not None]
time (s) => 0.4278396000000000
------------------------------
def merge_iterables(*its):
result = []
def merge(i=0):
for x in its:
if i < len(x):
result.append(x[i])
if any(i < len(x) for x in its):
merge(i + 1)
merge()
return result
time (s) => 4.4487939000000001
------------------------------
def zippa(*its):
if len(its) == 0:
return []
head_list, *rest_its = its
if head_list:
head, *rest = head_list
return [head] + zippa(*rest_its, rest)
else:
return zippa(*rest_its)
time (s) => 40.0880948000000004
------------------------------
elif
)永远不会被执行,因为如果条件len(l1) == 0 and len(l2) == 0
成立,则第一个分支的条件len(l1) == 0
也将成立,因此将选择第一个分支(因为它是第一个)。 - Steflen(l1) == 0
为空时;你仍然将'l1'传递给一个递归调用'zippa(l1,l2[1:])'。如果你知道'l1'是空的,那就摆脱它吧!!! - Stef