蟒蛇Mergesort - 太慢？

Question

我想学习合并排序，但我不确定我是否正确。它的工作原理和我试图优化这个例如与leftpop deques，但我仍然得到的时间比内置sorted（）函数慢大约4倍。这是否应该发生？还是我错过了一些明显的瓶颈？

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 

Answer 1

有一些你可以缓存名称查找。我看到你做了很多.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语句应该是正数，而不是负数。有可能（甚至可能）同时耗尽两者。

Answer 2

这很慢，因为您复制了两个半（未排序）列表而不是使用索引。

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 

Answer 3

我试着优化代码，如下所示，但它只是更快一点。

我做了一次“分配”的工作清单，然后通过使用两个归并排序功能，一个是分类成最初的名单，进行排序进入工作列表中的其他副本避免回。

在我的系统中，英特尔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")