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慢得多。实际上，对于递归方法，即使对于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

所有代码都在这里。

我有一些问题：

• 为什么列表理解如此之快？
• 对python递归限制的一些启示。在某些情况下，我首先将其设置为100000？
  • （“优化尾递归”到底是什么意思，如何完成？）
• 尝试对1000000个元素进行排序占用了我的笔记本电脑的内存（使用递归方法）。如果我想对这么多元素排序，该怎么办？什么样的优化是可能的？

Answer 1

1. 为什么列表理解如此之快？

因为列表理解意味着C循环，它比使用Pythonfor块的慢速通用方法要快得多。

1. 对python递归限制的一些启示。 在某些情况下，我首先将其设置为100000？

万一您的内存不足。

1. 尝试对1000000个元素进行排序占用了我的笔记本电脑的内存（使用递归方法）。 如果我想对这么多元素排序，该怎么办？什么样的优化是可能的？

Python的递归带来了这样的开销，因为每个函数调用都会在每个调用上分配大量的堆栈内存空间。

一般而言，迭代就是答案（在统计上99％的用例中，其性能都会更好）。

谈到内存结构，如果您有简单的数据结构，例如chars，integers，floats：请使用内置函数，array.array它比a的内存效率高得多list。