Codeoptimierung Primzahlenberechnung (Sieb des Eratosthenes)
-
Hallo,
habe mich mal an einem Programm versucht, um Primzahlen nach dem Sieb des Erastothenes zu berechnen. Es rechnet soweit richtig, ist aber (meiner Ansicht nach) zu langsam.So braucht das Programm z.B. für Zahlen bis 10^5 mehrere Minuten (Athlon X2, 3GHz, 8GB Ram).Hat jemand eine Idee, was ich besser machen könnte? Die Algorithmen habe ich von http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo25.php , bis auf eine Verfeinerung (die letzte) habe ich alle umgesetzt, dieser letzte kann meiner Ansicht nach aber nicht das Programm auf Durchschnittswerte beschleunigen.
Hier das Kernstück des Code (kann den Rest auch noch posten, wenn gewünscht.)cin>>n; //Zahl, bis zu der Primzahlen berechnet werden sollen. list<unsigned int> mylist; //Generierung einer Liste list<unsigned int>::iterator it; //Generierung eines Iterators for (long long int l=2; l<=n; ++l) //Füllung der Liste, beginnend mit "2" { mylist.push_back (l); } for (it=mylist.begin(); it!=mylist.end(); ++it) //Schleife für die Durchläufe zur Berechnung/Entfernung der Nichtprimzahlen { //Um Doppelrechnungen zu vermeiden, wird das Quadrat von i (p)gebildet, da Zahlen //innerhalb des Quadrats schon entfernt worden sind, da sie niedrige Teiler hatten. //1.Doppelrechnungen vermeiden p=((*it)*(*it)); if(*it<=sqrt(n)) //3.Laufbereich für i begrenzen. Aus i<=k<=(n/i) erhält man (i^2)<=n. { for(unsigned int k=1;(k<=(n/(*it)));++k) //Entfernung der "Vielfachen der Primzahlen"=Nichtprimzahlen ////2. Verlassen der Schleife,wenn k<=(n/i) { / m=((*it)*k)+p; //1.Doppelrechnungen vermeiden. Berechnung der Vielfachen von i*i+(i+k) //+p,da die Zahlen vor dem Quadrat von *it schon //entfernt worden sind. mylist.remove(m); //Entfernen der Vielfachen von i+p mylist.remove(p); //Entfernung der Quadratzahl von i; } } else { break; } }
-
list ist hier eine denkbar ungeeignete Datenstruktur. Du musst ja jedesmal die ganze Liste von vorne durchgehen, wenn du ein bestimmtes Element löschen möchtest. Das dauert vieeeel zu laaaaaaange. Das ist ungefähr linear in der Zeit mit der Listenlänge für jeden Löschvorgang.
Zwei Lösungsvorschläge:
1. Wenn du das mit dem Löschen der Elemente wörtlich nehmen willst, dann solltest du nutzen, dass die Zahlen sortiert sind. Dann findet man die zu löschenden Elemente viel schneller. Ein std::set macht das für dich. Da geht das Löschen bestimmter Elemente in logarithmischer Zeit. Schon viel besser.
2. Das obige ist zwar gut, aber immer noch nicht optimal. Vergiss das mit dem tatsächlichen Löschen der Zahl. Nimm einen vector<int> und setz einfach jeweils '1' für "ist noch dabei" und 0 für "ist gestrichen". Dann geht das "Löschen" in konstanter Zeit. Und dann rennt dein Algorithmus auch richtig schnell.
Es ist wichtig, dass du die Elemente nicht wirklich löscht, da der vector beim Löschen extrem langsam wäre.
-
ohne deinen code komplett durchgesehen zu haben:
1. Der Zugriff auf list elemente ist langsam(er). Nimm dafür liebr vector
2. du solltest die einträge aus der liste nicht während des algorithmus löschen - das kostet Zeit. Besser wäre es, einen vector mit n elementen zu erstellen (zB unsigned char [um Speicherplatz zu sparen] oder int) und diese auf 1 oder 0 zu setzen, falls die Zahl als Primzahlin Betracht kommt. Falls du nicht primzahlige Elemente löschen willst, kannst du es danach noch tun
3. die Elementfunktion .end() wird jeden Schleifendurchlauf aufgerufen. Das ist wahrscheinlich nicht so teuer, trotzdem kann man das auslagern und nur einmal berechnen.
-
Zusätzlich könntest du natürlich auch noch das sqrt(n) aus
if(*it<=sqrt(n))außerhalb der Schleifen einmal berechnen lassen und in einer konstanten Variablen speichern und daraus abrufen, als weitere "kleine" Optimierung.
-
Danke für Tips soweit. Werde die erstmal umsetzen und dann noch mal posten.
