Python quicksort - 列表理解与递归(分区例程)

Question

我看了三个美丽的快速排序的演讲，并且正在研究快速排序。我在 python 中的实现与 c 非常相似(选择枢轴，围绕它进行分区并在越来越小的分区上递归)。我认为这不是 pythonic。

所以这是在python中使用列表理解的实现。

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

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

一些数字:

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

所有代码都是here .

我有几个问题:

• 为什么列表理解要快得多？
• 对python递归限制的一些启示。我先设置成100000在什么情况下需要注意？
  • (“优化尾递归”到底是什么意思，它是如何完成的？)
• 尝试对占用笔记本电脑内存的 1000000 个元素进行排序(使用递归方法)。这么多元素要排序怎么办？可以进行哪些优化？

Answer 1

1. 为什么列表理解要快得多？

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

2. 对python递归限制的一些启示。我先设置成100000在什么情况下需要注意？

   以防内存不足。

3. 尝试对占用笔记本电脑内存的 1000000 个元素进行排序(使用递归方法)。这么多元素要排序怎么办？什么样的优化是可能的？

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

   一般来说，迭代就是答案(在统计上 99% 的用例中会提供更好的性能)。

   谈到内存结构，如果你有简单的数据结构，比如字符、整数、 float :使用内置的 array.array，它比 list.