2016-04-08 44 views
1

Bu iki çok benzer kod çok farklı hızlara sahiptir. Nedenini anlamıyorum. Birincisi ikincisinden (5s) çok daha yavaş (2 dk).N ama çok farklı CPU zamanı altında primleri oluşturmak için iki çok benzer kodlar

from numpy import sqrt 
primes = [2] 
for i in range(3, 1000000): 
    sq = int(sqrt(i)) 
    aux = False 
    for j in primes: 
     if j>sq: 
      aux = True 
     elif i%j==0: 
      break 
    if aux: 
     primes.append(i) 

=========================================== =======================

def isPrime(p, primes): 
     bound = numpy.sqrt(p) 
     i = 0 
     while(primes[i] <= bound): 
      if p % primes[i] == 0: 
       return False 
      i += 1 
     return True 

def compute_primes(bound): 
    primes = [] 
    primes.append(2) 
    for n in range(3, bound): 
     answer = isPrime(n, primes) 
     if answer: 
      primes.append(n) 
    return primes 

compute_primes(1000000) 
+0

birincisi geçersiz girinti vardır. Python koşmayacak. – recursive

+0

[zorunlu bir bildirim] (https://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth). –

cevap

5

performans farkı nedeni üst sınırdır birinci versiyonu iç döngü kırılmaz olmasıdır ikincisinin olduğu yere ulaştı. Her iki versiyonun da 11'un en baştan olup olmadığını kontrol ettiğini varsayalım. İlk sürüm, (2, 3, 5, 7) numaralı tüm küçük primerler için iç döngüyü çalıştıracak, ikincisi ise yalnızca sqrt(11): (2, 3)'dan daha küçük veya eşit değerleri kontrol edecektir.

onlar kabaca aynı çalışma süresi ulaşıldığında üst sınırı kırmak için ilk sürümü değiştirirseniz:

if j > sq: 
    aux = True 
    break