我一直在实现我自己的堆模块来帮助我理解堆数据结构。我了解它们是如何工作和管理的,但我的实现比标准的python heapq模块慢得多,同时执行堆排序(对于大小为100000的列表,heapq需要0.6s,而我的代码需要2s(最初是2.6s,通过从percDown中取出len()语句并传递长度,将其减少到2s,这样就不必每次方法调用自身时都计算len)。以下是我的实现:
def percDown(lst, start, end, node):
#Moves given node down the heap, starting at index start, until the heap property is
#satisfied (all children must be larger than their parent)
iChild = 2 * start + 1
i = start
# if the node has reached the end of the heap (i.e. no children left),
# return its index (we are done)
if iChild > end - 1:
return start
#if the second child exists and is smaller than the first child, use that child index
#for comparing later
if iChild + 1 < end and lst[iChild + 1] < lst[iChild]:
iChild += 1
#if the smallest child is less than the node, it is the new parent
if lst[iChild] < node:
#move the child to the parent position
lst[start] = lst[iChild]
#continue recursively going through the child nodes of the
# new parent node to find where node is meant to go
i = percDown(lst, iChild, end, node)
return i
popMin:弹出最小值(lst[0]),并重新排序堆
^{pr2}$把堆变成一个地方
def heapify(lst):
iLastParent = math.floor((len(lst) - 1) / 2)
length = len(lst)
while iLastParent >= 0:
ele = lst[iLastParent]
i = percDown(lst, iLastParent, length, lst[iLastParent])
lst[i] = ele
iLastParent -= 1
排序:使用上面的方法堆起给定的列表(不在原位)
def sort(lst):
result = []
heap.heapify(lst)
length = len(lst)
for z in range(0, length):
result.append(heap.popMin(lst))
return result
是我错误地增加了算法/堆创建的复杂性,还是仅仅是python heapq模块被严重优化了?我有一种感觉是前者,因为0.6秒对2秒是一个巨大的区别。在
0.6s与2.6s的差别比4x小。是不是太大了?在
没有足够的信息来回答。一个4倍的差异肯定是由算法错误引起的……但是如果不进行不同大小的测试,真的没有办法分辨。在
比如说,如果在1000时只有1.2倍的差异,100000时只有4倍的差异,1000000时只有12倍的差异,那么你的算法复杂度很可能会更差,这意味着你很可能出了问题,这是你需要解决的问题。在
另一方面,如果这三种尺寸都相差4倍,那么在你的开销中就有一个更大的常数乘数。很可能是因为您已经在Python中运行了一个内部循环,而(CPython)stdlib版本使用的是在C中执行相同循环的
_heapq
加速器模块,如Martijn Pieters' answer中所述。所以,你没做错什么。你也许可以进行一些微优化,但最终你必须要么用C重写代码的核心,要么在JIT优化的解释器中运行它,以接近stdlib的性能。实际上,如果你只是为了理解算法而写这篇文章,你不需要这么做。在另外,您可能需要尝试在PyPy中运行比较。它的stdlib大部分是用纯Python编写的,没有特殊的优化,但是经过优化的JIT编译器使它几乎与CPython中的本机C代码一样快。同样的JIT也会应用到你的代码中,这意味着你未优化的代码通常也和CPython中的本机C代码一样。当然,这并不能保证这一点,也不能改变这样一个事实:如果你想测试算法复杂度,你总是需要以不同的大小进行测试。在
Python
heapq
模块使用C扩展。你不能打败C代码。在从^{} module source code :
另请参见^{} C source 。在
相关问题 更多 >
编程相关推荐