Python heapq 与 sorted 的复杂度和性能比较

Question

我相对较新于使用Python（使用v3.x语法），并希望了解heapq和sorted的复杂性和性能方面的注意事项。

为贪心的“找到最佳作业调度”算法已经实现了基于heapq的解决方案。但是，我了解到可以使用“sorted”及operator.itemgetter()和reverse=True。

不幸的是，我找不到有关“sorted”与heapq预期复杂性和/或性能的任何解释。

- ofer.sheffer

---

不清楚你究竟想做什么。如果你正在寻找列表中最大的元素，max(L) 比创建堆要快得多，而且比调用 sorted 更快。 - Dan R

@DanRoche，抱歉如果这是一个愚蠢的问题，但是否有一种方法可以从具有max（L）的集合中删除/弹出？ - ofer.sheffer

如果L是一个列表，那么你可以通过L.remove(max(L))删除最大的元素。虽然这有点浪费，因为它进行了两次遍历，而实际上只需要一次，但它仍然比构建堆要快。 - Dan R

Answer 1

如果您使用二叉堆以顺序弹出所有元素，那么您所做的基本上就是堆排序。除了它的实现是纯python之外，它比sorted函数中的排序算法慢。

如果需要动态添加元素，即添加和插入可能以未指定的顺序进行，则heapq比sorted更快。在任何堆中保留内部顺序的添加新元素比每次插入后重新排序数组更快。

如果稍后需要按顺序检索所有元素，则sorted更快。

它们唯一可以竞争的问题是，如果您需要从集合中获取最小（或最大）元素的某些部分。虽然有专门的算法处理这种情况, 但是heapq或sorted哪个更快取决于初始数组的大小和您需要提取的部分。

- Odomontois

---

在这种情况下，我假定两者都已经被完美优化了，并且你所说的一切都是正确的。但是，如果我想要测试复杂度和性能以确保哪一个比另一个更快，我该如何做？ - ofer.sheffer

优化规则

1. 不要优化。
2. 还不要优化……
3. 先进行性能分析。我对创建一个包含10,000个随机数并调用sorted函数以及创建另外10,000个数字并使用heapq.heappush函数构建列表的性能进行了快速而简单的分析，结果时间相差28%。这听起来很惊人，但是如果你看一下数量级：每个元素大约需要230纳秒（哪种算法？我很难找到一种情况，其中该选择占主导地位）。

- msw

Answer 2

heapq中的nlargest()和nsmallest()函数最适合在你想要找到相对较少的项目时使用。如果你只想找到单个最小或最大值，那么使用min()和max()是最适合的，因为它更快，并使用sorted然后切片。如果你正在查找N个最小或最大项，而且N相对于集合的总大小较小，这些函数提供了更好的性能。尽管在你的代码中使用heapq并不是必须的，但它是一个有趣的主题和值得学习的课题。

- vikas0713

Answer 3

heapq是一个以二叉堆为基础实现的工具。需要注意以下关键点，涉及到二叉堆和heapq：

1. 不支持搜索操作
2. 平均插入时间为常数
3. 平均删除时间为O(log n)

更多二叉堆信息请参考：http://en.wikipedia.org/wiki/Binary_heap

sorted是一个不同的概念，它返回一个排好序的列表，而heapq则是一个你需要不断使用的数据结构，可以通过sorted进行排序。

更多sorted信息请参考：https://docs.python.org/3.4/library/functions.html#sorted

你具体想要实现什么功能？

回复OP评论：

为什么你认为一定需要heapq？二叉堆是一种特殊的数据结构，根据你的需求，很可能并不需要它。

你似乎非常关注性能问题，但是并不清楚为什么。如果某个东西的“性能不好”，但是其总时间不重要，那么在大局上就无所谓了。在总体情况下，dict或list通常都能很好地执行。你为什么认为一定需要heapq？

我想知道这是否属于不要让完美成为敌人的好类型的情况。

使用C扩展编写Python是一种保留给真正需要性能的情况下的利基用例。（例如，如果你处理大文件并且性能是主要问题，则使用C扩展的XML解析器可能比纯Python更好）。

关于在复杂结构中保持玩耍时，使用sorted进行排序并通过.append()添加元素是否更快：

我仍然不清楚这里的用例是什么。如我上面提到的，sorted和heapq实际上是两个不同的概念。

你所关注的性能问题是针对什么使用场景的？（如果没有其他未指定的因素，我认为你可能过分强调了代码中最佳性能的重要性。）

- khampson

---

平均来说，插入操作的时间复杂度是固定的；通常情况下为O(log n)。（使用摊销分析，它们也可以被视为常数时间复杂度，因为n次插入操作总共需要O(n)的时间。） - chepner

是的，我编辑了我的回复以反映平均值；我无意中省略了它。 - khampson

@ken-hampson，我的课程有许多不同的作业。如果是超基本情况：一次排列以弹出最小值。我可以假设“sorted”是最好的选择吗？实现是什么？此外，还有“用C编写”/“纯Python”性能相关概念，这对我来说是相当新的。在复杂的情况下，保持结构不断变化：使用排序和通过.append()添加元素可能更快吗？希望这能解决我的疑虑。 - ofer.sheffer

在回答中添加了额外的信息以回答问题。 - khampson

@chepner，你关于n次插入的摊销复杂度的说法是不正确的，至少如果你使用摊销的通常意义，即“在所有操作中平均最坏时间”。特别是，如果元素按相反的排序顺序插入，则每次插入的摊销成本实际上为Ω(log n)。你可能会混淆一次性构建整个堆的O(n)成本。 - Dan R

@KenHampson，感谢您的建议。我目前正在尝试了解尽可能多的选项，以便获得最佳结果，而且实现起来不需要太长时间。从这个意义上说，我理解您所说的完美是敌人的观点。另外：请参见我在给Odomontois的留言。 - ofer.sheffer