使 pypy 运行更快的选项

Question

我写了一个测试代码看看pypy如何优化python代码并且运行更快。这是一种非就地快速排序，应该运行慢到足以产生差异。通过简单地将 python 替换为 pypy，结果实际上从 16 秒减慢到 25 秒。我搜索了一下，找到了 opt 选项，但我找不到将其应用于 pypy 的方法。我对 python 很陌生，所以请帮帮我。

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 的 "cons" 链表那样对待 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))

使 pypy 运行 更快的选项

Options to make pypy run faster

python

pypy

使 pypy 运行更快的选项