7

我看了三个美丽的快速排序的谈话，并在玩快速排序。我在 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。现在我注意到对于 large(r) 列表，qsortR 的运行速度比 qsort 慢得多。实际上“最大递归深度超过 cmp”即使对于递归方法的 1000 个元素也是如此。我在 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 个元素进行排序（使用递归方法）。如果要对这么多元素进行排序，该怎么办？可以进行哪些优化？
4

3 回答 3

9

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

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

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

    以防内存不足。

  3. 尝试对占用笔记本电脑内存的 1000000 个元素进行排序（使用递归方法）。如果要对这么多元素进行排序，该怎么办？可以进行哪些优化？

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

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

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

于 2012-08-24T10:58:59.023 回答
1

您是否尝试过编写 的非递归实现partition？我怀疑性能差异纯粹是partition实现。您正在为实现中的每个元素进行递归。

更新

这是一个快速实现。它仍然不是超级快甚至效率不高，但它比你原来的递归要好得多。

>>> def partition(data):
...  pivot = data[0]
...  less, equal, greater = [], [], []
...  for elm in data:
...   if elm < pivot:
...    less.append(elm)
...   elif elm > pivot:
...    greater.append(elm)
...   else:
...    equal.append(elm)
...  return less, equal, greater
...
>>> def qsort2(data):
...  if data:
...   less, equal, greater = partition(data)
...   return qsort2(less) + equal + qsort2(greater)
...  return data
...

我也认为“传统”版本中生成的临时列表数量较多。

于 2012-08-24T11:10:24.560 回答
1

当内存变得非常大时，尝试将列表理解与就地算法进行比较。下面的代码在对 100K 整数进行排序时获得了接近执行时间，但在对 1M 整数进行排序时，您可能会陷入列表理解解决方案中。我使用 4Gb 机器进行了测试。完整代码：http ://snipt.org/Aaaje2

class QSort:
def __init__(self, lst):
    self.lst = lst

def sorted(self):
    self.qsort_swap(0, len(self.lst))
    return self.lst

def qsort_swap(self, begin, end):
    if (end - begin) > 1:
       pivot = self.lst[begin]
       l = begin + 1
       r = end
       while l < r:
           if self.lst[l] <= pivot:
               l += 1
           else:
               r -= 1
               self.lst[l], self.lst[r] = self.lst[r], self.lst[l]

       l -= 1
       self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]    
       # print begin, end, self.lst
       self.qsort_swap(begin, l)
       self.qsort_swap(r, end)
于 2013-05-13T13:40:33.903 回答