Python heapq与排序的复杂性和性能 [英] Python heapq vs. sorted complexity and performance
问题描述
我是python的新手(使用v3.x语法)，并且希望您了解关于heapq和sorted的复杂性和性能的注释.
我已经为贪婪的查找最佳工作时间表"算法实现了基于heapq的解决方案.但是随后，我了解了将"sorted"与operator.itemgetter()和reverse = True一起使用的可能性.
遗憾的是，我无法找到有关已排序"与堆"的预期复杂性和/或性能的任何解释.
如果您使用二进制堆按顺序弹出所有元素，则您要做的基本上是 sorted函数中的算法排序慢，除了它的实现是纯python./p>
heapq比sorted更快，以防万一您需要动态添加元素，即添加和插入的顺序可能不确定.在每次插入之后在任何堆中添加保留内部顺序的新元素比每次插入后重新排序数组要快.
如果以后需要检索所有元素，则sorted更快.
他们可以竞争的唯一问题-如果您需要从集合中收集一些最小(或最大)的元素.尽管对于这种情况有一些特殊的算法，但是heapq或sorted会在此处更快取决于其大小您需要提取的初始数组和部分.
I'm relatively new to python (using v3.x syntax) and would appreciate notes regarding complexity and performance of heapq vs. sorted.
I've already implemented a heapq based solution for a greedy 'find the best job schedule' algorithm. But then I've learned about the possibility of using 'sorted' together with operator.itemgetter() and reverse=True.
Sadly, I could not find any explanation on expected complexity and/or performance of 'sorted' vs. heapq.
If you use binary heap to pop all elements in order, the thing you do is basically heapsort. It is slower than sort algorightm in sorted function apart from it's implementation is pure python.
The heapq is faster than sorted in case if you need to add elements on the fly i.e. additions and insertions could come in unspecified order. Adding new element preserving inner order in any heap is faster than resorting array after each insertion.
The sorted is faster if you will need to retrieve all elements in order later.
The only problem where they can compete - if you need some portion of smallest (or largest) elements from collection. Although there are special algorigthms for that case, whether heapq or sorted will be faster here depends on the size of the initial array and portion you'll need to extract.
这篇关于Python heapq与排序的复杂性和性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
