为什么堆比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））。但是，我的提交结果显示排序比heapq快。这怎么发生的？从理论上讲是相反的，不是吗？

Answer 1

让我们从Wikipedia中选择Big-O符号的定义：

大O表示法是一种数学表示法，它描述自变量趋于特定值或无穷大时函数的限制行为。

...

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

因此，Big-O类似于：

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

我们有两种算法：第一种是O（1），可以精确地运行10000个滴答，第二种是O（n ^ 2）。因此，在1〜100的范围内，第二个会比第一个快（100^2 == 10000so (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。

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