Anfängerfragen zu C++

AlexSpritze

AlexSpritze

Bekanntes Mitglied
Und dann wär noch die Frage nach
Code: 
while(!kbhit()) {
        Sleep(100);
    }

Sieht aus, als ob du da pollst. Kann man das nicht auch eleganter lösen? Da müssten dann wohl die C++-Experten ran.
 
Gossi

Gossi

Bekanntes Mitglied
Mal eine Frage, gibt es in C++ eine schnellere Lösung um festzustellen, ob eine Zahl eine Primzahl ist, als so?

Code: 
bool isPrimzahl(int kandidat) {
    for(int i = 2; i < kandidat; i++) {
        if(kandidat % i == 0) {
            return false;
        }
    }
    return true;
}
 
I

Illuvatar

Top Contributor
Meinst du schneller im Sinne von "mit weniger Code" oder "mit kürzerer Laufzeit"?
Du müsstest zum Beispiel die Schleife nur bis zur Wurzel von [c]kandidat[/c] laufen lassen, das braucht aber natürlich mehr Code ;) Abgesehen davon gibt es auch noch ausgefeiltere Algorithmen.
 
Gossi

Gossi

Bekanntes Mitglied
Illuvatar hat gesagt.:
Meinst du schneller im Sinne von "mit weniger Code" oder "mit kürzerer Laufzeit"?
Du müsstest zum Beispiel die Schleife nur bis zur Wurzel von [c]kandidat[/c] laufen lassen, das braucht aber natürlich mehr Code ;) Abgesehen davon gibt es auch noch ausgefeiltere Algorithmen.
Zum Vergrößern anklicken....

Hmm, ok, werd ich mir mal anschauen, das pdf-Dokument les ich mir auch mal durch....

