Performance Optimierung

[Fellhuhn]

b=2,c=sqrt(a); b<=c;

ist doch das gleiche wie:

b=2; b*b <= a;

Spart Zeit.

[betheman]

Dravere schrieb:

Stichwort: Sieb des Eratosthenes
PS: Ich hoffe du willst deinen Code nicht als C++ durchgehen lassen

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

[hustbaer]

Fellhuhn schrieb:

b=2,c=sqrt(a); b<=c;

ist doch das gleiche wie:

b=2; b*b <= a;

Spart Zeit.

Das ist jetzt ein Scherz, oder?

[Nexus]

betheman schrieb:

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

Wahrscheinlich meinte er <conio.h> und getch() , die nicht Standard-C++ entsprechen. <cmath> darf man wohl noch durchgehen lassen, auch wenn es bereits in C vorhanden war.

Zudem ist es sehr unschön, Variablen an Orten zu deklarieren, an denen man sie nicht braucht. Also keine globalen Variablen. Und die Schleifen-Zählvariablen kannst du auch gleich lokal im Schleifenkopf deklarieren.

[Dravere]

Nexus schrieb:

betheman schrieb:

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

Wahrscheinlich meinte er <conio.h> und getch() , die nicht Standard-C++ entsprechen. <cmath> darf man wohl noch durchgehen lassen, auch wenn es bereits in C vorhanden war.

Zudem ist es sehr unschön, Variablen an Orten zu deklarieren, an denen man sie nicht braucht. Also keine globalen Variablen. Und die Schleifen-Zählvariablen kannst du auch gleich lokal im Schleifenkopf deklarieren.

Genau, danke fürs übernehmen

Grüssli

[Nexus]

Dravere schrieb:

Genau, danke fürs übernehmen

So langsam kenn ich dich...

[pumuckl]

hustbaer schrieb:

Fellhuhn schrieb:

b=2,c=sqrt(a); b<=c;

ist doch das gleiche wie:

b=2; b*b <= a;

Spart Zeit.

Das ist jetzt ein Scherz, oder?

Wieso, stimmt doch. Wurzelziehn dauert länger als Multiplikation mit sich selbst
Dass man auch gleich 4 <= a hätte schreiben können ist dann wieder n anderes Thema

[Belli]

pumuckl schrieb:

hustbaer schrieb:

Fellhuhn schrieb:

b=2,c=sqrt(a); b<=c;

ist doch das gleiche wie:

b=2; b*b <= a;

Spart Zeit.

Das ist jetzt ein Scherz, oder?

Wieso, stimmt doch. Wurzelziehn dauert länger als Multiplikation mit sich selbst
Dass man auch gleich 4 <= a hätte schreiben können ist dann wieder n anderes Thema

Im 'Original' wird die Wurzel nur einmal bei Initialisierung der Schleife berechnet. Abbruchbedingung ist in der Folge immer ein einfacher Vergleich. Bei Deinem Verbesserungsvorschlag wird bei jedem Schleifendurchlauf die Multiplikation durchgeführt, um die Abbruchbedingung zu testen.
Und "gleich 4 <= a" zu schreiben, ist auch keine gute Idee, weil b bei jedem Schleifendurchlauf inkrementiert wird, und eben nicht immer 2 ist.

[Belli]

Ich hab das mal folgendermaßen gemacht:
Ich merke mir die bereits ermittelten Primzahlen und dividiere die zu testenden Zahlen nur noch durch diese und nicht mehr durch alle Zahlen. Wenn mein Quotient kleiner als der Divisor wird, ist Schluß, damit spare ich mir die Wurzel. Allerdings muß ich zweimal dividieren, einmal für den Quotienten, einmal für den Rest ... vielleicht kann man das noch vereinfachen.

#include <vector>
#include <iostream>

typedef unsigned int uint;

int main()
{
	uint maxTest = 10000000;

	std::vector<uint> pZahl;

	pZahl.reserve(1000000);

	pZahl.push_back(2);
	pZahl.push_back(3);

	uint max_ind = 1;

	for(uint zTest = 5; zTest <= maxTest; ++zTest)
	{
		uint div = 0;
		uint rest;
		uint ind = 0;
		uint quot;

		do
		{
			rest = zTest % pZahl[ind];
			quot = zTest / pZahl[ind];
			++ind;
		}while(rest != 0 && pZahl[ind] < quot && ind <= max_ind);

		if(rest)
		{
			++max_ind;
			pZahl.push_back(zTest);
		}
	}
	/*
	for(int i = 0; i < pZahl.size(); ++i)
		std::cout << pZahl[i] << std::endl; */
	std::cout << pZahl.size() << std::endl;
}

[betheman]

