Warum ist mein Code in pypy langsamer als der Standard-Python-Interpreter?

Question

Angesichts einer Anzahl von Spielern n, muss ich H finden, die Liste aller Tupel, wo jedes Tupel eine Kombination von Koalitionen ist (der Spieler, zB (1,2,3) ist die Koalition der Spieler 1, 2 und 3. ((1,2,3), (4,5), (6,)) ist eine Kombination von Koalitionen - die auch Tupel sind), die diese Regel respektieren: Jeder Spieler erscheint nur und genau einmal (dh in nur einem Koalition). P.S. Jede Kombination von Koalitionen wird Layout im Code genannt.

Am Anfang habe ich einen Ausschnitt geschrieben, in dem ich alle Kombinationen aller Koalitionen berechnet habe und für jede Kombination die Regel überprüft habe. Problem ist, dass für 5-6 Spieler die Anzahl der Kombinationen von Koalitionen bereits so groß war, dass mein Computer pleite ging. Um ein einen großen Teil der Berechnung (alle möglichen Kombinationen, die Schleife und die ifs) zu vermeiden, schrieb ich folgendes (die ich getestet und es ist äquivalent zu dem vorherigen Snippet):

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 

ERKLÄRUNG: sagen n = 3

Zunächst erstelle ich alle möglichen Koalitionen:

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

Dann initialisieren I H mit den offensichtlichen Kombinationen: jeden Spieler in seiner eigenen Koalition und jeden Spieler in der größten Koalition.

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

Dann berechnen ich alle möglichen Formen der Layouts:

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

ich berechnen die Permutationen (perms). Schließlich berechne ich für jede Dauerwelle und für jeden Kamm die verschiedenen möglichen Layouts. Ich set das Ergebnis (layouts), um Duplikate zu löschen und

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

Hier ist der Vergleich zu H. hinzufügen:

python script.py

• 4: 0,000520944595337 Sekunden
• 5: 0,18219 Sekunden
• 6: 0.0408189296722 Sekunden
• 7: 0,431486845016 Sekunden lang
• 8: 6,05224680901 Sekunden lang
• 9: 76,4520540237 Sekunden lang

pypy script.py

• 4: 0,00342392921448 Sekunden lang
• 5: 0,0668039321899 Sekunden lang
• 6: 0,311077833176 Sekunden
• 7 : 1.13124799728 Sekunden
• 8: 11.5973010063 Sekunden
• 9: ging phut

Warum ist PyPy dass langsamer? Was soll ich ändern?

Answer 1

Zunächst möchte ich darauf hinweisen, dass Sie die Bell numbers studieren, die den nächsten Teil Ihrer Arbeit erleichtern könnte, nachdem Sie alle Teilmengen generiert haben. Zum Beispiel ist es einfach zu wissen, wie groß jedes Bell-Set sein wird; OEIS hat the sequence of Bell numbers bereits.

Ich schrieb die Schleifen manuell, um die Glockensätze zu erzeugen; Hier ist mein Code:

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 

Ich habe hier einige Memoization für praktische Zwecke enthalten. Doch durch einen Code zu kommentieren aus, und einige andere Code zu schreiben, können Sie die folgende un-memoized Version erhalten, die ich für Benchmarks verwendet:

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 

Meine Zahlen sind auf einem mehrere Jahre alten Thinkpad zugrunde, dass Ich mache die meiste Arbeit an mir. Die meisten kleineren Fälle sind viel zu schnell, um zuverlässig zu messen (nicht einmal eine Millisekunde pro Test für die ersten), daher testen meine Benchmarks bell(9) bis bell(11).

Benchmarks für CPython 2.7.11, den Standard timeit Modul:

$ 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 

Und auf PyPy 4.0.1, auch timeit mit:

$ 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 

die Schlussfolgerung, dass ich so, Kommen Sie dazu, dass itertools nicht sehr schnell ist, wenn Sie versuchen, es außerhalb seiner beabsichtigten Idiome zu verwenden. Bell-Zahlen sind kombinatorisch interessant, aber sie entstehen nicht auf natürliche Weise aus einer einfachen Zusammensetzung von itertools Widgets, die ich finden kann.

Als Reaktion auf Ihre ursprüngliche Abfrage, was zu tun ist, um es schneller zu machen: Einfach Code-öffnen. Hoffe das hilft!

~ C.

Answer 2

Hier ist ein Pypy-Problem auf itertools.product.

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

Beachten Sie, dass unser Ziel, sicherzustellen, dass itertools nicht massiv langsamer als Ebene Python ist, aber wir haben nicht wirklich kümmern uns um was es genau so schnell (oder schneller) als einfacher Python . Solange es nicht massiv langsamer ist, ist es in Ordnung. (Bei dest ich nicht mit Ihnen darüber einigen, ob a) oder b) ist einfacher :-) zu lesen

Ohne Code im Detail zu studieren, es sieht aus wie es die starke Nutzung der Kombinationen itertools macht, Permutationen und Produktfunktionen. In regulären CPython werden diese in kompiliertem C-Code geschrieben, um sie schnell zu machen. Pypy implementiert den C-Code nicht, daher sollte es nicht überraschen, dass diese Funktionen langsamer sind.