PythonでPythonインタープリタよりもコードが遅いのはなぜですか？

Question

nの数が与えられると、私はHを見つける必要があります。各タプルが連合の組み合わせであるすべてのタプルのリスト（例えば（1,2,3）は選手1,2、および3の連合です。この規則を尊重する（（1,2,3）、（4,5）、（6、））は、連合の組み合わせであり、これはタプルでもある）：各選手は、連合）。 P.P.連合の各組み合わせは、コード内のレイアウトと呼ばれます。

私はすべての連合のすべての組み合わせを計算したスニペットを書き、ルールをチェックした各組み合わせについてスニペットを書きました。問題は、5-6人のプレイヤーのために、連合の組み合わせの数がすでに大きかったために、私のコンピュータがプットしたことです。 は、計算（すべての可能な組み合わせ、ループおよびIFS）のAA大きな部分を避けるために、私は（私がテストし、それが前のスニペットと同等だもの）以下を書いた：

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

まず、私はすべての可能な連合を作成します。

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

その後、私は明白な組み合わせでHを初期化：自分の連立政権内の各選手との最大の連合内のすべてのプレーヤー。

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

そしてIは、レイアウトのすべての可能な形態を計算する：

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

Iの順列（パーマ）を計算します。 最後に、各パーマと各くしごとに、考えられるさまざまなレイアウトを計算します。

python script.py

• 4：0.000520944595337秒
• 5：0.18219秒私は重複を削除し、H.
  に

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

  を追加するために、ここでの比較だ（layouts）の結果をset

• 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 

私は実際の目的のためにここにいくつかのメモを入れました。私の数字は、そのいくつかの歳のThinkPadに基づいています

def bell(x): 
    if x == 0: 
     return() 
    if x == 1: 
     return ((set([1]),),) 
    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 

：しかし、いくつかのコードをコメントアウトし、他のいくつかのコードを書くことによって、あなたは私がベンチマークに使用し、以下の非メモ化バージョンを、入手することができます私は自分の仕事のほとんどをやります。小規模なケースの大半は信頼性の高い測定方法ではありません（最初の数回は1ミリ秒でさえありません）ので、私のベンチマークではbell(9)からbell(11)をテストしています。

標準timeitモジュール使用CPythonの2.7.11のためのベンチマーク、：、だから私はきた結論を

$ 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 

：またtimeitを使用して

$ python -mtimeit -s 'from derp import bell' 'bell(9)' 
10 loops, best of 3: 31.5 msec per loop 
$ python -mtimeit -s 'from derp import bell' 'bell(10)' 
10 loops, best of 3: 176 msec per loop 
$ python -mtimeit -s 'from derp import bell' 'bell(11)' 
10 loops, best of 3: 1.07 sec per loop 

そしてPyPy 4.0.1上を、あなたが意図したイディオムの外でそれを使用しようとすると、それほど高速ではないということが、itertoolsです。ベル番号は組み合わせて興味深いですが、私が見つけることができるitertoolsウィジェットの単純な構成から自然に発生するものではありません。

これを高速化するために何をすべきかというあなたの元々の質問に対して、それをオープンコード化するだけです。お役に立てれば！

〜C.

Answer 2

ここにはitertools.productのPypyの問題があります。

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

私たちの目標は、itertoolsが プレーンPythonのより大規模に遅くはありませんが、私たちは本当にそれが正確に早く（またはより高速 ）することを気にしないことを確実にするためであることに注意してください平野Pythonなど。大幅に遅くない限り、それは問題ありません。 （ 少なくとも、私があなたに同意していないかどうかa）またはb）は、それがitertools組み合わせを多用するように見える、詳細にあなたのコードを勉強しなければ:-)

を読みやすくなり、順列および製品機能。通常のCPythonでは、コンパイルされたCコードで書かれています。 PypyはCコードを実装していないので、これらの関数が遅いのは驚くべきことではありません。