मेरे पास पाइथन में प्राइम्स खोजने के दो एल्गोरिदम हैं। प्रत्येक के आंतरिक लूप को समान संख्या में निष्पादित किया जाता है, और यह उतना ही सरल है। हालांकि, उनमें से एक दूसरे के रूप में 10 गुना अधिक लेता है। मेरा सवाल है:प्राइम ढूंढने के लिए दो एल्गोरिदम इतने तेज क्यों होते हैं भले ही वे समान संख्या में पुनरावृत्ति करते हैं?
क्यों? क्या यह पाइथन का कुछ कर्कश है जिसे अनुकूलित किया जा सकता है (कैसे?), या क्या मुझे कुछ और याद आ रहा है?
समस्या जो मैं हल कर रहा हूं वह अनिवार्य रूप से http://www.spoj.pl/problems/PRIME1/ से है। मेरे मामले में, मेरे पास एन = 10 ** 9, डेल्टा = 10 ** 5 है, और मैं एन-डेल्टा और डेल्टा के बीच सभी प्राइम ढूंढना चाहता हूं। मैं भी smallprimes है, सभी का एक पूर्व निर्मित सूची से कम या एन के वर्गमूल के बराबर primes पहले एल्गोरिथ्म बहुत सरल है:
def range_f1(lo, hi, smallprimes):
"""Finds all primes p with lo <= p <= hi.
smallprimes is the sorted list of all primes up to (at least) square root of hi.
hi & lo might be large, but hi-lo+1 miust fit into a long."""
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
isprime = True
for p in smallprimes:
if n % p == 0:
isprime = False
break
if isprime:
primes.append(n)
return primes
कॉलिंग range_f1(N-delta,N,smallprimes) एक लंबे समय (के बारे में 10 सेकंड) लेता है। आंतरिक पाश को 1 9 5170 बार कहा जाता है। मेरे पास इस एल्गोरिदम का एक संस्करण भी है जो लूप को एक सूची समझ के साथ बदलता है (यही वह है जिसे मैं वास्तव में प्रोफाइलिंग के लिए उपयोग करता हूं; प्रश्न का अंत देखें) लेकिन यह कोई तेज़ नहीं है।
def range_sieve(lo, hi, smallprimes):
"""Parameters as before"""
# So ugly! But SO FAST!! How??
delta = hi-lo+1
iamprime = [True] * delta # iamprime[i] says whether lo + i is prime
if lo<= 1:
iamprime[1 - lo] = False
def sillyfun(): # For profiling & speed comparison
pass
for p in smallprimes:
rem = lo % p
if rem == 0:
iamprime[0] = False
for i in xrange(p - rem, delta, p):
iamprime[i] = False
sillyfun()
if p >= lo and p <= hi:
iamprime[p - lo] = True
return [p + lo for (p, ami) in enumerate(iamprime) if ami]
इस बारे में 10 बार के रूप में तेजी से होता है, 2 सेकंड से भी कम समय लेता है:
दूसरे संस्करण (का एक बदसूरत कार्यान्वयन) एरेटोस्थेनेज की चलनी है। हालांकि, आंतरिक लूप (sillyfun()) को पिछले मामले की तुलना में 259982 गुना कहा जाता है। मुझे यह समझाने में कमी है कि यह तेज़ क्यों है।
मैंने सोचा कि शायद कारण यह है कि पहले एल्गोरिदम के आंतरिक पाश में मॉड्यूलर अंकगणित होता है, जबकि दूसरे के पास केवल असाइनमेंट होता है।
def range_f2(lo, hi, smallprimes):
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
try:
(1 for p in smallprimes if n % p ==0).next()
except StopIteration:
primes.append(n)
return primes
यहाँ हैं:
>>> from timeit import timeit
>>> timeit("10**9 % 2341234")
0.23445186469234613
>>> timeit("a[5000]=False", "a = [True] * 10000")
0.47924750212666822
यहाँ (कम पठनीय) मैं वास्तव में उपयोग पहले एल्गोरिथ्म के संस्करण है: हालांकि, निम्नलिखित मॉड्यूलर अंकगणितीय से भी तेजी से किया जाता है कि काम के अर्थ में लगता है range_f2() के लिए प्रोफाइलर को कॉल करने का नतीजा (ध्यान दें कि जनरेटिंग अभिव्यक्ति की संख्या का मूल्यांकन किया गया है):
>>> from cProfile import run as prof
>>> prof("range_f2(N-delta,N,sp)")
200005 function calls in 13.866 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 13.866 13.866 <string>:1(<module>)
195170 12.632 0.000 12.632 0.000 prime1.py:101(<genexpr>)
1 1.224 1.224 13.865 13.865 prime1.py:90(range_f2)
4832 0.009 0.000 0.009 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
यहाँ() range_sieve के लिए प्रोफाइलर परिणाम है:
>>> prof("range_sieve(N-delta,N,sp)")
259985 function calls in 1.370 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.003 0.003 1.370 1.370 <string>:1(<module>)
1 0.877 0.877 1.367 1.367 prime1.py:39(range_sieve)
259982 0.490 0.000 0.490 0.000 prime1.py:51(sillyfun)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
अंत में, यहाँ वह पूरा कोड है कि (एक बहुत मूर्खतापूर्ण तरीके से) छोटे अभाज्य संख्या की सूची उत्पन्न करता है, ताकि आप जाँच कर सकते हैं आपको क्या परिणाम मिलता है: http://pastebin.com/7sfN4mG4
अद्यतन लोकप्रिय मांग के अनुसार, कोड के पहले खंड के लिए प्रोफाइलिंग डेटा। आंतरिक लूप को कितनी बार निष्पादित किया जाता है इस पर कोई डेटा नहीं है, लेकिन यह बहुत स्पष्ट लगता है कि यह तीसरा जैसा ही है।
>>> prof("range_f1(N-delta,N,sp)")
4835 function calls in 14.184 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 14.184 14.184 <string>:1(<module>)
1 14.162 14.162 14.183 14.183 prime1.py:69(range_f1)
4832 0.021 0.000 0.021 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
मुझे लगता है कि इसे आपके 'प्रयास ... पकड़' तर्क के साथ करना है। क्या आप इसके बजाय कोड के पहले दो हिस्सों का परीक्षण कर सकते हैं? – Blender
मेरे पास अब परीक्षण करने के लिए पास कंप्यूटर नहीं है, लेकिन मेरा अनुमान यह है कि ऐसा इसलिए है क्योंकि पहले मामले में आप xrange की तुलना में अधिक बार सूची में फिर से शुरू होते हैं, जबकि दूसरे मामले में आप जेनरेटर xrange पर सूची की तुलना में अधिक बार फिर से सक्रिय करते हैं। आप समझ सकते हैं? xrange जैसे जेनरेटर पर पुनरावृत्तियों नियमित सूचियों पर पुनरावृत्तियों की तुलना में बहुत तेज़ है – Timur
@ ब्लेंडर: कोड का पहला हिस्सा तीसरा से थोड़ा सा धीमा है। मुझे लगता है कि कोशिश करें ... अपवाद उठाए जाने पर केवल विज्ञापन ओवरहेड पकड़ो, मुझे लगता है। लेकिन कोई समस्या नहीं, मैं प्रोफाइलिंग डेटा जोड़ दूंगा। –