Perché la deque di Pypy è così lenta?

Ecco un tentativo (leggermente disordinato) allo Project Euler Problem 49.Perché la deque di Pypy è così lenta?

Devo dire a priori che lo deque non è stata una buona scelta! La mia idea era che ridurre il set di numeri primi per testare l'appartenenza avrebbe fatto accelerare il ciclo. Tuttavia, quando ho capito che avrei dovuto usare uno set (e non mi preoccupo di rimuovere elementi), ho ottenuto un aumento di velocità 60x.

from collections import deque 
from itertools import permutations 
from .sieve import sieve_of_erastothenes # my own implementation of the Sieve of Erastothenes 

primes = deque(prime for prime in sieve_of_erastothenes(10000) if prime > 1000 and prime != 1487) # all four-digit primes except 1487 
try: 
    while True: 
     prime = primes.popleft() # decrease the length of primes each time to speed up membership test 
     for inc in xrange(1,10000 + 1 - (2 * prime)): # this limit ensures we don't end up with results > 10000 
      inc1 = prime + inc 
      inc2 = prime + 2*inc 

      if inc1 in primes and inc2 in primes: 
       primestr = str(prime) 
       perms = set(''.join(tup) for tup in permutations(primestr)) # because permutations() returns tuples 
       inc1str = str(inc1) 
       inc2str = str(inc2) 
       if inc1str in perms and inc2str in perms: 
        print primestr + inc1str + inc2str 
        raise IOError # I chose IOError because it's unlikely to be raised 
            # by anything else in the block. Exceptions are an easy 
            # way to break out of nested loops. 
except IOError: 
    pass

In ogni caso, prima di pensare di usare un set, ho provato in PyPy. Ho trovato i risultati siano piuttosto sorprendente:

$ time python "problem49-deque.py" 
296962999629 

real 1m3.429s 
user 0m49.779s 
sys 0m0.335s 

$ time pypy-c "problem49-deque.py" 
296962999629 

real 5m52.736s 
user 5m15.608s 
sys 0m1.509s

Perché PyPy oltre cinque volte più lento su questo codice? Direi che la versione di Pypy dello deque è il colpevole (perché corre più veloce nella versione set), ma non ho idea del perché sia così.

fonte

2012-11-16 Benjamin Hodgson

Grazie per aver chiesto questo! Stavo per pubblicare una domanda che mi chiedeva perché la versione deque del mio codice fosse del 28% più lenta della versione list. –

La parte lenta è inc1 in primes and inc2 in primes. Vedrò perché PyPy è così lento (grazie per il bug report delle prestazioni, in pratica). Nota che come hai detto il codice può essere reso incredibilmente più veloce (sia su PyPy che su CPython) --- in questo caso, semplicemente copiando il demaggio primes in un set subito prima del ciclo for.

fonte

2012-11-16 17:48:37

+1, ma non ho accettato la risposta perché non risponde ancora alla domanda. Se scopri qual è il problema, per favore potresti segnalarmi? Mi piacerebbe sapere cosa lo sta causando. –

Follow-up sul funzionario [bug tracker.] (Https://bugs.pypy.org/issue1327) –

Il bug tracker ufficiale spostato: https://bitbucket.org/pypy/pypy/issues/1327 (ovviamente è stato risolto da sempre.) –

È necessario prevedere che i test di appartenenza in un deque (con le caratteristiche di prestazioni python) siano lenti, poiché qualsiasi test di appartenenza in un elenco implica una scansione lineare. Al contrario, set è una infrastruttura ottimizzata per i test di appartenenza. In questo senso, non vi è alcun bug qui.

fonte

2012-11-16 18:21:41 Marcin

La mia domanda riguardava la differenza di velocità tra 'deque 'di CPython e' deque' di Pypy. Sono d'accordo (vedi la domanda) che un 'set' era la scelta giusta per la struttura dei dati in questo caso particolare e un' deque' no. –

@poorsod Giusto, ma la tua domanda è "perché un datastructure inappropriato funziona male". La risposta è che è inappropriato e che ciò era conoscibile in anticipo. È positivo che il codice del test di appartenenza CPython sia altamente ottimizzato, ma non è male che il codice CPython non lo sia, perché non si tratta di una infrastruttura adatta a molti test di questo tipo. – Marcin

Ero curioso di sapere esattamente perché il test di appartenenza di Pypy è molto più lento di quello di CPython. Se senti che la domanda non è chiara su questo punto, la modificherò. –

Perché la deque di Pypy è così lenta?

risposta

Problemi correlati