इरेटोस्टेनेस की मेरी चलनी इतनी धीमी क्यों है?

Question

मैं प्रोजेक्ट यूलर पर कुछ समस्याओं को हल करता हूं और किसी समस्या को हल करने के लिए 2 मिलियन प्राइम उत्पन्न करना पड़ता था। इरेटोस्टेनेस की चलनी का मेरा कार्यान्वयन बेहद धीमा हो गया लेकिन मुझे नहीं पता कि क्यों। क्या कोई इस कार्यान्वयन के साथ प्रमुख समस्याओं की व्याख्या कर सकता है। मैंने सोचा कि यह तो बहुत था, और फिर मैं पता लगा यह पूरी तरह से भयानक है :(मैं ऑनलाइन यह का एक और कार्यान्वयन पाया जाता है और यह इतना मेरा तुलना में बहुत तेज था

def generatePrimes(upperBound): 
    numbers = range(2,upperBound+1) 
    primes = [] 

    while numbers: 
     prime = numbers[0] 
     primes.append(prime) 
     numbers = filter((lambda x: x%prime),numbers) 
    return primes 

संपादित करें:।। सभी प्रश्नों के उत्तर के लिए धन्यवाद! इसका निष्कर्ष यह है कि यह फ़िल्टर है जो समस्या है क्योंकि यह प्रत्येक तत्व के माध्यम से जाता है (केवल उन लोगों के बजाय जिन्हें प्राइम के रूप में चिह्नित नहीं किया जाता है) और क्योंकि यह हर बार एक नई सूची बनाता है। इसे लूप के लिए पुराने पुराने के साथ दोबारा दोहराएं । और छानने के एक दौर है और यह बहुत तेजी से काम करता है नए कोड:

def generatePrimes(upperBound): 
numbers = range(2,upperBound+1) 

for i in xrange(len(numbers)): 
    if(numbers[i] != 0): 
     for j in xrange(i+numbers[i],len(numbers),numbers[i]): 
      numbers[j] = 0 

primes = filter(lambda x: x,numbers) 
return primes 

Answer 1

एरेटोस्थेनेज की चलनी इस तरह दिखता है:

def sieve(n): 
    primality_flags = [True]*(n+1) 
    flags[0] = flags[1] = False 
    primes = [] 
    for i, flag in enumerate(primality_flags): 
     if flag: 
      primes.append(i) 
      for j in xrange(2*i, n+1, i): 
       flags[i] = False 

यह एक बार प्रत्येक संख्या को संसाधित करता है जब बाहरी पाश यह हर प्रधानमंत्री है कि यह बांटता के लिए पहुंचता है, और एक बार। लगभग 1/2 संख्याएं 2 से विभाजित होती हैं, लगभग 1/3 3 से विभाजित होती हैं, और इसी तरह; असम्बद्ध रूप से बोलते हुए, प्रत्येक संख्या को संसाधित करने की औसत संख्या 1 + है, जो प्राइम के पारस्परिक प्रावधानों की राशि है। This sum is about log(log(n)), इसलिए चलनी में एसिम्प्टोटिक समय जटिलता O(n*log(log(n))) है, मान लीजिए अंकगणित स्थिर समय है। यह सचमुच अच्छा है।

---

आपका कार्य ऐसा नहीं करता है। आपके filternumbers में प्रत्येक तत्व पर चला जाता है, भले ही यह prime द्वारा विभाजित हो। प्रत्येक तत्व को प्रत्येक प्राइम तक संसाधित किया जाता है जब तक कि इसे विभाजित करने वाले पहले प्राइम तक, और प्राइम पी को प्रोसेस करना numbers के तत्वों के लगभग 1/पी को हटा देता है। प्राइम्स के अनुक्रम को पी [0], पी [1], पी [2], आदि होना चाहिए, और numbers के आकार के क्रम को एन [0], एन [1], एन [2] इत्यादि होना चाहिए। , हम निम्नलिखित अनुमानित पुनरावृत्ति है:

n[0] = upperBound - 1 
n[1] = n[0] * (p[0]-1)/p[0] 
n[2] = n[1] * (p[1]-1)/p[1] 
... 
n[k+1] = n[k] * (p[k]-1)/p[k] 

और अपने एल्गोरिथ्म समय मोटे तौर पर जब तक numbers खाली है n मान का योग के लिए आनुपातिक लेता है। मैंने उस श्रृंखला के व्यवहार का विश्लेषण नहीं किया है, लेकिन गणना दर्शाती है कि वृद्धि O(n*log(log(n))) से भी बदतर है।

Answer 2

cProfile चल रहा है पता चलता है कि समय के सबसे अधिक फिल्टर में खर्च किया जाता है replac। एक सूची समझ के साथ फिल्टर ing चीजों को एक गति से 2.

numbers = [n for n in numbers if n%prime != 0] 

एक पहलू के बारे में द्वारा लेकिन यह वास्तव में मुख्य समस्या है, जो है कि आप प्रत्येक यात्रा के साथ नंबर की सूची पुनः कर रहे हैं कर रहे हैं ठीक नहीं होती, , और वह धीमा है। तेजी से कार्यान्वयन http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d बस गैर प्राइम को 0 या इसी तरह से बदलकर चिह्नित करें।