使pypy运行得更快的选项

Question

我编写了一个测试代码，以了解pypy如何更好地优化python代码并运行得更快。这是一种非就地快速排序，应该运行的速度足够慢，以发挥作用。简单地将python替换为pypy，结果实际上要慢一些，从16秒到25秒。我搜索了一下，找到了opt选项，但是我找不到将它应用于pypy的方法。我对蟒蛇很陌生，所以请帮帮我。

import sys

def sqsort(xxs):
    if len(xxs) == 1 or len(xxs) == 0:
        return xxs
    x = xxs[0]
    xs = xxs[1 :]
    l = []
    g = []
    for x2 in xs:
        if x2 < x:
            l.append(x2)
        if x2 >= x:
            g.append(x2)
    return sqsort(l) + [x] + sqsort(g)

sys.setrecursionlimit(30000)
l = list(reversed(range(15000)))
print(l)
print(sqsort(l))

Answer 1

不是一个完整的答案，但实际上问题是递归，PyPy并不擅长这个问题。下面是相同的算法，只对较短的子列表( l或g)使用递归，对于较长的列表使用迭代。这个版本仍然是递归的，但递归保证仅限于O(log(n))时间，而不是O(n)。现在PyPy的速度快了4-5倍。

请注意，我们不能说这个算法的总时间(在这两个版本中)实际上是O(n log(n))，因为它充满了列表连接，这也需要时间。不能像对待Haskell或Lisp的“con”链表那样对待Python的列表；在Python中，列表是可变大小的数组。

def sqsort(xxs):
    left, right = [], []
    while True:
        if len(xxs) == 1 or len(xxs) == 0:
            return left + xxs + right
        x = xxs[0]
        xs = xxs[1 :]
        l = []
        g = []
        for x2 in xs:
            if x2 < x:
                l.append(x2)
            if x2 >= x:
                g.append(x2)
        if len(l) <= len(g):
            left += sqsort(l) + [x]
            xxs = g
        else:
            right = [x] + sqsort(g) + right
            xxs = l

l = list(reversed(range(15000)))
print(l)
print(sqsort(l))