堆排序算法与其他算法相比表现不佳

Question

我有两个heapsort算法。第一个是我写的，而第二个是从一些网站上取的。据我说，两者都有相同的逻辑，但第二个比第一个要好得多。为什么会发生这种情况？我能看到的唯一区别是，我的使用递归，而另一个使用迭代。单凭这一点就能成为区别因素吗？

我的代码：

def heapify(arr,i,n):
pivot = arr[i]   #the value of the root node
left,right = (i<<1)+1,(i<<1)+2  #indices of the left and right subtree root nodes
if right <= n-1:  #if right is within the array, so is left
if arr[left] <= pivot and arr[right] <= pivot:
return  #if both are less than the root node, it's already heapified
maximum = left if arr[left] >= arr[right] else right #else find which child has a higher value
arr[maximum],arr[i] = arr[i],arr[maximum]  #swap the root node with that child
return heapify(arr,maximum,n)  #make the changed child the new root and recurse
else:
if left <= n-1:  #right is outside the array, so check for left only
if arr[left] <= pivot:
return
arr[i],arr[left] = arr[left], arr[i]  #same logic as above
return heapify(arr,left,n)
else:
return
def heapit(array,n):
for i in range((len(array)-1)/2,-1,-1):  #all elements after (len(array)-1)/2 are the leaf nodes, so we have to heapify earlier nodes
heapify(array,i,n)
def heapsort(array):
n = len(array)
for i in range(n,0,-1):
heapit(array,i)  #make the array a heap
array[0],array[i-1] = array[i-1],array[0]  #swap the root node with the last element

另一个代码：

def HeapSort(A):
def heapify(A):
start = (len(A) - 2) / 2
while start >= 0:
siftDown(A, start, len(A) - 1)
start -= 1
def siftDown(A, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and A[child] < A[child + 1]:
child += 1
if child <= end and A[root] < A[child]:
A[root], A[child] = A[child], A[root]
root = child
else:
return
heapify(A)
end = len(A) - 1
while end > 0:
A[end], A[0] = A[0], A[end]
siftDown(A, 0, end - 1)
end -= 1

即使对于大小约为100000的小型阵列，差异也会变得很大。我只是通过将要排序的数组传递给函数HeapSort(list)或heapsort(list)来调用这两种代码。

编辑：

我把heapsort功能换成了这个：

def heapsort(array):
n = len(array)
heapit(array,n)
array[n-1],array[0] = array[0],array[n-1]
for i in range(n-1):
heapify(array,0,n-1-i)
array[n-i-2],array[0] = array[0],array[n-i-2]

这提供了类似的性能，但速度仍然较慢。对于一个价值100万美元的数组，结果几乎是20秒：4秒。还能做什么？

Answer 1

EDIT：我下面的备注可能解释了一个主要的减速，但最重要的是，您的算法不是heapsort。

在函数heapsort中，执行循环for i in range(n,0,-1)。这是n迭代，其中n是输入的大小。在这个循环中，您调用heapit，它循环for i in range((len(array)-1)/2,-1,-1)；这大约是n//2迭代。

n * (n // 2)=θ(n²)。换句话说，您有一个至少需要二次时间的算法，而第二个算法实现了真正的堆排序，它在O(nlgn)时间内运行。

/EDIT

递归很可能会扼杀性能，再加上对模块级定义的函数的调用。Python(至少是CPython)不是为递归程序优化的，而是为迭代程序优化的。对于heapify中的每个递归调用，CPython都必须执行以下七字节代码指令：

9         158 LOAD_GLOBAL              0 (heapify)
161 LOAD_FAST                0 (arr)
164 LOAD_FAST                6 (maximum)
167 LOAD_FAST                2 (n)
170 CALL_FUNCTION            3
173 RETURN_VALUE        
>>  174 POP_TOP             

(使用dis确定)。最后两条指令是在递归调用完成后执行的，因为Python执行而不是执行尾调用优化。

虽然这看起来并不昂贵，但LOAD_GLOBAL必须进行至少一次哈希表查找才能找到heapify，并且heapify、arr、maximum和i的引用计数必须递增。当递归调用完成时，引用计数必须再次递减。函数调用在Python中相当昂贵。

正如import this所说，"平面比嵌套好"：只要可能，就喜欢迭代而不是递归。