Python的性能：堆

我想寫一個最佳函數，給出一個項目列表，返回一個重新排序的列表與top_k項目在開始（他們不需要自己命令）。我對剩餘元素的順序沒有任何限制，但理想情況下我希望他們按原始順序排列。Python的性能：堆

我試過3種方法。首先，一個在O（top_k * N）時間運行的簡單解決方案。其次，使用O（log（top_k）* N）（最慢）的最大元素的優先級堆，最後通過強力排序整個列表O（N * logN），結果是最快的）

def semi_sort_trivial(items, top_k=3): 
    for i in range(top_k): 
     maximum = items[i] 
     pos = i 
     for j in range(i+1, len(itemss)): 
      if maximum < events[j]: 
       pos = j 
       maximum = items[j] 
     # Swap maximum with the top i'th position under evaluation. 
     items[pos], items[i] = items[i], items[pos] 
    return items 

def semi_heap_sort(items, top_k=3): 
    lst = [] 
    heap_store = items[:top_k] 
    for item in items[top_k:]: 
     lst.append(heapq.heappushpop(heap_store, item)) 
    return heap_store + lst 

def semi_sort_usingsort(items, top_k=3): 
    lst = sorted(items)[-top_k:] 
    return lst + [item for item in items if item not in lst] 


In [7]: %timeit semi_heap_sort(range(20)) 
10000 loops, best of 3: 26.3 us per loop 

In [8]: %timeit semi_sort_trivial(range(20)) 
100000 loops, best of 3: 11 us per loop 

In [9]: %timeit semi_sort_usingsort(range(20)) 
100000 loops, best of 3: 5.89 us per loop

我很驚訝堆表現最差。我最初的猜測是恆定的因素太高。但在嘗試更大的範圍之後，我仍然遇到類似的性能問題。我期望堆能夠表現最好。任何指針？

感覺就像有一個更好的方法來解決這個問題。對於N = 20和k = 3的一般情況，N log N大約是20 * 5操作，我相信我們應該能夠在N log top_k或20 * 2操作中執行此操作。應該可以比semi_sort_usingsort方法做得更好。任何建議，使這種情況發生？

謝謝。

來源

2011-05-23 GeneralBecos

首先，你正在測試相當小的問題k = 3，n = 20。隨着數字的減小，python與C的速度變得更加重要。結果，基於sort（）的方法獲勝，因爲它爲該邏輯跳轉到C，而您的其他方法必須留在python中。

其次，你正在做一個排序列表。對已排序的項進行排序往往會導致排序算法出現異常行爲。一些算法在這種情況下表現出病態行爲。相比於實際對一個隨機列表進行排序，Python似乎很快對列表進行排序。

第三，函數heapq.nlargest返回來自可迭代的n個最大項。這是一個可以考慮的選擇。

第四，

def semi_heap_sort(items, top_k=L): 
    lst = [] 
    heap_store = items[:top_k]

你需要調用heapq.heapify（）上堆，以確保它遵循堆的規則。

for item in items[top_k:]:

您實際上正在生產一個新的列表，只比原來略短。這將需要相當長的時間。

 lst.append(heapq.heappushpop(heap_store, item)) 
    return heap_store + lst

這裏是相同的功能的優化版本：

編輯原始版本馬車。可悲的是，我的速度優勢消失:(它只有更好時，問題變得更大。

def mod_heap_sorta(items, top_k=L): 
    heap_store = items[:top_k] 
    heapq.heapify(heap_store) 
    remaining = itertools.islice(items, top_k, None) 
    leftovers = [heapq.heappushpop(heap_store, item) for item in remaining] 
    return heap_store + leftovers

我猜，當你試圖擴大數字，你增加了項目，但你的列表的大小並沒有擴大top_k的值，所有算法似乎對列表的大小都非常敏感，但是，semi_trivial_sort對top_k也非常敏感，對於k的小值，semi_trivial_sort快於semi_heap_sort，因爲常數因素

看來我的版本中最大的性能好處是避免重複項目列表，使用列表理解也有幫助，但是沒有達到相同的程度。 t可以通過改寫功能來使用地圖來代替。然而，地圖在PyPy上表現不佳，所以我避免了它。

來源

2011-05-24 01:46:39

謝謝！這是非常有用的:-) – GeneralBecos 2011-05-24 02:38:19

只是發現你的優化版本有一個錯誤，剩菜數組將永遠是空的。 – GeneralBecos 2011-05-24 03:51:07

@GeneralBecos，實際上它的空的堆_store – 2011-05-24 14:00:26

請參閱Selection Algorithm。

如果你能忍受的近似方法，你可以

直方圖數據O（N）
總和直方圖來獲得累積分佈O（直方圖桶數）

選擇所有數字> = XO（1）
選擇一個數字X在分佈的k/N部分O N）。

所以整個事情基本上是O（N）。（這並不意味着它很快，它只能說明它是如何擴展的。）

你可能會在選擇太多數字時犯錯。然後，如果你有太多的，做這一切在小集，這是O（K）

來源

2011-05-23 23:33:28

你可以試試另一件事情是修改忽略開始以比top_k更高的位置上的任何間隔快速排序。

來源

2011-05-24 00:41:10

Python的性能：堆

回答

相關問題