这是出于对 python 中 heapq.py 模块的 nsmallest 和 nlargest 方法的好奇。
我在读它here在文档中。
文档没有说明它是如何在任何可迭代对象上这样做的(nsmalles/nlargest)。
这可能是一个愚蠢的问题,但我可以假设这些方法在内部创建一个可迭代数据结构的堆(可能使用“heapify”方法),然后返回 n 个最小/最大元素吗?
只是想证实我的结论。谢谢!
最佳答案
查找 n
的算法N
的可迭代项中的最小或最大项项目有点棘手。你看,你没有创建大小- N
min-heap 找到最小的项目。
取而代之的是,您制作了一个更小的尺寸- n
第一个 n
的最大堆项目,然后重复 pushpop
使用序列中的剩余项目对其进行操作。完成后,从堆中弹出项目并以相反的顺序返回它们。
这个过程需要O(N log(n))
时间(注意小的 n
)当然只有 O(n)
空间。如果 n
远小于 N
,它比排序和切片效率高得多。
heapq
module包含该算法的纯 Python 实现,但是当您导入它时,您可能会得到用 C 编写的代码的更快版本(您也可以阅读 the source for that,但除非您了解 Python C,否则它不太友好API)。
关于python-2.7 - nlargest 和 nsmallest ;堆 python ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33069490/