蟒蛇Mergesort - 太慢？

我想學習合併排序，但我不確定我是否正確。它的工作原理和我試圖優化這個例如與leftpop deques，但我仍然得到的時間比內置sorted（）函數慢大約4倍。這是否應該發生？還是我錯過了一些明顯的瓶頸？蟒蛇Mergesort - 太慢？

import random 
from time import time 
from collections import deque 

unsorted = [random.randint(0, 1000) for r in xrange(101101)] 


def merge_sort(unsorted_list): 
    length = len(unsorted_list) 
    if length <= 1: 
     return unsorted_list 

    left = unsorted_list[:length/2] 
    right = unsorted_list[length/2:] 

    left_sorted = deque(merge_sort(left)) 
    right_sorted = deque(merge_sort(right)) 

    new = [] 
    while left_sorted and right_sorted: 
     if left_sorted[0] < right_sorted[0]: 
      new.append(left_sorted.popleft()) 
      if not left_sorted: 
       new += right_sorted 
     else: 
      new.append(right_sorted.popleft()) 
      if not right_sorted: 
       new += left_sorted 
    return new 


s = time() 
print merge_sort(unsorted) 
e = time() 
print e - s 

s = time() 
print sorted(unsorted) 
e = time() 
print e - s

編輯：下面一個有點優化版本：

def merge_sort(unsorted_list): 
    length = len(unsorted_list) 
    if length <= 1: 
     return unsorted_list 

    left = unsorted_list[:length/2] 
    right = unsorted_list[length/2:] 

    left_sorted = deque(merge_sort(left)) 
    right_sorted = deque(merge_sort(right)) 

    new = [] 

    new_append = new.append 
    left_pop = left_sorted.popleft 
    right_pop = right_sorted.popleft 

    while left_sorted and right_sorted: 
     if left_sorted[0] < right_sorted[0]: 
      new_append(left_pop()) 
     else: 
      new_append(right_pop()) 

    if not left_sorted: 
     new += right_sorted 
    if not right_sorted: 
     new += left_sorted 

    return new

來源

2017-03-29 iknownothing

比高度優化的內建C函數慢4倍。 –

該死的你是對的。我完全忘了CPython不是用Python編寫的。那麼，至少這裏是一些谷歌mergesort python的代碼。 – iknownothing

我投票結束這個問題作爲題外話，因爲這應該進入CodeReview.Stackexchange.com – Prune

有一些你可以緩存名稱查找。我看到你做了很多.append和.popleft。嘗試將它們存儲在局部變量中：

new_append = new.append 
left_pop = left_sorted.popleft 
right_pop = right_sorted.popleft 

... 

new_append(left_pop()) 

... 

new_append(right_pop())

這應該刪除一些操作碼。

此外，您的if not left_sorted:和right_sorted邏輯可能會移到循環外部。

如果您始終使用索引變量 - left [li]和right [ri]，而不是left [0]和right [0]，則可能不需要使用出隊。一次銷燬一個子列表是沒有用的。（我不知道這是否會加快速度，但是出列隊列可能會緩存起始索引並按照這種方式進行。）

最後的if語句應該是正數，而不是負數。有可能（甚至可能）同時耗盡兩者。

來源

2017-03-29 22:16:27

嘿，那實際上有幫助。 if語句是我的一個明顯的錯誤。姓名查找我不會想到，但他們很好。我現在比排序（）慢了大約2.5倍，這很酷。謝謝。 – iknownothing

更新問題。 –

因爲我一個一個地做，所以我不會同時用完兩者，所以我會在每個數字被排序後檢查條件，如果有任何列表爲空，我會把剩下的結束。列表上的AFAIK pop（0）比deque上的leftpop（）慢得多。 – iknownothing

這很慢，因爲您複製了兩個半（未排序）列表而不是使用索引。

def merge(liste): 
    def order(start1,middle,stop2): 
     stop1=start2=middle 
     index1=start1 
     index2=start2 
     merge_list=[] 
     while index1<stop1 and index2<stop2: 
      if liste[index1]<liste[index2]: 
       merge_list.append(liste[index1]) 
       index1+=1 
      else: 
       merge_list.append(liste[index2]) 
       index2+=1 
     if index1<stop1: 
      merge_list.extend(liste[index1:stop1]) 
     if index2<stop2: 
      merge_list.extend(liste[index2:stop2]) 
     liste[start1:stop2] = merge_list 

    def sort(start,stop): 
     middle=(start+stop)//2 
     if start+1<stop: 
      sort(start,middle) 
      sort(middle,stop) 
      order(start,middle,stop) 

    sort(0,len(liste)) 
    return liste

來源

2017-03-29 22:36:19 user4624500

我試着優化代碼，如下所示，但它只是更快一點。

我做了一次「分配」的工作清單，然後通過使用兩個歸併排序功能，一個是分類成最初的名單，進行排序進入工作列表中的其他副本避免回。

在我的系統中，英特爾3770K 3.5ghz，Windows 7 64位，Python 2.7，排序100,000個整數時，上面的「優化」版本大約需要0.468秒，而下面的版本大約需要0.320秒。解釋代碼的開銷似乎是瓶頸。在C++中編譯的相同算法大約需要0.0067秒，大約快47倍。

import random 
from time import time 

def sort(a): 
    b = a        # "allocate" b 
    msa2a(a, b, 0, len(a))    # merge sort a to a 

def msa2a(a, b, low, end):    # merge sort a to a 
    if((end - low) < 2):    # if < 2 elements 
     return       # return 
    mid = (low+end)//2     # set mid point 
    msa2b(a, b, low, mid)    # merge sort left half to b 
    msa2b(a, b, mid, end)    # merge sort right half to b 
    mrg(b, a, low, mid, end)   # merge halves from b to a 

def msa2b(a, b, low, end):    # merge sort a to b 
    if((end - low) < 2):    # if < 2 elements 
     b[low] = a[low]     # copy 1 element from a to b 
     return       # return 
    mid = (low+end)//2     # set mid point 
    msa2a(a, b, low, mid)    # merge sort left half to a 
    msa2a(a, b, mid, end)    # merge sort right half to a 
    mrg(a, b, low, mid, end)   # merge halves from a to b 

def mrg(a, b, ll, rr, ee):    # merge a pair of runs from a to b 
    o = ll        # o = b[]  index 
    l = ll        # l = a[] left index 
    r = rr        # r = a[] right index 
    while True: 
     if(a[l] <= a[r]):    # if a[l] <= a[r] 
      b[o] = a[l]     # copy a[l] 
      o += 1 
      l += 1 
      if(l < rr):     # if not end of left run 
       continue    #  continue (back to while) 
      b[o:ee] = a[r:ee]   # else copy rest of right run 
      return      #  and return 
     else:       # else a[l] > a[r] 
      b[o] = a[r]     # copy a[r] 
      o += 1 
      r += 1 
      if(r < ee):     # if not end of right run 
       continue    #  continue (back to while) 
      b[o:ee] = a[l:rr]   # else copy rest of left run 
      return      #  and return 

# test sort 
a = [random.randint(0, 1000) for r in xrange(100000)] 
s = time() 
sort(a) 
e = time() 
print e - s 

# check to see if data was sorted 
f = 0 
for i in range (1 ,len(a)-1): 
    if(a[i-1] > a[i]): 
     f = 1 
     break 
if(f == 0): 
    print("sorted") 
else: 
    print("error")

來源

2017-03-29 23:04:21 rcgldr

蟒蛇Mergesort - 太慢？

回答

相關問題