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

Question

我正在尝试创建一种更有效的方法来在 python 中对列表和字典进行排序，并遇到了高效的数据结构，使对象在多个键上排序。建议的解决方案是使用 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

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

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

对代码的一些评论：

• 填充堆的方式具有 O(𝑛log𝑛) 时间复杂度。首先填充列表，然后对其调用

  heapify

  的效率更高：时间复杂度为 O(𝑛)。诚然，这与您执行的计时无关，但它也会导致更少的代码：

  standardlist = [random.randint(0,100000) for _ in range(1000000)]
  heaplist = standardlist[:]
  heapify(heaplist)
  

• 重复调用

  heappop

  来获取排序列表比调用

  heapq.nsmallest

  函数慢，后者在本机完成这项工作（可能通过编译的 C 代码）：

  # Heap sorting method:
  start_time = time.time()
  heap_sorted_list = nsmallest(len(heaplist), heaplist)
  finish_time_2 = time.time() - start_time
  

通过后一个更改，您将获得更快的运行时间。但它仍然无法击败标准排序算法。 文档在提到

nsmallest

...

时也证实了这一点

...对于较小的 n 值，性能最佳。对于较大的值，使用

sorted()

函数会更有效。