1

我正在尝试从 Google 的 Python 类中解决以下练习。

E. 给定两个按升序排序的列表，创建并返回按排序顺序排列的所有元素的合并列表。您可以修改传入的列表。理想情况下，解决方案应该在“线性”时间内工作，对两个列表进行一次遍历。

我正在使用以下方案方法（我希望我有汽车、cdr 和缺点！）。

def helper(list1, list2, result):
  if list1 == None:
    return result + list2
  elif list2 == None:
    return result + list1
  elif list1[0] < list2[0]:
    return helper(list1[1:], list2, result.insert(0, list1[0]))
  else:
    return helper(list1, list2[1:], result.insert(0, list2[0]))

def linear_merge(list1, list2):
  helper(list1, list2, [])

我得到的错误是，当结果为 [] 时，我似乎无法将元素插入结果中：

AttributeError: 'NoneType' object has no attribute 'insert'

但这在控制台中工作正常：

>>> b = []
[]
>>> b.insert(0, 4)
>>> b
[4]

我是 Python 的新手，所以我有两个问题：

  1. 关于 None 与 []，我缺少什么，以及如何使此代码正常工作？
  2. 如果 Python 不是用于 Scheme/Lisp 方法，那么解决这个问题的“Python 方法”是什么？这对我来说不太重要，因为我可以检查解决方案。

谢谢！

4

4 回答 4

5

list.insert返回无，而不是修改后的列表。

这需要helper更改为阅读

def helper(list1, list2, result):
  if not list1:
    return result + list2
  elif not list2:
    return result + list1
  elif list1[0] < list2[0]:
    return helper(list1[1:], list2, result + [list1[0]])
  else:
    return helper(list1, list2[1:], result + [list2[0]])

请注意对两个基本案例的更改。None和空列表[]不是一回事。测试列表是否为空的 Pythonic 方法是将列表视为布尔值：空列表为False，所有其他列表为True。

正如其他人在我之前注意到的那样，您需要显式返回helperin的返回值linear_merge。

于 2013-11-12T19:56:10.390 回答
3

第一个问题是[]和None不相等。

这会给您带来两个问题。

首先，您对递归基本案例的测试不起作用。如果您尝试测试列表是否为空，有多种方法可以做到：

if not list1:

if list1 == []:

if len(list1) == 0:

但是将其与它进行比较None不是其中一种方式。

第一个通常被认为是最 Pythonic 的（并且受到 PEP 8 样式指南的明确鼓励）。

其次，您显然是None在未向我们展示的代码中的某处显式调用此函数作为参数。不要那样做。当[]你的意思是[].

另一个问题是可变方法，如list.insert不返回变异对象，它们返回None. 所以，而不是这个：

return helper(list1[1:], list2, result.insert(0, list1[0]))

......你需要这样做：

result.insert(0, list1[0])
return helper(list1[1:], list2, result)

…或者使用非变异表达式代替：

return helper(list1[1:], list2, [list1[0]] + result)

然后，你什么都linear_merge没有return，所以它的价值将是None. 将其更改为：

return helper(list1, list2, [])
于 2013-11-12T19:56:22.333 回答
1

result.insert does not return a new list; it modifies an existing result in place. Thus you wind up passing None as the third argument to your nested helper() calls, because that's what result.insert returns - None.

Also note:

def linear_merge(list1, list2):
    helper(list1, list2, [])

Since you don't return anything from linear_merge, you're always going to get None as the result.

于 2013-11-12T19:58:17.870 回答
0

由于您要求提供 Pythonic 解决方案以及如何解决您的尝试，我将给您写一个单独的答案。

我会通过使用迭代器来做到这一点。在每个步骤中，您都会产生较低的值并拉下一个值。就像你在 Haskell 中做的那样。* 这实际上是线性时间，而且它也是惰性的。使用more-itertools：

def itermerge(i1, i2):
    i1, i2 = iter(i1), more_itertools.peekable(iter(i2))
    for v1 in i1:
        while i2 and i2.peek() < v1:
            yield next(i2)
        yield v1
    yield from i2

如果您需要 Python 2.x 或 3.2 兼容性，只需更改yield from i2with for v2 in i2: yield v2。

如果不清楚这是如何工作的，这里是最明确的版本，以准确显示每个步骤发生的情况：

def itermerge(i1, i2):
    i1, i2 = iter(i1), iter(i2)
    sentinel = object()
    v1, v2 = sentinel, sentinel
    while True:
        if v1 is sentinel:
            try:
                v1 = next(i1)
            except StopIteration:
                yield from i2
                return
        if v2 is sentinel:
            try:
                v2 = next(i2)
            except StopIteration:
                yield from i1
                return
        if v1 < v2:
            yield v1
            v1 = sentinel
        else:
            yield v2
            v2 = sentinel

如果您需要一个返回列表的函数，这很简单：

def linear_merge(l1, l2):
    return list(itermerge(l1, l2))

* 这有点开玩笑。虽然您可以在 Haskell 中编写该算法的几乎任何不可变版本，但与此解决方案最相似的版本可能不是您要编写的版本。

于 2013-11-12T20:08:10.503 回答