3 Quicksorts 函数 - 为什么 lambda 版本更慢?提供代码
3 Quicksorts Functions - Why is the lambda version slower? Code provided
我在测试快速排序运行时,发现 lambda 版本的快速排序速度较慢。
为什么 lambda 版本明显变慢?我已经尝试交换我调用的每个订单,但它似乎一直在变慢。是不是因为我每次都重新声明左、等和右,因为必须分配过滤器(相对于 appending/in 位置)?
import timeit
def qsort(list):
if len(list) > 1:
pivot = list[0]
left = filter(lambda x: x < pivot, list)
equal = filter(lambda x: x == pivot, list)
right = filter(lambda x: x > pivot, list)
return qsort(left) + equal + qsort(right)
else:
return list
def sort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
if begin >= end:
return
pivot = partition(array, begin, end)
quicksort(array, begin, pivot-1)
quicksort(array, pivot+1, end)
return array
print qsort([5,3,1,5,2,6])
print sort([5,3,1,5,2,6])
print quicksort([5,3,1,5,2,6])
print (timeit.timeit(lambda: qsort([5,3,1,5,2,6]), number=1000))
print (timeit.timeit(lambda: sort([5,3,1,5,2,6]), number=1000))
print (timeit.timeit(lambda: quicksort([5,3,1,5,2,6]), number=1000))
如评论中所述,lambdas
需要额外的函数调用,这很昂贵。可以使用列表理解重写此函数,以提供与其他函数非常接近(有时更小)的时间。
def qsort(ls):
if len(ls) > 1:
pivot = ls[0]
left = [e for e in ls if e < pivot]
equal = [e for e in ls if e == pivot]
right = [e for e in ls if e > pivot]
return qsort(left) + equal + qsort(right)
else:
return ls
此外,我将 list
更改为 ls
,这样内置的 list
就不会被隐藏。真正有趣的部分是,尽管对输入进行了重复迭代,并创建了新的中间数组,这在时间上仍然与就地排序功能相当。不幸的是,我所知道的不足以解释原因。对于较大的列表,似乎 qsort
表现最好,而就地方法开始显着减慢。
我在测试快速排序运行时,发现 lambda 版本的快速排序速度较慢。
为什么 lambda 版本明显变慢?我已经尝试交换我调用的每个订单,但它似乎一直在变慢。是不是因为我每次都重新声明左、等和右,因为必须分配过滤器(相对于 appending/in 位置)?
import timeit
def qsort(list):
if len(list) > 1:
pivot = list[0]
left = filter(lambda x: x < pivot, list)
equal = filter(lambda x: x == pivot, list)
right = filter(lambda x: x > pivot, list)
return qsort(left) + equal + qsort(right)
else:
return list
def sort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
if begin >= end:
return
pivot = partition(array, begin, end)
quicksort(array, begin, pivot-1)
quicksort(array, pivot+1, end)
return array
print qsort([5,3,1,5,2,6])
print sort([5,3,1,5,2,6])
print quicksort([5,3,1,5,2,6])
print (timeit.timeit(lambda: qsort([5,3,1,5,2,6]), number=1000))
print (timeit.timeit(lambda: sort([5,3,1,5,2,6]), number=1000))
print (timeit.timeit(lambda: quicksort([5,3,1,5,2,6]), number=1000))
如评论中所述,lambdas
需要额外的函数调用,这很昂贵。可以使用列表理解重写此函数,以提供与其他函数非常接近(有时更小)的时间。
def qsort(ls):
if len(ls) > 1:
pivot = ls[0]
left = [e for e in ls if e < pivot]
equal = [e for e in ls if e == pivot]
right = [e for e in ls if e > pivot]
return qsort(left) + equal + qsort(right)
else:
return ls
此外,我将 list
更改为 ls
,这样内置的 list
就不会被隐藏。真正有趣的部分是,尽管对输入进行了重复迭代,并创建了新的中间数组,这在时间上仍然与就地排序功能相当。不幸的是,我所知道的不足以解释原因。对于较大的列表,似乎 qsort
表现最好,而就地方法开始显着减慢。