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

Question

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

但是，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

CPython 的 list.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函数都比较这些小列表(而不是 只是 iterables 的值)，并且列表比较总是通过列表首先查找不是 == 的第一个对应项。 .

因此，例如，询问是否 [0] < [1] 首先询问是否0 == 1 .不是，所以然后它继续询问是否 0 < 1 .

因此，每个 <在执行 heapq.merge() 期间完成的比较实际上做了两个对象比较(一个 == ，另一个 < )。 ==比较是“浪费”的工作，从某种意义上说，它们在逻辑上不是解决问题所必需的——它们只是列表比较内部使用的“优化”(在这种情况下恰好不值得!)。

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