Python quicksort-列表理解与递归(分区例程) [英] Python quicksort - List comprehension vs Recursion (partition routine)

问题描述

我看了谈话三个美丽的快速排序"，并开始忙于快速排序.我在python中的实现与c非常相似(选择数据透视图，围绕它的分区并在越来越大的分区上递归).我以为不是 pythonic .

I watched the talk Three Beautiful Quicksorts and was messing around with quicksort. My implementation in python was very similar to c (select pivot, partition around it and recursing over smaller and larger partitions). Which I thought wasn't pythonic.

所以这是在python中使用列表推导的实现.

So this is the implementation using list comprehension in 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中重设了.

Lets call the recursion metho qsortR. now I noticed that qsortR runs much slower than qsort for large(r) lists. Actually "maximum recursion depth exceeded in cmp" even for 1000 elems for recursion method. Which I reset in 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?
  • (优化尾递归"到底是什么意思，如何完成?)
  • Why is list comprehension so much faster?
  • Some enlightenment on the limit on recursion in python. I first set it to 100000 in what cases should I be careful?
    • (What exactly is meant by 'optimizing tail recursion', how is it done?)

    推荐答案

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

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

    Because list comprehension implies C loop which is much faster than slow general way of using Python's for block.

    一些关于python递归限制的启示.我首先将其设置为100000，在什么情况下应该小心?

    以防内存不足.

    试图对1000000个元素进行排序，这消耗了我的笔记本电脑的内存(使用递归方法).如果我想对这么多元素排序，该怎么办?什么样的优化是可能的?

    Python的递归带来了这样的开销，因为每个函数调用在每个调用上分配了很多堆栈内存空间.

    Python's recursion gives such an overhead because every function call allocates a lot of stack memory space on each call.

    一般来说，迭代就是答案(在统计上占用例99％的情况下，将提供更好的性能).

    In general, iteration is the answer (will give better performance in statistically 99% of use cases).

    如果您有简单的数据结构(例如chars，integers，floats)，请讨论内存结构:使用内置的array.array，它比list的内存效率要高得多.

    Talking about memory structures, if you have simple data structures, like chars, integers, floats: use built-in array.array which is much more memory efficient than a list.

    这篇关于Python quicksort-列表理解与递归(分区例程)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！