Python中用于列表线性合并的方法

Question

我正在完成Google的Python课程练习。其中一个练习是：

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

我想出的解决方案是：

    def linear_merge(list1, list2):
      list1.extend(list2) 
      return sorted(list1)

它通过了测试函数，但给出的解决方案是这样的：

    def linear_merge(list1, list2):
      result = []
      # Look at the two lists so long as both are non-empty.
      # Take whichever element [0] is smaller.
      while len(list1) and len(list2):
        if list1[0] < list2[0]:
          result.append(list1.pop(0))
         else:
          result.append(list2.pop(0))

      # Now tack on what's left
      result.extend(list1)
      result.extend(list2)
      return result

作为解决方案的一部分，包括以下内容：

注意：上述解决方案很可爱，但是使用标准Python列表实现时，list.pop(0)不是恒定时间，因此上述解决方案不是严格的线性时间。另一种方法使用pop(-1)从每个列表中删除最后一个元素，构建一个反向的解决方案列表。然后使用reversed()将结果放回正确的顺序。该解决方案在线性时间内运行，但更加丑陋。

为什么这两个解决方案如此不同？我有什么遗漏，还是它们过于复杂了？

- Megan Taylor

Answer 1

他们鼓励您思考合并两个排序列表的实际方法（算法）。假设您有两堆纸张，上面有姓名，每个人的名字都按字母顺序排列，并且您想要从它们中创建一个排序的堆栈。您不会只是把它们混在一起然后从头开始排序；那太麻烦了。您会利用每个堆栈已经排序的事实，因此可以从其中一个堆栈中取出优先的条目，然后将它们放入新的堆栈中。

- Tom Zych

---

好的，那很有道理。我猜他们只是觉得期望一个新手能想出那个解决方案有点奇怪。你能给我举个例子说明result.extend(list1) result.extend(list2)会实现什么效果吗？ - Megan Taylor

pop 从列表中移除一个项目并返回其值，因此您正在从每个列表中删除项目并将它们放入 result 中。初始循环运行的时间与 list1 和 list2 都包含任何内容一样长。当其中一个用完时，您只需取出另一个中剩下的任何内容并将其附加到 result 上；这就是 extend 的作用。 - Tom Zych

很高兴能帮到你。我猜你是新手程序员？这是一个很酷的世界，玩得开心！ - Tom Zych

他们期望你作为“n00b”能够想出解决问题的方法，因为他们期望你具备思考和解决问题的能力。如果你能够发现pop(0)在标准Python实现中不是以恒定时间运行的，那么你肯定不缺乏思考能力。对于这种情况，尝试从建模问题开始：拿一副牌，洗牌，切成两半，将每半排序，然后将这两半拼在一起进行排序 - 并思考你正在做什么。 - Karl Knechtel

顺便说一句，解决 pop(0) 问题的另一种简单方法是根本不要从子列表中删除项目，只需通过每个列表推进索引，将引用复制到结果列表中即可。 :) - Karl Knechtel

Answer 2

我最喜欢 @Abhijit 的方法。这是他代码片段的稍微更pythonic/易读版本:

def linear_merge(list1, list2):
    result = []

    while list1 and list2:
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

    return (result + list1 + list2)[-1::-1]

借助Python内置的功能，我们可以：

1. 无需使用len函数显式检查列表是否为空。
2. 可以合并/附加空列表，结果仍然不变，因此无需显式检查。
3. 我们可以组合多个语句（如果可读性允许），有时会使代码更紧凑。

- intel

Answer 3

result = []
while list1 and list2:
    result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

if len(list1):
    result += list1[-1::-1]
if len(list2):
    result += list2[-1::-1]

return result[-1::-1]

@Abhijit 和 @intel 的解决方案并不适用于所有情况，因为他们没有翻转原始列表中剩余的部分。如果我们有 list1 = [1, 2, 3, 5, 9, 11, 13, 17] 和 list2 = [6, 7, 12, 15]，他们的解决方案会给出[5, 3, 2, 1, 6, 7, 9, 11, 12, 13, 15, 17]，而我们想要的是[1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17]。

- jontaylor224

Answer 4

正如您所指出的，您的解决方案完美地运作。那么为什么要这么复杂呢？首先

理想情况下，该解决方案应该在“线性”时间内工作，对两个列表进行单次遍历。

好吧，您并没有明确地通过任何列表，但是您正在调用sorted()。那么sorted()会经过多少次列表呢？

嗯，我实际上不知道。通常，排序算法的操作时间大约为O(n*log(n))，但是看看Python文档中的这句话：

Python中使用的Timsort算法可以有效地执行多个排序，因为它可以利用数据集中已有的任何排序。

也许更了解timsort的人可以弄清楚。

但是他们在解决方案中所做的是利用他们知道他们有2个排序列表的事实。因此，他们不是从头开始使用sorted，而是逐个挑选元素。

- Owen

Answer 5

稍微改进但仍然不美观的解决方案（使用Python3.5）：

def linear_merge(list1: list, list2: list):
    result = []

    while len(list1) and len(list2):
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

    result += list1 if len(list1) else list2

    return result[-1::-1]

- Abhijit

Answer 6

def linear_merge(list1, list2):
     a= list1 + list2
     a.sort() 
     return a

- Fzed

Answer 7

你的解决方案是O(n log n)，这意味着如果你的列表长度增加10倍，程序所需时间将增加（大约）30倍。他们的解决方案只需要增加10倍的时间。

- Michael Lorton

---

对于给定的示例（已排序子列表），我认为Python的Timsort（类似于归并排序）是O（n）。 - agf

如果你的列表长度增加了10倍，程序所需时间将增加（大约）30倍。不；随着列表大小无限增长，运行时间的比率将趋近于10。你试图使用的公式只适用于O(n^k)类型的运行时间。 - Karl Knechtel

Answer 8

弹出列表的末尾，直到其中一个为空。我认为这是线性的，而且反转也是线性的。很丑，但是是一种解决方案。

def linear_merge(list1, list2):
  # NOT return sorted (list1 + list2), as this is not linear
  list3 = []
  rem = []
  empty = False

  while not empty:
    # Get last items from each list, if they exist
    if len (list1) > 0:
      a = list1[-1]
    else:
      rem = list2[:]
      empty = True

    if len (list2) > 0:
      b = list2[-1]
    else:
      rem = list1[:]
      empty = True

    # Pop the one that's largest onto the new list
    if not empty:
      if a > b:
        list3.append (a)
        list1.pop ()
      else:
        list3.append (b)
        list2.pop ()

  # add the (reversed) remainder to the list
  rem.reverse ()
  list3 += rem

  # reverse the entire list
  list3.reverse ()
  return list3

- Chris