3 Quicksorts 函数 - 为什么 lambda 版本更慢？提供代码

Question

我在测试快速排序运行时，发现 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))

Answer 1

如评论中所述，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 表现最好，而就地方法开始显着减慢。

3 Quicksorts 函数 - 为什么 lambda 版本更慢？提供代码

3 Quicksorts Functions - Why is the lambda version slower? Code provided

python

algorithm

lambda

runtime

big-o