我看了演讲《三个美丽的快速排序》，并开始尝试快速排序。我在 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。现在我注意到对于大型（r）列表，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
所有的代码都是here.
我有一些问题：
- 为什么列表理解速度这么快？
- Some enlightenment on the limit on recursion in python. I first set it to 100000 in what cases should I be careful?
- （“优化尾递归”到底是什么意思，它是如何完成的？）
- 尝试对 1000000 个元素进行排序占用了我笔记本电脑的内存（使用递归方法）。如果我想对这么多元素进行排序该怎么办？可以进行哪些类型的优化？
-
为什么列表理解速度这么快？
因为列表理解意味着 C 循环比使用 Python 的慢速一般方式要快得多for block.
-
关于python中递归限制的一些启示。我首先将其设置为100000，在什么情况下我应该小心？
万一你内存不足。
-
尝试对 1000000 个元素进行排序占用了我笔记本电脑的内存（使用递归方法）。如果我想对这么多元素进行排序该怎么办？可以进行哪些类型的优化？
Python 的递归会产生这样的开销，因为每个函数调用都会在每次调用时分配大量的堆栈内存空间。
一般来说，迭代就是答案（在统计上 99% 的用例中将提供更好的性能）。
谈论内存结构，如果你有简单的数据结构，比如字符、整数、浮点数：使用内置的array.array这比一个内存效率高得多list.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
