python - 在 Python 中合并 2 个排序列表的有效解决方案

Question

我正在从 Google 发布的速成类(class)开始自学 Python。其中一个练习题是编写一个函数，它接受 2 个已排序 列表，将它们合并在一起，并返回一个已排序列表。最明显的解决方案是:

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

显然上面的方法不是很有效，或者我是这么认为的，因为在后端，排序函数将不得不再次遍历整个输出列表。该问题要求一种有效的方法来实现此功能，大概它可以在巨大的列表上运行良好。我的代码与 Google 的答案类似，但我对其进行了一些调整以使其更快:

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

  result.extend(list1)
  result.extend(list2)
  return result[::-1]

原始的 Google 代码是从数组的前面弹出，但即使他们也注意到从数组的后面弹出比反转它更有效。

我尝试用包含 2000 万个条目的大型数组运行这两个函数，而简单愚蠢的组合和排序函数每次都以 3 倍以上的优势排在首位。不到 1 秒与超过 3 秒相比，应该是更有效的方法。

有什么想法吗？我错过了什么吗？它是否与解释我的代码时正在编译的内置排序函数有关(听起来不太可能)。还有其他想法吗？

Answer 1

这是因为 .sort() 的 Python 实现。 Python 使用一种叫做 Timsort 的东西.

Timsort 是一种归并排序。它的显着特征是它识别用于合并的预排序数据的“运行”。在现实世界的数据中，未排序数据中的排序运行非常常见，如果两个已排序数组已预排序，您可以在 O(n) 时间内对它们进行排序。这可以极大地减少通常在 O(nlog(n)) 时间内运行的排序时间。

所以发生的事情是，当您在 Python 中调用 list.sort() 时，它会识别两次运行的已排序数据 list1 和 list2 并在 O(n) 时间内合并它们。此外，此实现是编译的 C 代码，它比执行相同操作的解释型 Python 实现更快。