Python heapq 与预排序列表的排序速度

Question

我有相当多的 n=10000 个长度为 k=100 的排序列表。由于合并两个排序列表需要线性时间，我认为heapq.merge()在深度 log(n) 树中递归合并长度为 O(nk) 的排序列表比sorted()在 O(nklog( n) 中对整个事物进行一次排序更便宜nk)) 时间。

但是，该sorted()方法在我的机器上似乎快了 17-44 倍。它的实现是否sorted()比heapq.merge()经典合并的渐近时间优势快得多？

import itertools
import heapq

data = [range(n*8000,n*8000+10000,100) for n in range(10000)]

# Approach 1
for val in heapq.merge(*data):
    test = val

# Approach 2
for val in sorted(itertools.chain(*data)):
    test = val

Answer 1

CPythonlist.sort()使用自适应合并排序，它识别输入中的自然运行，然后“智能地”合并它们。它在利用多种预先存在的秩序方面非常有效。例如，尝试排序range(N)*2（在 Python 2 中）以增加 的值N，您会发现所需的时间在 中线性增长N。

因此，如果您迭代结果（而不是实现包含所有结果的有序列表）heapq.merge()，则此应用程序中唯一真正的优势是较低的峰值内存使用量。

事实上，与方法相比，list.sort()它更多地利用了特定数据中的结构heapq.merge()。我对此有一些见解，因为我编写了 Python 的list.sort();-)

（顺便说一句，我看到你已经接受了一个答案，这对我来说很好 - 这是一个很好的答案。我只是想提供更多信息。）

关于“更多优势”

正如评论中讨论的那样，list.sort()玩了很多工程技巧，可能会减少需要的比较次数heapq.merge()。这取决于数据。这是对您问题中的特定数据会发生什么情况的快速说明。首先定义一个计算所执行比较次数的类（请注意，我使用的是 Python 3，因此必须考虑所有可能的比较）：

class V(object):
    def __init__(self, val):
        self.val = val

    def __lt__(a, b):
        global ncmp
        ncmp += 1
        return a.val < b.val

    def __eq__(a, b):
        global ncmp
        ncmp += 1
        return a.val == b.val

    def __le__(a, b):
        raise ValueError("unexpected comparison")

    __ne__ = __gt__ = __ge__ = __le__

sort()故意编写为仅使用<( __lt__)。这更像是一个意外heapq（而且，我记得，甚至在不同的 Python 版本中都不同），但结果证明.merge()只需要<和==. 所以这些是该类以有用的方式定义的唯一比较。

然后更改您的数据以使用该类的实例：

data = [[V(i) for i in range(n*8000,n*8000+10000,100)]
        for n in range(10000)]

然后运行这两种方法：

ncmp = 0
for val in heapq.merge(*data):
    test = val
print(format(ncmp, ","))

ncmp = 0
for val in sorted(itertools.chain(*data)):
    test = val
print(format(ncmp, ","))

输出有点惊人：

43,207,638
1,639,884

因此，对于此特定数据，sorted()所需的比较次数要少得多merge()。这就是它更快的主要原因。

长话短说

那些比较计数对我来说太显着了；-) 计数heapq.merge()看起来大约是我认为合理的两倍。

花了一段时间来追踪这个。简而言之，它是一种heapq.merge()实现方式的人工制品：它维护了一堆 3 元素列表对象，每个列表对象都包含来自可迭代对象的当前下一个值，所有可迭代对象中该可迭代对象的从 0 开始的索引（以打破比较关系)，以及那个可迭代的__next__方法。这些heapq函数都比较这些小列表（而不仅仅是可迭代对象的值），并且列表比较总是先通过列表查找第一个不是 的对应项==。

因此，例如，询问是否[0] < [1] 首先询问是否0 == 1。不是，所以接着问是否0 < 1。

正因为如此，<在执行期间进行的每次比较heapq.merge()实际上都会进行两次对象比较（一个==，另一个<）。该==比较是“浪费”的工作，在这个意义上，他们是没有逻辑需要解决的问题-他们只是“优化”（这恰好不是在这方面付出！）的列表进行比较，在内部使用。

因此，从某种意义上说，将heapq.merge()比较报告减半会更公平。但它仍然远远超过sorted()需要，所以我现在就让它放下;-)