एक लाइन

Question

में पायथन प्राइम जनरेटर मैं एक मजेदार अभ्यास के रूप में पाइथन की एक पंक्ति में प्राइम नंबर जेनरेटर बनाने की कोशिश कर रहा हूं।

निम्नलिखित कोड अपेक्षित ढंग से काम करता है, लेकिन यह बहुत धीमी है:

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))]) 
for i in primes(10): 
    print i, 

:

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)]) 
for i in primes(10): 
    print i, 

तो द्वितीय केवल j और कश्मीर के वर्ग जड़ से ऊपर की जाँच करके यह करने की कोशिश की

लेकिन यह आउटपुट करता है: 2 3 5 6 7 8

तो मेरे सूचकांक जे और के साथ कुछ गड़बड़ होनी चाहिए, लेकिन मुझे कोई सुराग नहीं मिला है।

Answer 1

यह एराटोस्टेनेस की चाकू नहीं है, भले ही ऐसा लगता है। यह वास्तव में बहुत खराब है। छल खोजने के लिए चलनी सबसे अच्छा एल्गोरिदम है।

देखें http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

संपादित: मैं https://stackoverflow.com/a/9302299/711085 संशोधित कर लिया है एक एक लाइनर होने के लिए (मूल रूप से यह असली चलनी नहीं था, लेकिन अब यह है ... शायद ...):

reduce((lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
     range(2,N), set(range(2,N))) 

डेमो:

>>> primesUpTo(N): lambda N: reduce(...) 
>>> primesUpTo(30) 
{2, 3, 5, 7, 11, 13, 17, 19} 

---

अफसोस की बात है कि मुझे लगता है कि यह एक कार्यात्मक प्रोग्रामिंग भाषा में कुशल होगा, यह गैर-निरंतर (साझा राज्य और अपरिवर्तनीय) डेटा संरचनाओं के कारण अजगर में उतना ही कुशल नहीं हो सकता है, और अजगर में किसी भी चलनी को उत्परिवर्तन का उपयोग करने की आवश्यकता होगी तुलनीय प्रदर्शन प्राप्त करें। अगर हम बेहद ज़रूरी चाहते हैं तो हम इसे एक लाइनर में भी क्रैम कर सकते हैं। लेकिन पहले...

सामान्य चलनी:

>>> N = 100 
>>> table = list(range(N)) 
>>> for i in range(2,int(N**0.5)+1): 
...  if table[i]: 
...   for mult in range(i**2,N,i): 
...    table[mult] = False 
... 
>>> primes = [p for p in table if p][1:] 
>>> primes 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

अब हम को परिभाषित करने और एक ही लाइन पर गुमनाम काम करता है, और साथ ही [...].__setitem__ के हैक फोन इनलाइन उत्परिवर्तन करने के लिए कर सकते हैं और ... मूल्यांकन करने के लिए ... and foo के हैक जबकि foo लौटने :

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N))) 
>>> primesUpTo(30) 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

हॉरर में चापलूसी के लिए आगे बढ़ें, एक लाइनर का विस्तार (विचित्र रूप से सुंदर है क्योंकि आप लगभग सीधे नियंत्रण प्रवाह उसका अनुवाद कर सकें, फिर भी की एक भयानक दुरुपयोग सब कुछ):

lambda N: 
    (lambda table: 
     [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
      for i in range(2,int(N**0.5)+1) if table[i]] 
     and [p for p in table if p][1:] 
    )(list(range(N))) 

यह एक लाइनर परिवर्तनशील संस्करण मेरी मशीन पर लगभग 10 पर छोड़ दिया, जबकि मूल परिवर्तनशील संस्करण लगभग 10 पर छोड़ दिया, स्मृति (विचित्र रूप से) से बाहर चल रहा है।

मूल reduce संस्करण 10 पर छोड़ दिया गया। तो शायद यह नहीं है कि सभी के बाद अक्षम (कम से कम उन संख्याओं के लिए जिन्हें आप अपने कंप्यूटर पर सौदा कर सकते हैं)।

EDIT2 ऐसा लगता है आप दुष्प्रभाव का दुरुपयोग कर सकते हैं के रूप में अधिक संक्षेप में:

reduce((lambda r,x: (r.difference_update(range(x**2,N,x)) or r) 
        if (x in r) else r), 
     range(2,N), set(range(2,N))) 

यह लगभग 10 पर देता है, एक लाइनर परिवर्तनशील संस्करण के समान।

edit3: यह runs at हे (एन) empirical complexity, जबकि difference_update बिना यह O(n^2.2) complexity पर भाग गया।

रेंज उस पर कम हो जाता है ऊपरी सीमा के sqrt के लिए, सीमित है, और काम कर with odds only, अतिरिक्त गति-अप (2x और 1.6x तदनुसार) में दोनों परिणाम:

reduce((lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r) 
        if (x in r) else r), 
     range(3, int((N+1)**0.5+1), 2), 
     set([2] + range(3,N,2))) 

Answer 2

आप प्राइम के लिए परीक्षण करने के लिए केवल वर्ग रूट तक संख्याओं के उत्पादों की जांच नहीं कर सकते हैं। 8 देखें- 8 की वर्ग रूट 2.8 है, इसलिए यह कभी भी 4 * 2 की कोशिश नहीं करेगा। (दरअसल, केवल को प्राइम संख्या के रूप में नहीं देखा जाएगा)।

ईटीए: जे और के सभी संभावित संयोजनों को आजमाने की बजाय, क्यों जांचें कि क्या मैं प्रत्येक जे द्वारा विभाजित है (i % j == 0 का उपयोग करके) जे के वर्ग रूट तक? यह दोनों कम कोड लेता है और यह अधिक कुशल है (हालांकि यह अभी भी लगभग नहीं है जैसा कि इरेटोस्टेनेस की चलनी के रूप में कुशल है)।

Answer 3

यहाँ आप क्या चाहता है:

def primes (q) : 
# return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)]) 
# return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)]) 
# return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)]) 

return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))]) 

हास्केल में, पर्वतमाला शामिल होते हैं, तो primes(542)

है

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],  k<-[1..n-1]]] -- 25.66s 
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],  k<-[1..j]]] -- 15.30s 
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]] -- 6.00s 
                     -- 0.79s 
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]] 

और वास्तव में, 1*x == x तो एक गुणक के रूप में की जरूरत नहीं है, इस प्रकार यह

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]] 

जो केवल 0.59 सेकंड लेता है होना चाहिए।या, पायथन में

def primes (q) : 
return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))]) 

---

अद्यतन: किसी कारण से, min j ... कम से कम हास्केल में बहुत अधिक अंतर नहीं है,। तो अभिव्यक्ति बस

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]] 

Answer 4

हो जाता है के बारे में कैसे:

def primes(x): 
    return [i for i in range(2,x) if 0 not in [i%j for j in range(2,i)]]