Ich habe gerade mal den Code von Belli getestet.
In einem Bereich von 1 bis 900.000 brauche ich mit meinem Programm 0.625 sek, belli's prog braucht dafür 1.218 sek.

Ich habe meinen Code jetz mal folgendermaßen umgeschrieben:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    double c;                           // Variabeln
    unsigned int counter=1,b;           // in main
    bool isprim=false;                  // deklarieren

    for(unsigned int a=3; a!=1000000001 ; a+=2)
    {
        isprim=true;
        for(b=2,c=sqrt(a) ; b<=c ; ++b)
        {

            if(!(a%b))
            {
                isprim=false;
                break;
            }
        }
        if(isprim)
            ++counter;
    }

    cout<<counter;
    cin.get();          // cin.get() statt getch()
}

Der Grund, warum ich b und c nicht in der zweiten schleife deklariere ist, dass die ja dann bei jedem Aufruf der kleinen Schleife neu deklariert würde. Das bedeutet doch, dass nach dem verlassen der inneren Schleife die Variable zerstört wird und bei einem erneuten Aufruf wieder erstellt werden muss. Ist es nicht schneller, diese Variable daher außerhalb der inneren Schleife zu deklarieren, damit b nur initialisiert und nicht nochmal deklariert werden muss?

Und zu sqrt(): Im Prinzip reicht es ja, die Wurzel nur "bis zum Komma" zu errechnen, da ja eine int variable mit der Wurzel vergleichen wird. Es istalso völlig egal ob a mit 3 oder mit 3.162... verglichen wird. Kann man das nicht nutzten um eine eigene Funktion zu schreiben, die schneller ist als sqrt() ?

[Dravere]

#include <ctime>
#include <vector>
#include <iostream>

int main()
{
	std::clock_t start = std::clock();

	unsigned int counter = 1;
	unsigned int const maxLimit = 900000;
	std::vector<bool> primVec(maxLimit, true);

	for(std::vector<bool>::size_type i = 2; i < primVec.size(); ++i)
	{
		if(primVec[i])
		{
			++counter;

			for(std::vector<bool>::size_type r = i + i; r < primVec.size(); r += i)
			{ primVec[r] = false; }
		}
	}

	std::cout << (std::clock() - start) << "ms" << std::endl;
	std::cout << counter << std::endl;

	/*for(std::vector<bool>::size_type i = 1; i < primVec.size(); ++i)
	{
		if(primVec[i])
		{ std::cout << i << ", "; }
	}*/

	return 0;
}

Überseh ich etwas? Wenn nicht, dann läuft der Code durch mit weniger als 50ms

Grüssli

[betheman]

Habs grad nochmal probiert:
Dravere's Variante: 375 ms (Allerdings zeigt die Version eine Zahl zuviel an)
Meine Variante: 718 ms
Billi's Variante: 1234ms

wtwas Abgeänderte Version von Dravere: 128ms (siehe unten)

//kein .size() mehr bei JEDEM Schleifendurchlauf
#include <ctime>
#include <vector>
#include <iostream>

int main()
{
    std::clock_t start = std::clock();

    unsigned int counter = 1;
    unsigned int const maxLimit = 900000;
    std::vector<bool> primVec(maxLimit, true);

    for(std::vector<bool>::size_type i = 2, c = primVec.size() ; i<c ; ++i)
    {
        if(primVec[i])
        {
            ++counter;

            for(std::vector<bool>::size_type r = i + i, d = primVec.size() ; r<d; r += i)
            { primVec[r] = false; }
        }
    }

    std::cout << (std::clock() - start) << "ms" << std::endl;
    std::cout << counter << std::endl;

    return 0;
}

Theoretisch würde man doch noch mehr Performance gewinnen, wenn man nicht mit dem Indexoperator sondern mit Iteratoren auf den Vector zugreift. Allerdings weis ich nicht, wie man i+i und r+=i in der inneren Schleife schreiben soll, wenn i und r Iteratoren sind.

[Belli]

Ich habe nochmal geändert: zTest in der äußeren Schleife immer um 2 inkrementiert (Ich habe den Algorithmus vor Jahren in Cobol geschrieben, und jetzt auf die Schnelle nach C++ übersetzt, dabei habe ich das übersehen). Das bringt nicht soooo viel.
Was aber eine Beschleunigung um mehr als 50% gebracht hat, ist, statt eines Vectors mit seiner push_back - Methode ein genügend großes POD - Array zu nehmen. Ich habe hier gerade nur einen langsamen Rechner (1GHz Athlon), deshalb erspare ich mir mal die absoluten Zahlen.

Ich denke aber, das Sieb des Eratosthenes wird nicht zu schlagen sein ...

[Belli]

