2016-11-06 13 views
0

私は楽しいためのアルゴリズムについて学ぶ初心者です。私はPythonでマージソートを実装しようとしています。非常に異なる実行中のTImesを持つMergeSortの2つの実装

以下は私の実装です。私は100000リストをフィードすると非常に遅いです。

def mergesortedlist(L, R): 
    LR = [0]*(len(L)+len(R)) ##merged output (LR combined) 
    i= 0  ##counter for left side 
    j= 0  ##counter for ride side 
    k = 0 
    while i <= len(L) and j <= len(R): 

     if i == len(L): 
      LR[k:]= R[j:] 
      return LR 

     elif j == len(R): 
      LR[k:] = L[i:] 
      return LR 
     elif L[i] < R[j]: 
      LR[k]= L[i] 
      i+=1 
      k+=1 
     else: ##left side is bigger than right side 
      LR[k]=R[j] 
      j+=1 
      k+=1 

def mergesort(N): 

    if len(N) <= 1: 
     return N 
    else: 
     sub1 = N[0:round(len(N)/2)] 
     sub2 = N[round(len(N)/2):] 
     return mergesortedlist(mergesort(sub1), mergesort(sub2)) 

ここで私はこのウェブサイトから、どこかにオンラインで見つける実装(http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html

def mergeSort(alist): 
    print("Splitting ",alist) 
    if len(alist)>1: 
     mid = len(alist)//2 
     lefthalf = alist[:mid] 
     righthalf = alist[mid:] 

     mergeSort(lefthalf) 
     mergeSort(righthalf) 

     i=0 
     j=0 
     k=0 
     while i < len(lefthalf) and j < len(righthalf): 
      if lefthalf[i] < righthalf[j]: 
       alist[k]=lefthalf[i] 
       i=i+1 
      else: 
       alist[k]=righthalf[j] 
       j=j+1 
      k=k+1 

     while i < len(lefthalf): 
      alist[k]=lefthalf[i] 
      i=i+1 
      k=k+1 

     while j < len(righthalf): 
      alist[k]=righthalf[j] 
      j=j+1 
      k=k+1 
    print("Merging ",alist) 

alist = [54,26,93,17,77,31,44,55,20] 
mergeSort(alist) 
print(alist) 

は、それは非常に高速だのです。

私の言うことは、私の実装もO(Nlog(N))なので、なぜ私の方がはるかに遅いのですか?

ありがとうございました。

乾杯!

+0

パフォーマンス差の測定方法を示すことはできますか? – sal

答えて

0

私は巨大なパフォーマンスの違いは見られません:1,000sのランダムフロートに対して7.3sと5.4sです。しかし、2番目の方が速いのは正しいです。

時間の経過を確認するためにプロファイルする方法は次のとおりです。

python -m cProfile -s time mergesort.py 

あなたからの出力:

999999 8.517 0.000 11.088 0.000 mergesort.py:2(mergesortedlist) 
1999999/1 2.735 0.000 14.151 14.151 mergesort.py:25(mergesort) 
84184856/84184834 2.725 0.000 2.725 0.000 {len} 
1999998 0.174 0.000 0.174 0.000 {round} 

2つ目:

ncalls tottime percall cumtime percall filename:lineno(function) 
1999999/1 7.377 0.000 8.721 8.721 mergesort2.py:1(mergeSort) 
40499148/40499126 1.344 0.000 1.344 0.000 {len} 

あなたはあなたがlen()とラウンドを(呼び出しでより多くの時間を費やしている参照)。

また、2番目の配列は参照渡しの配列で動作し、配列は配列を返します。そのコピーには時間がかかります。あなたは初心者なので、レビューするのが理にかなっていますdifference

0

私の2セントです。 私のテストでは、round()またはlen()の機能は実行時間に大きく影響しません。 私は問題が次のようだと思う:各mergesortedlist()コールでは、新しいリストを作成します。 私はIPythonの%%timeit

L = N[0:round(len(N)/2)] 
R = N[round(len(N)/2):] 
LR = [0]*(len(L)+len(R)) 

2,000,000要素と、このコードをテスト - > 10のループ、3の最高:ループあたり34.4ミリ
1,000,000要素 - > 100のループ、3の最高:ループあたり17.2ミリ
50万要素 - > 100のループ、3の最もよい:ループあたり8.3ミリ
25万要素 - > 100のループ、3の最もよい:ループ当たり3.49ミリ
125,000要素 - 、> 1000のループ、3の最もよい:ループ
当たり1.25ミリ62,500個の要素 - > 1000個のループ、最高3個:ループあたり526μs
など...

そして、Mergesortの最悪のケースはO(N * logN)です。 (この事実は、最初のソート関数を乱数に適用した場合とソートした数値に2番目のソート関数を適用した場合を拒否します)。

関連する問題