私は楽しいためのアルゴリズムについて学ぶ初心者です。私は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))なので、なぜ私の方がはるかに遅いのですか?
ありがとうございました。
乾杯!
パフォーマンス差の測定方法を示すことはできますか? – sal