高效的列表排序：使用堆代替标准排序速度较慢

Question

我正在尝试创建一种更有效的方法来对 python 中的列表和字典进行排序，并遇到了Efficient data Structurekeepingingobjectsonmultiplekeys。建议的解决方案是使用heapq模块。

然而，在我的测试中，堆似乎比原生 Python 排序算法慢两倍。下面是我用来做简单测试的代码。结果例如：

堆： 0.005993366241455078

标准： 0.0020036697387695312

有没有办法真正使用堆并提高性能，正如上面链接的帖子声称的那样？该代码会是什么样子？

这是测试它的代码：

import  random
import time
from heapq import *

standardlist = []
heaplist = []
for i in range(10000):
    num = random.randint(0,10000)
    standardlist.append(num)
    heappush(heaplist, num)

# Standard sorting method:
start_time = time.time()
sorted_list = sorted(standardlist)
finish_time_1 = time.time() - start_time

# Heap sorting method:
start_time = time.time()
heap_sorted_list = [heappop(heaplist) for i in range(len(heaplist))]
finish_time_2 = time.time() - start_time

print("Standard Finish Time:", finish_time_1)
print("Heap Finish Time:", finish_time_2)

Answer 1

当您有一个随时间变化（通过插入和删除）的集合，并且在每个时刻您都希望快速访问当前集合中的最小条目并可能提取它时，堆数据结构可能是正确的解决方案。您链接的问答中有这样的要求。

\n

然而，如果目标只是对数据集进行一次排序，那么使用堆并不是最有效的。

\n

关于您的代码的一些注释：

\n

\n

• 填充堆的方式具有 O(log) 时间复杂度。首先填充列表，然后调用heapify它会更有效：时间复杂度为 O()。诚然，这与您执行的计时无关，但它也会减少代码：

  \n

  standardlist = [random.randint(0,100000) for _ in range(1000000)]\nheaplist = standardlist[:]\nheapify(heaplist)\n

  \n
\n

• sorted是本机 Python 函数，该部分可以依赖已编译的 C 代码sort。用 Python 编写的显式循环无法打败它。

  \n
\n

• 尽管堆排序具有最佳时间复杂度，但实现良好的快速排序通常比堆排序快 2\xe2\x80\x933 倍。另请参见快速排序与堆排序。Python实际上使用了高度优化的排序算法。

  \n
\n

• 您的代码仅执行一项测试，并且会在几毫秒内完成。这并没有给出很有代表性的结果。最好多次重复测试并取平均值。

  \n
\n

\n