पापी का डेक इतना धीमा क्यों है?

Question

यहां Project Euler Problem 49 पर एक (थोड़ा गन्दा) प्रयास है।

मुझे यह कहना चाहिए कि deque एक अच्छा विकल्प नहीं था! मेरा विचार था कि सदस्यता के परीक्षण के लिए प्राइम के सेट को कम करने से लूप बढ़ने का कारण बन जाएगा। हालांकि, जब मुझे एहसास हुआ कि मुझे set (और तत्वों को हटाने के बारे में चिंता न करें) का उपयोग करना चाहिए था, तो मुझे 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 

वैसे भी, इससे पहले कि मैं एक set का उपयोग करने के बारे में सोचा, मैं इसे बाहर PyPy में की कोशिश की। मैंने परिणामों को अपेक्षाकृत आश्चर्यजनक पाया:

$ 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 

इस कोड पर पापी पांच गुना धीमी क्यों है? मुझे लगता है कि deque का पापी का संस्करण अपराधी है (क्योंकि यह set संस्करण पर तेज़ी से चलता है), लेकिन मुझे नहीं पता कि यह क्यों है।

Answer 1

धीमी हिस्सा inc1 in primes and inc2 in primes है। मैं देखूंगा कि क्यों पीपीपी इतनी धीमी है (प्रदर्शन बग रिपोर्ट के लिए धन्यवाद, मूल रूप से)। ध्यान दें कि जैसा कि आपने बताया है कि कोड को अविश्वसनीय रूप से तेज़ बनाया जा सकता है (पीपीपी और सीपीथॉन दोनों पर) --- इस मामले में, डेक को for लूप से पहले सेट में कॉपी करके।

Answer 2

आपको धीमे होने के लिए एक डेक (पायथन प्रदर्शन चरित्रिकी के साथ) में सदस्यता परीक्षण की अपेक्षा करनी चाहिए, क्योंकि किसी सूची में किसी सदस्यता परीक्षा में रैखिक स्कैन शामिल है। इसके विपरीत, सेट सदस्यता परीक्षणों के लिए अनुकूलित एक डेटास्ट्रक्चर है। उस अर्थ में, यहां कोई बग नहीं है।