17

The coding task is here

The heap solution:

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)

The sort solution:

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]

According to the explanation here, Python's heapq.nsmallest is O(n log(t)), and Python List.sort() is O(n log(n)). However, my submission results show that sort is faster than heapq. How did this happen? Theoretically, it's the contrary, isn't it?

4

2 回答 2

26

让我们从 Wikipedia中选择 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)
于 2019-05-27T17:00:29.137 回答
2

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

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

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

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

于 2019-07-02T17:59:29.850 回答