为什么堆比 K 最近点到原点的排序慢？

Question

编码任务是here

堆解决方案：

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]

根据here的解释，Python的heapq.nsmallest是O(n log(t))，而Python List.sort()是 O(n log(n))。但是我的提交结果显示sort比heapq快。这怎么发生的？理论上是相反的吧？

Answer 1

让我们选择 Big-O 符号的定义 from the Wikipedia:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

...

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

所以 Big-O 类似于：

所以当你在小 ranges/numbers 上比较两个算法时，你不能强烈依赖 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 排序的快速排序是一个因素。这里的另一个因素是堆操作不像合并排序和插入排序那样 cache-friendly（tim 排序是这两者的混合）。

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

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

每次你在 adding/removing 元素 to/from 堆之后进行渗透 up/down 操作时，它会尝试访问远离 parent/children 的节点当前索引。这不是 cache-friendly。这也是堆排序通常比快速排序慢的原因，尽管它们在渐近上是相同的。

为什么堆比 K 最近点到原点的排序慢？

Why is heap slower than sort for K Closest Points to Origin?

python

algorithm

sorting

complexity-theory

heapq