4

私は2つのheapsortアルゴリズムを持っています。最初のものは私が書いたもので、2 番目のものはどこかのウェブサイトから取ったものです。私によると、どちらも同じロジックを持っていますが、2 番目の方が 1 番目よりもパフォーマンスが優れています。これが起こっている理由は何ですか？私が見ることができる唯一の違いは、私のものは再帰を使用しているのに対し、他のものは繰り返し実行していることです。それだけで差別化要因になるの？

私のコード:

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

サイズが約 100,000 の小さな配列であっても、その差はかなり大きくなります。関数に並べ替える配列を渡すだけで、どちらかのコードを呼び出しています: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 秒です。他に何ができますか？

4

1 に答える 1

5

編集: 以下の私の発言は、大幅な速度低下を説明している可能性がありますが、最も重要なことは、アルゴリズムが 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²)。つまり、少なくとも 2 次時間がかかるアルゴリズムがあり、2 番目のアルゴリズムは O( nlg n) 時間で実行される真のヒープソートを実装しています。

/編集

モジュールレベルで定義された関数の呼び出しと組み合わせて、パフォーマンスを低下させているのは再帰である可能性が非常に高いです。Python (少なくとも CPython) は、再帰的なプログラムには最適化されていませんが、反復的なプログラムには最適化されています。の再帰呼び出しごとにheapify、CPython は次の 7 バイト コード命令を実行する必要があります。

  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 は末尾呼び出しの最適化を実行しないため、最後の 2 つの命令は再帰呼び出しが終了した後に実行されます。

これはコストがかからないように見えるかもしれませんが、 aLOAD_GLOBALはを見つけるためだけに少なくとも 1 回ハッシュ テーブルのルックアップを行う必要があり、 、、およびheapifyの参照カウントをインクリメントする必要があります。再帰呼び出しが終了したら、参照カウントを再度デクリメントする必要があります。関数呼び出しは、Python ではかなり高価です。heapifyarrmaximumi

import this「フラットはネストよりも優れている」と言われているように、可能な限り再帰よりも反復を優先します。

于 2012-09-20T11:54:59.220 に答える