Primsuche optimierung

[fail]

Hey ich bin bei Problem 10 beim Project Euler aber mein Programm braucht zu lange ich weiss nicht wie ich ihn schneller machen kann.

Code: Alles auswählen

def sieve(limit):
    Primelist=list(range(2,limit))
    for i in range(2,int(limit**0.5)+1):
        for k in range(i,int(limit/i+1)):
            try:
                index=Primelist.index(i*k)
                del Primelist[index]
            except ValueError:
                pass
    return Primelist

def main():
    summe=sum(sieve(2000000))
    print(summe)
if __name__ == '__main__':
    main()

[BlackJack]

@fail: Dein Algorithmus sucht ständig linear Zahlen in einer Liste und im Erfolgsfall wird dann mitten aus einer Liste ein Wert gelöscht, was auch wieder zu einem linearen kopieren aller Folgewerte um einen Platz weiter vorne führt. Damit explodiert die Anzahl der Vergleichs- und Verschiebeoperationen. Üblicherweise verwendet man bei Sievealgorithmen eine Liste mit Wahrheitswerten wo zur Indexzahl gespeichert wird ob es eine Primzahl ist oder nicht. Da muss man dann nicht linear Suchen oder gar Elemente aus der Liste löschen, sondern passt einfach direkt den zu einer Zahl gehörenden Wahrheitswert an.

Statt ``i * k`` zu rechnen hätte man bei `range()` eine passende Schrittweite angeben können.

[fail]

wie meinst du das mit der schrittzahl von range()?

[pillmuncher]

@fail:

Code: Alles auswählen

>>> for i in range(10, 20, 3):
...     print i
...
10
13
16
19

[Eugenie]

Für umfangreiche numerische Berechnungen lohnt sich auch numpy, das ist deutlich schneller als die Standardmöglichkeiten von Python.

[BlackJack]

@Eugenie: Projekt Euler-Probleme sind in der Regel nicht so rechenintensiv — vorausgesetzt man denkt über sie nach und geht nicht immer gleich mit einem „brute force”-Ansatz an sie heran. Wobei dass hier auch in reinem Python relativ schnell lösbar sein sollte. Die Frage ist die Summe aller Primzahlen unter zwei Millionen.

[Eugenie]

Na gut, hatte grad nix zu tun Mit dem Sieb des Eratosthenes: ist auch mit reinem Python noch schnell genug, kann sicherlich noch verbessert werden, sollte aber für den Threadstarter reichen (Python 2.7)

Code: Alles auswählen

import time
import math
import numpy as np

def versionNumpy(number):
    start = time.time()

    possiblePrimes = np.ones(number, dtype=np.bool)
    possiblePrimes[4::2] = 0
    for i in xrange(3,int(np.sqrt(number))+1,2):
        if possiblePrimes[i]:
            possiblePrimes[i*i::2*i] = 0 
    result = possiblePrimes.nonzero()[0][2:].sum(dtype=np.uint64)
                    
    end = time.time()
    print "numpy:", result
    print "time in sec:", (end-start)
    
def versionStandard(number):
    start = time.time()

    possiblePrimes = [0,0] + [1] * (number-2)
    for x in xrange(4,number,2):
        possiblePrimes[x] = 0
    for i in xrange(3,int(math.sqrt(number))+1,2):
        if possiblePrimes[i]:
            for x in xrange(i*i,number,2*i):
                possiblePrimes[x] = 0
    result = sum(i for i, prime in enumerate(possiblePrimes) if prime)
                    
    end = time.time()
    print "standard:", result
    print "time in sec:", (end-start)

if __name__ == "__main__":
    versionNumpy(2000000)
    versionStandard(2000000)

Ausgabe:

Code: Alles auswählen

numpy: 142913828922
time in sec: 0.0469999313354

standard: 142913828922
time in sec: 0.858999967575

[fail]

so?

Code: Alles auswählen

def sieve(limit):
    zahlen = [True]*(limit+1)
    zahlen[0] = False
    zahlen[1] = False
    Primzahlenliste=[]

    i = 2
 
    while i*i <= limit:
        if zahlen[i] == True: 
            for k in range(i*i,limit+1,i):
                zahlen[k] = False
        i+=1        
 
 
    
    for i, v in enumerate(zahlen):
        if v == True:
            Primzahlenliste.append(i)
            
 
    return Primzahlenliste


def main():
    summe=sum(sieve(2000000))
    print(summe)
if __name__ == '__main__':
    main()

[BlackJack]

@fail: So könnte man das machen, ja.

Ich würde `zahlen` anders benennen, damit die Bedeutung der Struktur deutlicher wird. Zum Beispiel `ist_primzahl`.

Die `Primzahlenliste` hält sich von der Schreibweise her nicht an den Style Guide for Python Code. Und der Datentyp sollte auch nicht Bestandteil des Namens sein. Also zum Beispiel `primzahlen`. Der Name wird ziemlich früh definiert. An der Stelle wird er ja noch gar nicht benötigt. Und man könnte sich diese Liste komplett sparen wenn man einen Generatorausdruck für den Rückgabewert verwendet. Oder zumindest eine „list comprehension”.

Anstelle der ``while``-Schleife würde sich eine ``for``-Schleife anbieten.

Die Vergleiche von Wahrheitswerten mit literalen Wahrheitswerten sind überflüssig. Da kommt doch sowieso nur wieder ein Wahrheitswert heraus. In beiden Fällen der den man sowieso schon aus der Liste hatte.

Code: Alles auswählen

def sieve(limit):
    ist_primzahl = [True] * (limit + 1)
    ist_primzahl[0] = ist_primzahl[1] = False
    
    for i in xrange(2, int(math.sqrt(limit)) + 1):
        if ist_primzahl[i]:
            for k in xrange(i * i, limit + 1, i):
                ist_primzahl[k] = False
    
    return (n for n, p in enumerate(ist_primzahl) if p)