Hab jetzt einfach mal (schön blöd, dass ich das vorher nicht gesehen habe, die Funktion leicht umgeschrieben:

Code: 
bool isPrimzahl(int kandidat) {
    int halfKandidat = kandidat / 2;
    for(int i = 2; i < halfKandidat; i++) {
        if(kandidat % i == 0) {
            return false;
        }
    }
    return true;
}

Und siehe da:

129.719 s vorher
64.938 s nachher, immerhin schonmal etwas...
 
Zuletzt bearbeitet:
Gossi

Gossi

Bekanntes Mitglied
Wobei ich bei meiner "neuen Version" eine Primzahl mehr habe als in der alten ???:L

Edit:
Code: 
int halfKandidat = (kandidat / 2) + 1;
Funktioniert ^^

Edit 2:
So, eine weitere Verbesserung (auf unter 1 sekunde bei Primzahlen bis 1.000.000):
Code: 
double halfKandidat = sqrt(kandidat+1);
Bei kandidat, anstelle von kandidat+1 bekomme ich leider unstimmigkeiten bei den Primzahlen, aber so läufts ^^
 
Zuletzt bearbeitet:
Gossi

Gossi

Bekanntes Mitglied
So, wers einmal selber testen will, oder über den Quellcode motzen will :D

Main:
Code: 
#include "Prime.hpp"

using namespace std;

int main()
{
    int max = 1000000;
    Prime *prim = new Prime();
    prim->showAndWritePrimzahlen(max, prim->getPrimzahlen(max));
}

Prime.hpp:
Code: 
#ifndef PRIME_HPP_INCLUDED
#define PRIME_HPP_INCLUDED
#include <vector>
#include <fstream>
#include <math.h>
#include <iostream>

using namespace std;

class Prime {

    public:
        Prime();
        ~Prime();

        bool isPrimzahl(int kandidat);
        vector<int> getPrimzahlen(int max);
        void writePrimzahlen(int max, vector<int> primes);
        void showPrimzahlen(vector<int> primes);
        void showAndWritePrimzahlen(int max, vector<int> primes);

};

#endif // PRIME_HPP_INCLUDED

Prime.cpp:
Code: 
#include "Prime.hpp"

Prime::Prime() {}

Prime::~Prime() {}

bool Prime::isPrimzahl(int kandidat) {
    double halfKandidat = sqrt(kandidat+1);
    for(int i = 2; i < halfKandidat; i++) {
        if(kandidat % i == 0) {
            return false;
        }
    }
    return true;
}

vector<int> Prime::getPrimzahlen(int max) {
    vector<int> returnList;
    if(max >= 100) {
        int berechne = 0;
        int mod = max / 100;
        for(int i = 2; i <= max; i++) {
            if(i % mod == 0) {
                if(berechne < 10) {
                    cout << "Berechne: 00" << berechne << "% abgeschlossen" << endl;
                } else if(berechne < 100) {
                    cout << "Berechne: 0" << berechne << "% abgeschlossen" << endl;
                } else {
                    cout << "Berechne: " << berechne << "% abgeschlossen" << endl;
                }
                berechne += 1;
            }
            if(isPrimzahl(i)) {
                returnList.push_back(i);
            }
        }
    } else {
        for(int i = 2; i <= max; i++) {
            if(isPrimzahl(i)) {
                returnList.push_back(i);
            }
        }
    }
    return returnList;
}

void Prime::writePrimzahlen(int max, vector<int> primes) {
    vector<int>::iterator iterPrime = primes.begin();
    fstream out;
    out.open("test.txt", ios::out);
    out << max << endl;
    while( iterPrime != primes.end() ) {
        vector<int>::iterator thisone = iterPrime;
        iterPrime++;
        out << *thisone << " ist eine Primzahl" << endl;
    }
    out.close();
}

void Prime::showPrimzahlen(vector<int> primes) {
    vector<int>::iterator iterPrime = primes.begin();
    while( iterPrime != primes.end() ) {
        vector<int>::iterator thisone = iterPrime;
        iterPrime++;
        cout << *thisone << " ist eine Primzahl" << endl;
    }
}

void Prime::showAndWritePrimzahlen(int max, vector<int> primes) {
    showPrimzahlen(primes);
    writePrimzahlen(max, primes);
}
 
schalentier

schalentier

Gesperrter Benutzer
Regel Nummer 1:

new und delete vermeiden!

Code: 
int main()
{
    int max = 1000000;
    Prime prim();
    prim.showAndWritePrimzahlen(max, prim.getPrimzahlen(max));
}

Regel Nummer 2:
In C++ machst du immer Call by Value per default. D.h. sowohl in deinem getPrimzahlen(), als auch in allen andren Methoden, wird der vector<int> IMMER kopiert!

Besser waere in deinem Fall, den vector<int> als Feld direkt in die Klasse Prime zu packen.
 
Fu3L

Fu3L

Top Contributor
Meine Java Implementierung braucht 11 Millisekunden ohne Ausgaben... Wenn du das schlägst, bist du mittelmäßig ;) (Kleiner Anreiz sich Marcos Link anzusehen oder Wikipedia oder andere Quellen ;) )

Edit: Ich werfe mal das Stichwort "sieve of Eratosthenes" dazu^^ ;) Wäre vllt ganz interessant zu sehen, wie der Performanceunterschied dann tatsächlich ist zwischen Java und C++ in so einer Aufgabe.
 
Zuletzt bearbeitet:
Gossi

Gossi

Bekanntes Mitglied
So, mit Recherche im Internet hab ich meine Suche nun (bei 1.000.000 Zahlen) von von rund 500ms auf 50 bis 80 ms reduzieren....mal sehen, vielleicht finde ich ja noch mehr ^^

PS:
Wieviele Primzahlen findest du bis 1.000.000?

Edit:
Ausgabe bei meinem Programm:
Code: 
Zeit: 32ms
Zeit: 15ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 46ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 46ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 47ms
Zeit: 46ms
Zeit steht hierbei für die Berechnung der Primzahlen bis 1.000.000

Fu3L hat gesagt.:
Meine Java Implementierung braucht 11 Millisekunden ohne Ausgaben...
Zum Vergrößern anklicken....

???:L wie schaffst du in Java 11ms?
 
Zuletzt bearbeitet:
Fu3L

Fu3L

Top Contributor
Das ist schonmal kein schlechter Wert ;)
78498 Stück dürften es sein. Werde vllt heute Abend mal vergleichend die CPP Version meiner Java Implementierung testen, die ich grad wiederfand^^ (Grad keinen Compiler drauf)
Dann sehen wir auch, ob ich die nur schaffe, weil mein neuer PC cool ist^^ :D
 
Fu3L

