Sieb des Eratosthenes optimieren

[Huffi]

Hallo,
ich fange gerade an mich ein wenig mit Python zu beschäftigen und programmiere dazu die Beispiele aus http://projecteuler.net/.
Aktuell versuche ich mich am Problem 10 und habe nun den Sieb des Eratosthenes Algorithmus auf Python übertragen und suche nun nach Optimierungsmöglichkeiten.

Code: Alles auswählen

def primeSieve(limit):
    import math
    sievebound = (limit-1) // 2 
    sieve = [False]*(sievebound+1)
    crosslimit = (math.floor(math.sqrt(limit))-1) // 2
    for i in range(1,crosslimit+1):
        if not sieve[i]:
            for j in range(2*i*(i+1),sievebound+1,2*i+1):
                sieve[j] = True
    
    #Liste mit Primzahlen wird erzeugt
    primes =[2]
    for i in range(1, sievebound+1):
        if not sieve[i]:
            primes.append(2*i+1)
    return primes

Ist es möglich die letzte Schleife in der die [False, False,.., False, True, ...] Liste in eine Liste mit Primzahlen übergeht durch eine funktionale Funktion zu ersetzen? Zur Zeit hänge ich gedanklich bei so etwas fest:
filter(isTrue,sieve), müsste dann aber noch auf den Index der True Werte zugreifen können.

[numerix]

Aktuell versuche ich mich am Problem 10 und habe nun den Sieb des Eratosthenes Algorithmus auf Python übertragen und suche nun nach Optimierungsmöglichkeiten.

Optimierung in welcher Hinsicht? Geschwindigkeit? Codelänge? Eleganz?

Ist es möglich die letzte Schleife in der die [False, False,.., False, True, ...] Liste in eine Liste mit Primzahlen übergeht durch eine funktionale Funktion zu ersetzen?
Zur Zeit hänge ich gedanklich bei so etwas fest:
filter(isTrue,sieve), müsste dann aber noch auf den Index der True Werte zugreifen können.

Erstens: Ja.
Zweitens: Richtig erkannt.

Du kannnst filter(None,sieve) verwenden, wenn du sieve zuvor statt mit booleschen Werten mit den Zahlen selbst initialisierst. Dann bleiben nur noch die Primzahlen übrig. - Das math-Modul brauchst du hier übrigens nicht. Ein '**0.5' tut es auch und statt floor() kannst du int() verwenden.

[Huffi]

Danke, das war der entscheidende Hinweis, das ich ja auch mit einer Liste aus Zahlen direkt arbeiten und diese dann auf None setzen kann wenn ich sie nicht mehr brauche. Wobei scheinbar die letzte Schleife garnicht so viel Zeit kostet gegenüber dem Wechsel zu einer Liste aus Zahlen.


Werd mich dann mal dran machen auch nicht nur die geraden Zahlen, sondern auch die Vielfachen von 3 von vornherein aus der Liste zu lassen.

Gibt es noch was hinsichtlich Eleganz zu verbessern?

[numerix]

Werd mich dann mal dran machen auch nicht nur die geraden Zahlen, sondern auch die Vielfachen von 3 von vornherein aus der Liste zu lassen.

Wenn du einen Anhaltspunkt brauchst, wie performant deine Implementation gelungen ist, kannst mal PRIME1 versuchen.

Gibt es noch was hinsichtlich Eleganz zu verbessern?

Da du den letztgültigen Code nicht gepostet hast: Schwer zu sagen ...

Zum obigen Code: Den Import würde man nicht in die Funktion packen.
Ansonsten finde ich das akzeptabel (ich nehme an, du verwendest Python 3.x; sonst würde ich range durch xrange ersetzen).

[Huffi]

Ich hatte den import nur für das Forum in die Funktion gepackt, das der Code dann per Copy & Paste läuft. Die Liste enthält nun ungerade Zahlen und wird gefiltert, so das ich die letzte Schleife ersetzten konnte und die Funktion läuft auch schneller. Der Nachteil ist es das ich mit sum(primeSieve_2(2*10**8)) mit dieser Version nun einen MemoryError bekomme, wohingegen die erste Version mit der boolschen Liste es noch verarbeiten kann. Wie kann ich den herausfinden wie groß Listen maximal sein dürfen, ehe sie den Speicher überschreiten?

Code: Alles auswählen

def primeSieve_2(limit):
    "Sieb verwendet eine Liste mit Zahlen statt Boolean"
    sievebound = (limit-1) // 2 
    #sieve ist eine Liste mit ungereadne Zahlen
    sieve = list(range(1,limit,2))
    crosslimit = ((int)(limit**0.5)-1) // 2
    for i in range(1,crosslimit+1):
        if sieve[i]:
            for j in range(2*i*(i+1),sievebound+1,2*i+1):
                sieve[j] = None
     
    #tausche 1 (nicht prim)  gegen  2 (gerade)
    sieve[0]=2
    #Liste mit Primzahlen wird gefiltert
    return filter(None,sieve)

[BlackJack]

@Huffi: Es ist in diesem Fall wohl nicht die Grösse der Liste an sich, sondern dass Du da 200 Mio. Objekte erzeugst, die ja auch alle Speicherplatz benötigen. Ich glaube so um die 12 Bytes braucht ein Objekt mindestens, da wären wir also schon bei 2.4 GiB für die Objekte. Und das ohne die Zeiger in der Liste die darauf verweisen.

Vielleicht solltest Du es bei True/False belassen und die Zahlen erst beim Erstellen der Primzahlenliste verwenden. Denn von den 200 Mio. Zahlen sind ja bei weitem nicht alle prim.

Edit: Bei `crosslimit` solltest Du übrigens nochmal sicherstellen, dass Du Python verwendest und nicht C oder Java oder so. Das tut nicht das was Du denkst was es tut bzw. sieht das sehr komisch aus.

[numerix]

Der Nachteil ist es das ich mit sum(primeSieve_2(2*10**8 )) mit dieser Version nun einen MemoryError bekomme, wohingegen die erste Version mit der boolschen Liste es noch verarbeiten kann.

Die Variante "Feld mit Zahlen" (statt boolesches Feld) ist nur für relativ kleine Siebe performant, weil das Erzeugen mittels range zu teuer wird.
Auf meinem (ziemlich alten) Rechner mit Python 2.5 geht es bis etwa 10⁶ mit dieser Variante ganz gut, mit zunehmender Größe wird dann das boolesche Sieb erheblich performanter.

[numerix]

Für die, die sich (so wie ich) für das Sieb des Eratosthenes begeistern können, gibt es ziemlich neu bei SPOJ eine Aufgabe, die man als echte Herausforderung für Python betrachten kann: Die Berechnung aller Primzahlen bis 10⁸ innerhalb von 10 (SPOJ!) Sekunden.

Wer es lieber langsam und kurz möchte, der kann sich beim SHORTENING CONTEST an der Aufgabe PRIMES versuchen:
Ein möglichst kurzes Programm, das alle Primzahlen bis 1 Mio. ausgibt. Es gibt schon Python-Lösungen unter 80 Bytes ...