为什么对于距离原点最近的 K 个点，堆比排序慢？

Question

编码任务在这里

堆解决方案：

import heapq
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2)

排序解决方案：

class Solution(object):
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key = lambda P: P[0]**2 + P[1]**2)
        return points[:K]

根据这里的解释，Python的

heapq.nsmallest

是O(n log(t))，Python的

List.sort()

是O(n log(n))。然而，我的提交结果显示

sort

比

heapq

更快。这怎么发生的？理论上是相反的，不是吗？

Answer 1

让我们从维基百科中选择 Big-O 表示法的定义：

大 O 符号是一种数学符号，描述当参数趋于特定值或无穷大时函数的极限行为。

...

在计算机科学中，大 O 表示法用于根据算法的运行时间或空间需求如何随着输入大小的增长而增长来对算法进行分类。

所以 Big-O 类似于：

因此，当您在小范围/数字上比较两种算法时，您不能强烈依赖 Big-O。我们来分析一下例子：

我们有两种算法：第一个是

O(1)，适用于 10000 个刻度，第二个是 O(n^2)。因此，在 1~100 范围内，第二个将比第一个更快（100^2 == 10000

，所以 

(x<100)^2 < 10000

）。但从 100 开始，第二个算法将比第一个慢。

您的函数中也有类似的行为。我用不同的输入长度对它们进行计时并构建了时序图。以下是大数函数的计时（黄色是

sort

，蓝色是 

heap

）：

可以看到

sort

比

heap

消耗的时间更多，而且时间增长得比

heap's

更快。但如果我们仔细观察较低的范围：

我们会看到，在小范围内，

sort

比

heap

更快！看起来 

heap

 有“默认”时间消耗。因此，具有较差 Big-O 的算法比具有较好 Big-O 的算法运行得更快，这并没有错。这只是意味着它们的范围使用太小，以至于更好的算法比更差的算法更快。

这是第一个图的计时代码：

import timeit
import matplotlib.pyplot as plt

s = """
import heapq
def k_heap(points, K):
    return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2)

def k_sort(points, K):
    points.sort(key = lambda P: P[0]**2 + P[1]**2)
    return points[:K]
"""

random.seed(1)
points = [(random.random(), random.random()) for _ in range(1000000)]
r = list(range(11, 500000, 50000))
heap_times = []
sort_times = []
for i in r:
    heap_times.append(timeit.timeit('k_heap({}, 10)'.format(points[:i]), setup=s, number=1))
    sort_times.append(timeit.timeit('k_sort({}, 10)'.format(points[:i]), setup=s, number=1))

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
#plt.plot(left, 0, marker='.')
plt.plot(r, heap_times, marker='o')
plt.plot(r, sort_times, marker='D')
plt.show()

对于第二个图，替换：

r = list(range(11, 500000, 50000))  -> r = list(range(11, 200))
plt.plot(r, heap_times, marker='o') -> plt.plot(r, heap_times)
plt.plot(r, sort_times, marker='D') -> plt.plot(r, sort_times)

Answer 2

正如已经讨论过的，在 python 中使用 tim sort 快速实现排序是一个因素。这里的另一个因素是堆操作不像合并排序和插入排序那样对缓存友好（蒂姆排序是这两者的混合）。

堆操作访问存储在远程索引中的数据。

Python 使用基于 0 索引的数组来实现其堆库。因此，对于第 k 个值，其子节点索引为 k * 2 + 1 和 k * 2 + 2。

每次在堆中添加/删除元素后执行向上/向下渗透操作时，它都会尝试访问远离当前索引的父/子节点。这对缓存不友好。这也是为什么堆排序通常比快速排序慢的原因，尽管两者渐近相同。