Fu3L

Top Contributor
Schwankt auch bei mir zwischen 35 und 45 ms. Warum ist die erste Zeit eigentlich immer so kurz?

Hier mal das Sieb. Ich hoffe, dass das C++ und die Kommentare nicht zu grausig sind, ich kann C++ eigentlich gar nicht und es ist ein Jahr her^^ :D

Java: 
/*
 * Takes the pointer and points it onto a new array containing all primes in
 * the intervall [2;endNumber]
 *
 * returns the size of the array-1 (that is the last accessible index)
 *
 */

//Gets a reference to the pointer
int sievePrimes(int endNumber, long*& primes) {
	//If a field contains true it is crossed out
	int length = endNumber / 2;
	bool * sieve = new bool[length + 1];
	sieve[0] = true; //Represents 2
	double tmp = sqrt(endNumber / 2.);
	int sqrt = ceil(tmp);
	//1 -> 3; 2 -> 5; 3 -> 7 (saves all multiples of 2)
	for (int i = 1; i <= sqrt; i++) {
		//Not crossed out
		if (!sieve[i]) {
			long temp = i * 2 + 1;
			//Cross out all multiples of i starting at i²
			for (long n = 2 * i * (i + 1); n <= length; n += temp) {
				sieve[(int) n] = true;
			}
		}
	}

	//Fint out the size of the needed array
	int bound = 0;
	for(int i = 0; i <= length; i++) {
		if(!sieve[i]) {
			bound++;
		}
	}
	primes = new long[bound];
	//Reduce bound by 1 to use it as index when accessing the array
	bound--;
	int n = 1;
	primes[0] = 2;
	for(int i = 1; i <= length; i++) {
		if(!sieve[i]) {
			primes[n] = i*2+1;
			n++;
		}
	}
	delete [] sieve;
	return bound;
} //end sieving primes

Die Java Variante könnte den Vorteil oder Nachteil haben, dass ich TLongList nehme und daher nicht vorher nachzählen muss, wie groß das Array sein muss.
 
Fu3L

Fu3L

Top Contributor
Wenn ich das richtig in Erinnerung habe geht long * primes, das übergibst du dann der Methode sieve(1000000, primes) und die setzt da 'nen array rein^^ Ich mag Pointer und Referenzen nicht^^ :D
 
Gossi

Gossi

Bekanntes Mitglied
Okay....

Hab übrigens mein Programm mal nen bisschen getestet:
Java: 
Testsize: 1000
Zeit: 0ms
Testsize: 10000
Zeit: 0ms
Testsize: 100000
Zeit: 0ms
Testsize: 1000000
Zeit: 63ms
Testsize: 10000000
Zeit: 359ms
Testsize: 100000000
Zeit: 3344ms
Testsize: 1000000000
Zeit: 41906ms
Testsize: 1410065408
Zeit: 62188ms
Testsize: 1215752192
Zeit: 52453ms
Wird gegen ende doch recht langsam :D
 
G

Gast2

Gast
Da du ein Verfahren auf Basis der Probedivision angestellt hast ist das klar denn der Aufwand verält sich:

ad0c569ed32f9c0885065dc89ed93243.png
 
Gossi

Gossi

Bekanntes Mitglied
kappesf hat gesagt.:
Da du ein Verfahren auf Basis der Probedivision angestellt hast ist das klar denn der Aufwand verält sich:

ad0c569ed32f9c0885065dc89ed93243.png
Zum Vergrößern anklicken....

Das es langsamer wird, wusste ich, aber das er so lange braucht....

PS:

Die Zeit messe ich mit diesem Timer:
Code: 
#include <sys/timeb.h>
#include "Timer.h"


Timer::Timer() {}

Timer::Timer(const Timer& a){}

Timer::~Timer(){}

void Timer::start( void ) {
    ftime( &mStart );
}

void Timer::stop( void ) {
    ftime( &mStop );
}

long Timer::getMilliseconds( void ) {
    return (long)(1000 * (mStop.time - mStart.time) + mStop.millitm - mStart.millitm);
}
Hab ich mal im Internet gefunden..
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
W Datenbanken und einige Anfängerfragen Softwareentwicklung 13
G UML Anfängerfragen Softwareentwicklung 9

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben