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

Question

我从 Google 发布的速成课程开始自学 Python。其中一个练习题是编写一个函数，它接受 2 个 sorted 列表，将它们合并在一起，然后 returns 一个排序列表。最明显的解决方案是：

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

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

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

Efficient solution for merging 2 sorted lists in Python

python

arrays

sorting

list

performance-testing