Performance Optimierung

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.

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 ...

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

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

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.

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

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?

Dravere

Belli schrieb:

@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?

Da bin ich überfragt. Ich benutze die IDE Visual Studio, die macht mir die Schalter automatisch. Kenne die nicht auswendig ...
Aber ich denke mal wichtig sind die folgenden drei:
/O2 /Ot /GL

/O2 -> Maximize Speed
/Ot -> Favor Fast Code
/GL -> Enable link-time code generation

Grüssli