Sieb des Eratosthenes

[pixewakb]

Hi, ich habe mich am Sieb des Eratosthenes versucht und zwei Implementationen programmiert. Ich meine, dass ich die Skripte schon etwas optimiert habe, wäre aber für Feedback dankbar:

(1) Mit Listen

Code: Alles auswählen

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit Listen
    '''
    liste = [2]
    liste.extend([i for i in range(3,zahl+1,2)])
  
    for z in range(2,zahl+1):
        if z in liste:
            exliste = [e * z for e in range(z,zahl+1) if e * z <= zahl]
            # print(z, exliste)
            if len(exliste) == 0:
                break
            else:
                for e in exliste:
                    if e in liste:
                        liste.remove(e)
    return liste
  
  
ergebnis = sieben(10000)
  
print(", ".join(map(str,ergebnis)),end=".\n")

(2) Mit Wörterbüchern

Code: Alles auswählen

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit einem Woerterbuch
    '''
    keys = [2]
    keys.extend([i for i in range(3,zahl,2)])
 
    woerterbuch = {}
 
    for key in keys:
        woerterbuch[key] = True  # True = prime (!)
           
    for key in keys:
        if woerterbuch[key] == True:
            vielfache = [i * key for i in range(key,zahl+1) if i * key <= zahl]
            # print(key,vielfache)
            if len(vielfache) == 0:
                break
            else:
                for item in vielfache:
                    if item in woerterbuch:
                        woerterbuch[item] = False
    return [i for i in keys if woerterbuch[i] == True]
 
ergebnis = sieben(1000)
 
print(", ".join(map(str,ergebnis)),end=".\n")

Für Feedback, Kritik und Verbesserungsvorschläge wäre ich dankbar. Wo könnte man Quellcode optimieren, wo habe ich Optimierungsmöglichkeiten übersehen? Für Kritik am Programmierstil bzw. auch an Benennungen bin ich offen - glücklichere Namen sind mir nicht eingefallen...

Quelle

[BlackJack]

@pixewakb: Die erste Implementierung ist sehr ineffizient. Es werden ständig neue Listen mit Zahlen angelegt und wieder verworfen. Und das entfernen aus `liste` ist auch nicht gut. Da wird die Liste immer von vorne linear durchsucht und bei einem `remove()` passiert das dann gleich *noch mal* und danach werden alle Elemente danach um eine Position nach vorne verschoben. Alleine letzeres sorgt dafür, dass die Elemente in `liste` bei dem Sieben für 10.000 Werte mindestens 57.520.284 mal betrachtet oder gar kopiert werden müssen. Und diese Zahl steigt nicht linear sondern quadratisch. Wenn man 100.000 Werte siebt dann müssen 6.031.270.260 mal die Elemente betrachtet oder kopiert werden. Und das *dauert*.

Im Normalfall werden bei einer Siebimplementierung zwei Listen angelegt — sofern man das Ergebnis nicht als Generatorausdruck zurück gibt. Eine, oft mit Wahrheitswerten die angeben ob die Zahl an dem Index eine Primzahl ist oder nicht, und die mit dem Ergebnis. Die Zahlen die weggestrichen werden sollen, werden dann auch nicht erst in einer Liste gesammelt, sondern gleich aus der ersten Liste gestrichen in dem an der Stelle der Wahrheitswert gesetzt wird und nicht durch Entfernen von Elementen aus einer Liste.

Die übliche Implementierung (Python 2):

Code: Alles auswählen

from math import sqrt


def sieve(limit):
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False
    for i in xrange(2, sqrt(limit) + 1):
        if is_prime[i]:
            for j in xrange(i * i, limit, i):
                is_prime[j] = False
    return (i for i, t in enumerate(is_prime) if t)

Dein zweiter Ansatz mit dem Wörterbuch setzt das ja fast um. Du speicherst dort zwar nur ein Flag für die ungeraden Zahlen (neben der 2), aber dieser Speichergewinn könnte gut von der höheren Komplexität von Wörterbüchern im Gegensatz zu Listen aufgefressen werden.

Auch im zweiten Ansatz werden mit `vielfache` wieder unnötige Listen angelegt. Wenigstens ist der Name besser als `exliste` oder gar `liste` und `woerterbuch`. Die sagen nämlich wenig bis gar nicht wofür die Werte in diesen Datenstrukturen im Programmkontext stehen.

Nur Flags für die ungeraden Zahlen speichern, könnte man zum Beispiel mit einer Liste so lösen (Python 2):

Code: Alles auswählen

from math import sqrt
from itertools import chain

def sieve(limit):
    is_prime = [True] * (limit >> 1)
    is_prime[0] = False
    for i in xrange(3, sqrt(limit) + 1, 2):
        if is_prime[i >> 1]:
            for j in xrange((i >> 1) + i, limit >> 1, i):
                is_prime[j] = False
    return chain([2], ((i << 1) + 1 for i, t in enumerate(is_prime) if t))

Ich weiss nicht ob sich das in Python auf einem üblichen PC tatsächlich lohnt. Der Quelltext ist eine „Portierung” von einer C-Implementierung die ich für den C64 geschrieben habe um Project-Euler-Probleme mit Primzahlen anzugehen. Wobei die C-Implementierung ein Bitfeld benutzt, also pro Byte die Flags für acht ungerade Zahlen speichert.

[pixewakb]

Danke dir fürs Feedback - das sorgt manchmal für die nötige Erdung, wenn ich meine, dass ich mich in Python schon gut ausdrücken könnte. Deine Ansätze schaue ich mir genau an.