为什么pypy中的代码比默认的python解释器慢？

Question

给定若干玩家n，我需要找到H，其中每个元组都是联盟的组合（例如（1,2,3）是玩家1、2和3的联盟。（（1，2，3），（4，5），（6，））是一个联盟的组合-也是元组），它尊重这个规则：每个玩家只出现一次，而且只出现一次（即只在一个联盟中出现）。 P、 每一个联盟的组合在代码中称为布局。在

在开始的时候，我写了一段代码，我计算了所有联盟的所有组合，并检查了每个组合的规则。问题是，对于5-6个玩家来说，联盟组合的数量已经太多了，以至于我的电脑出了故障。 为了避免很大一部分的计算（所有可能的组合，循环和ifs），我写了以下内容（我测试了它，它相当于前面的代码片段）：

from itertools  import combinations, combinations_with_replacement, product, permutations

players = range(1,n+1)
coalitions = [[coal for coal in list(combinations(players,length))] for length in players]

H = [tuple(coalitions[0]),(coalitions[-1][0],)]
combs = [comb for length in xrange(2,n) for comb in combinations_with_replacement(players,length) if sum(comb) == n]
perms = list(permutations(players))
layouts = set(frozenset(frozenset(perm[i:i+x]) for (i,x) in zip([0]+[sum(comb[:y]) for y in xrange(1,len(comb))],comb)) for comb in combs for perm in perms)
H.extend(tuple(tuple(tuple(coal) for coal in layout) for layout in layouts))
print H

说明：假设n=3

首先，我创建所有可能的联盟：

^{pr2}$

然后我用明显的组合初始化H：每个成员在他自己的联盟中，每个成员在最大联盟中。在

H = [((1,),(2,),(3,)),((1,2,3),)]

然后计算所有可能的布局形式：

combs = [(1,2)]   #(1,2) represents a layout in which there is 
                  #one 1-player coalition and one 2-player coalition.

我计算排列。 最后，对于每个烫发和每个梳子，我计算出不同的可能布局。Iset结果（layouts）以便删除重复项并添加到H

H = [((1,),(2,),(3,)),((1,2,3),),((1,2),(3,)),((1,3),(2,)),((2,3),(1,))]

比较如下：

python script.py

• 4： 0.000520944595337秒
• 5： 0.0038321018219秒
• 6： 0.0408189296722秒
• 7： 0.431486845016秒
• 8： 6.05224680901秒
• 9： 76.4520540237秒

pypy script.py

• 4： 0.00342392921448秒
• 5： 0.0668039321899秒
• 6： 0.311077833176秒
• 7： 1.13124799728秒
• 8： 11.5973010063秒
• 9： 发脾气了

为什么pypy那么慢？我该换什么？在

Answer 1

首先，我想指出，您正在研究Bell numbers，这可能会在您完成所有子集的生成之后，简化下一部分的工作。例如，很容易知道每个铃声集的大小；OEIS已经有了the sequence of Bell numbers。在

我手工编写循环以生成铃声集；以下是我的代码：

cache = {0: (), 1: ((set([1]),),)}

def bell(x):
    # Change these lines to alter memoization.
    if x in cache:
        return cache[x]
    previous = bell(x - 1)
    new = []
    for sets in previous:
        r = []
        for mark in range(len(sets)):
            l = [s | set([x]) if i == mark else s for i, s in enumerate(sets)]
            r.append(tuple(l))
        new.extend(r)
        new.append(sets + (set([x]),))
    cache[x] = tuple(new)
    return new

为了实用起见，我在这里写了一些回忆录。但是，通过注释掉一些代码，并编写一些其他代码，您可以获得以下未记下来的版本，我将其用于基准测试：

^{pr2}$

我的数字是基于一个有几年历史的Thinkpad，我大部分的工作都是在这个平台上完成的。大多数较小的案例速度太快，无法可靠地测量（前几次试验甚至没有一毫秒），所以我的基准测试是bell(9)到{}。在

使用标准timeit模块的cpython2.7.11基准测试：

^{3}$

在Pypy4.0.1上，也使用timeit：

$ pypy -mtimeit -s 'from derp import bell' 'bell(9)'
100 loops, best of 3: 14.3 msec per loop
$ pypy -mtimeit -s 'from derp import bell' 'bell(10)'
10 loops, best of 3: 90.8 msec per loop
$ pypy -mtimeit -s 'from derp import bell' 'bell(11)'
10 loops, best of 3: 675 msec per loop

所以，我得出的结论是，当你试图在它的习惯用法之外使用{}时，它的速度不是很快。Bell数是有趣的组合，但它们并不是由我能找到的任何简单的itertools小部件组成的。在

为了回应你最初的问题：打开代码就可以了。希望这有帮助！在

~C

Answer 2

这是一个关于itertools.product的Pypy问题。在

https://bitbucket.org/pypy/pypy/issues/1677/itertoolsproduct-slower-than-nested-fors

Note that our goal is to ensure that itertools is not massively slower than plain Python, but we don't really care about making it exactly as fast (or faster) as plain Python. As long as it's not massively slower, it's fine. (At least I don't agree with you about whether a) or b) is easier to read :-)

如果不详细研究代码，它似乎大量使用了itertools组合、排列和乘积函数。在常规的CPython中，这些代码是用编译的C代码编写的，目的是使它们更快。Pypy并没有实现C代码，因此这些函数的速度慢一点也不奇怪。在