Ich habe weitere Zeit gespart, indem ich statt Division und Modulo die Standardfunktion div benutze, die Quotient und Rest liefert.
Auf diesem lahmen Rechner hier bin ich von 3.8 Sekunden in meiner Ursprungsversion auf nun 1 Sekunde gekommen.
So sieht das jetzt aus:

#include <iostream>
#include <ctime>

typedef unsigned int uint; 

int main() 
{ 
    uint maxTest = 1000000; 

	 uint pz[100000];

	 pz[0] = 2;
	 pz[1] = 3;

    uint max_ind = 1;
	 uint ind;
	 div_t res;

	 clock_t begin = clock();

	 for(uint zTest = 5; zTest <= maxTest; zTest += 2, ind = 0) 
    { 
        do 
        { 
				res = div((int)zTest, (int)pz[ind]);
            ++ind; 
        }while(res.rem != 0 && pz[ind] < res.quot && ind <= max_ind); 

        if(res.rem) 
        { 
            ++max_ind; 
				pz[max_ind] = zTest;
        } 
    } 

	clock_t ende = clock();
	double diff = static_cast<double>((ende - begin)) / CLOCKS_PER_SEC;
	std::cout << diff << std::endl;

   std::cout << max_ind + 1 << std::endl; 
}

[Dravere]

@betheman,
Sag mal, welcher Compiler benutzt du? Jedenfalls sicher nicht den den MSVC. Also nehme ich mal an, dass du den GCC verwendest. Hast du dort auch die Optimierungen angestellt? Oder ist der MSVC wirklich so viel besser?

Grüssli

[betheman]

ich benutze CodeBlocks v1.0 GNU GCC Compiler mingw32 (alle Einstellungen auf Standard, keine Ahnung ob ich da was optimieren kann, kenn mich nicht wirklich gut aus mit Compilern ^^)

Der neue Code von Belli läuft bei mir (bei Allen Zahlen bis 900000) läuft bei mir am schnellsten

[Belli]

Jetzt hast Du mich auf was gebracht. An Optimierungsschalter hab ich noch gar nicht gedacht. Aber die Angabe von -O, -O1, -O2 oder -O3 führt zu einem Programmabsturz zur Laufzeit. Das macht nun ein bißchen stutzig ...
Ich benutze übrigens den gcc.

[Belli]

do 
        { 
	res = div((int)zTest, (int)pz[ind++]);
         //++ind; 
        }while(res.rem != 0 && pz[ind] < res.quot && ind <= max_ind);

und

if(res.rem) 
        { 
            //++max_ind; 
	     pz[++max_ind] = zTest;
        }

Keine Extra-Anweisung für das Inkrement bringt tatsächlich noch mal eine Kleinigkeit, die sich bei einem größeren zu testenden Bereich sicher signifikant bemerkbar macht.

[Dravere]

#include <ctime>
#include <iostream>
#include <algorithm>

int main()
{
	std::clock_t start = std::clock();

	unsigned int counter = 1;
	std::size_t const maxCount = 900000;
	bool* prims = new bool[maxCount];

	std::fill_n(prims, maxCount, true);

	for(std::size_t i = 2; i < maxCount; ++i)
	{
		if(prims[i])
		{
			++counter;

			for(std::size_t r = i + i; r < maxCount; r += i)
			{ prims[r] = false; }
		}
	}

	std::cout << (std::clock() - start) << "ms" << std::endl;
	std::cout << counter << std::endl;

	/*for(std::vector<bool>::size_type i = 1; i < primVec.size(); ++i)
	{
		if(primVec[i])
		{ std::cout << i << ", "; }
	}*/

	delete[] prims;

	return 0;
}

MSVC volle Optimierung auf Geschwindigkeit: 0 - 16ms.
std::clock reicht da nicht mehr aus, hat eine zu schlechte Auflösung

GCC habe ich auf diesem Computer nicht, daher kann ich es nur mit dem MSVC testen.

Edit: Einen Header vergessen. Und die Ausgabe sollte man vielleicht noch anpassen (das im Kommentar).

Grüssli

[Belli]

In meinem Code ist ein gemeiner Fehler:
Die Variable ind muß bei der Definition mit 0 initialisiert werden, die Initialisierung im Schleifenkopf greift erst nach dem ersten Schleifendurchlauf. Dann klappts auch mit den Optimierungsschaltern. Damit komm ich auf 17 Sekunden bei einem Testbereich von 10.000.000 (Das Array pz muß dann 1.000.000 Elemente haben, die auf dem Heap angelegt werden müssen).

@Dravere:
Morgen abend könnte ich auch mal den MS-Compiler nutzen, welche Schalter kann ich dort auf der Kommandozeile dem cl.exe für Optimierung mitgeben?