Python快速排序 - 列表理解与递归(分区例程)

Question

我看了三个美丽的Quicksorts谈话,并且正在忙着赶快行动.我在python中的实现与c非常相似(选择pivot,围绕它进行分区并在越来越大的分区上递归).我认为这不是pythonic.

所以这是在python中使用list comprehension的实现.

def qsort(list):
    if list == []: 
        return []
    pivot = list[0]
    l = qsort([x for x in list[1:] if x < pivot])
    u = qsort([x for x in list[1:] if x >= pivot])
    return l + [pivot] + u

让我们调用递归方法qoortR.现在我注意到qsortR比大型(r)列表的qsort运行慢得多.实际上"cmp中超出了最大递归深度",即使对于递归方法也是1000个elems.我在sys.setrecursionlimit中重置.

一些数字:

list-compr 1000 elems 0.491770029068
recursion 1000 elems 2.24620914459
list-compr 2000 elems 0.992327928543
recursion 2000 elems 7.72630095482

所有代码都在这里.

我有一些问题:

• 为什么列表理解这么快？
• 对python中递归限制的一些启示.我首先将它设置为100000,在什么情况下我应该小心？
  • ('优化尾递归'究竟是什么意思,它是如何完成的？)
• 试图对我的笔记本电脑的1000000个元素进行排序(使用递归方法).如果我想要排序这么多元素,我该怎么办？什么样的优化是可能的？

Answer 1

1. 为什么列表理解这么快？

   因为列表理解意味着C循环比使用Python for块的慢速一般方法快得多.

2. 对python中递归限制的一些启示.我首先将它设置为100000,在什么情况下我应该小心？

   如果你的内存不足.

3. 试图对我的笔记本电脑的1000000个元素进行排序(使用递归方法).如果我想要排序这么多元素,我该怎么办？什么样的优化是可能的？

   Python的递归会产生这样的开销,因为每次调用都会在每次调用时分配大量的堆栈内存空间.

   通常,迭代是答案(在统计上99%的用例中将提供更好的性能).

   谈论内存结构,如果你有简单的数据结构,比如字符,整数,浮点数:使用内置的array.array内存效率比a更高list.