Neden Eratosthenes Elek çok yavaş?

Question

Proje Euler'da bazı problemleri çözüyorum ve bir problemi çözmek için 2 milyon prim üretmeliydim. Eratosthenes Elemanı'nın uygulanmamın çok yavaş olduğu ortaya çıktı ama nedenini tam olarak bilmiyorum. Birisi bu uygulama ile ilgili büyük sorunları açıklayabilir. O kadar güzel olduğunu düşündüm ve sonra bunun tamamen korkunç anladım :(Ben çevrimiçi bunun başka uygulama buldum ve o kadar benim daha çok hızlıydı

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 

DÜZENLEME:.. Tüm cevaplar için teşekkürler! Bunun sonucu olarak, bu sorun, her elemandan (sadece asal olarak işaretlenecek olanlar yerine) geçtiği ve her seferinde yeni bir liste oluşturduğu için sorun olan süzgeç olmasıdır. . ve bir filtreleme yuvarlak ve çok daha hızlı çalışır Yeni kod:

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

Elek şuna benzer:

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 

Bu dış döngü bölen her asal için bir kez ulaşır ve ne zaman bir kez her numarayı işler. Yaklaşık 1/2 sayı, 2 ile bölünebilir, yaklaşık 1/3, 3 ile bölünebilir; asimptotik olarak, her bir sayının işlenecek ortalama sayısı 1 + n'ye kadar olan primlerin karşılıklılıklarının toplamıdır. This sum is about log(log(n)), böylece elek aritmetik sabit zaman olduğu varsayılarak, asimptotik zaman karmaşıklığı O(n*log(log(n))) vardır. Bu gerçekten iyi.

---

İşleviniz bunu yapmaz. filter, prime tarafından bölünebilir olup olmadığına bakılmaksızın, numbers'daki her öğeye gider. Her bir eleman, her bir asal için, onu bölen birinci asama kadar işlenir ve ana p'nin işlenmesi, numbers öğelerinin yaklaşık 1/p'sini çıkarır. Astarların diziliminin p [0], p [1], p [2] vb. Olmasına izin vermek ve numbers boyutlarının dizilimini n [0], n [1], n [2] vb. biz şu yaklaşık tekrarını vardır:

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] 

ve algoritma numbers boşalana kadar n değerlerin yukarı toplamına kabaca orantılı bir zaman alır. Bu dizinin davranışını analiz etmedim, ancak hesaplamalar, büyümenin O(n*log(log(n)))'dan çok daha kötü olduğunu gösteriyor.

Answer 2

Cprofile Running çoğu zaman filtresinde harcandığını göstermektedir Replac. Bir liste anlayışı ile filtreyi ing 2.

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

yaklaşık bir faktör ortalığı bir hızlandırır Ama bu gerçekten her yineleme ile numaraların listesini yeniden oluşturuyorsunuz olmasıdır temel sorun, çözmezse ve bu yavaş. Daha hızlı olan http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d sadece uygulamaları, asal olmayanları 0 veya benzeri ile değiştirerek işaretler. Eratosthenes