为什么这个python代码需要这么久?
问题描述:
好吧,我有这比较合并排序和选择排序的Python代码,但它是永远。当从n = 0到90,000(列表大小)完成时,对列表排序只需要约3秒。按照这个逻辑,它将需要大约10 * 3 * 9秒(贯穿次数*持续时间*递增遍历[我们以10,000开始,然后是20,000,然后是30,000等))。然而,这需要更长的时间。为什么这个python代码需要这么久?
import time
import random
# Selection Sort Code #
def maxIndex(J):
return J.index(max(J))
def swap(LCopy, i, j):
temp = LCopy[i]
LCopy[i] = LCopy[j]
LCopy[j] = temp
# Implementation of selection sort
def selectionSort(L):
for i in range(len(L)-1, 1, -1):
j = maxIndex(L[0:i+1])
swap(L, i, j)
# Merge Sort Code #
# Assumes that L[first:mid+1] is sorted and also
# that L[mid: last+1] is sorted. Returns L with L[first: last+1] sorted
def merge(L, first, mid, last):
i = first # index into the first half
j = mid + 1 # index into the second half
tempList = []
# This loops goes on as long as BOTH i and j stay within their
# respective sorted blocks
while (i <= mid) and (j <= last):
if L[i] <= L[j]:
tempList.append(L[i])
#print L[i], "from the first block"
i += 1
else:
tempList.append(L[j])
#print L[j], "from the second block"
j += 1
# If i goes beyond the first block, there may be some elements
# in the second block that need to be copied into tempList.
# Similarly, if j goes beyond the second block, there may be some
# elements in the first block that need to be copied into tempList
if i == mid + 1:
tempList.extend(L[j:last+1])
#print L[j:last+1], "some elements in second block are left over"
elif j == last+1:
tempList.extend(L[i:mid+1])
#print L[i:mid+1], "some elements from first block are left over"
L[first:last+1] = tempList
#print tempList
# The merge sort function; sorts the sublist L[first:last+1]
def generalMergeSort(L, first, last):
# Base case: if first == last then it is already sorted
# Recursive case: L[first:last+1] has size 2 or more
if first < last:
# divide step
mid = (first + last)/2
# conquer step
generalMergeSort(L, first, mid)
generalMergeSort(L, mid+1, last)
# combine step
merge(L, first, mid, last)
# Wrapper function
def mergeSort(L):
generalMergeSort(L, 0, len(L)-1)
m = 10
n = 100000
n_increments = 9
baseList = [ random.randint(0,100) for r in range(n) ]
i = 0
while i < n_increments:
j = 0
sel_time = 0
mer_time = 0
while j < m:
# Do a Selection Sort #
x = time.clock()
selectionSort(baseList)
y = time.clock()
sel_time += (y - x)
random.shuffle(baseList)
# Do a Merge Sort #
x = time.clock()
mergeSort(baseList)
y = time.clock()
mer_time += (y - x)
random.shuffle(baseList)
j += 1
print "average select sort time for a list of", n, "size:", sel_time/m
print "average merge sort time for a list of", n, "size:", mer_time/m
j = 0
i += 1
n += 10000
答
因为您正在使用O(n^2)排序算法。这意味着如果您加倍n,算法运行时间会延长4倍。请注意,你开始在100,000而不是10,000
这是否适合http://codereview.stackexchange.com问题? – Acorn 2011-05-02 20:28:58
当你增加n时,你的代码实际上并没有增加列表的大小。将'baseList = [random.randint(0,100)for r in range(n)]'移到外部while循环中以解决此问题。 – 2011-05-02 20:33:05
@Acorn我不知道stackexchange网站存在... – 2011-05-02 20:38:18