Klassenvorstellung: Primzahlen

[Die erinnerung]

Werner Salomon schrieb:

template< typename T >
bool isPrime( const T& x )
{
    const T divisor_max = T(std::sqrt( double(x) )); // erfordert #include <cmath>
    for( Prime< T > i; *i <= divisor_max; ++i )
        if( x % *i == 0 )
            return false;
    return true;
}

Ich finde die Idee echt genial. Ich habe sie in einer leicht modifizierten Version umgestzt!

Wegen der Iteratordiskussion:

Ich habe keinerlei Problem, bei den inkrementen und Dekrementen this zurückzugeben. Werde ich dann auch noch umsetzten.

Zum Thema Threadsicherheit: Wie genau mache ich das?

[hustbaer]

Werner Salomon schrieb:

hustbaer schrieb:

Und Funktionen die nicht Thread-safe sind sind mir generell ein Greul.

Thread-Safety ist im Kontext der Probleme aus Projecteuler i.A. schlicht überflüssig, und man könnte es relativ leicht hinzufügen.

OK.
Kommt halt drauf an was man haben will. Wenn man "nur" ein nettes Werkzeug für solcherlei Aufgaben will, dann OK.

Andrerseits kann man bei den Projecteuler Aufgaben vermutlich auch gut damit leben irgendwo ne globale Instanz einer Klasse zu haben. Statt freie Funktionen würde man dann einfach Memberfunktionen dieser Klasse aufrufen. Und die Klasse könnte man dann leicht Thread-safe machen (im Sinn von "verschiedene Instanzen in verschiedenen Threads = OK, selbe Instanz in verschiedenen Threads = nicht OK" -- die "üblichen Regeln" halt).

[hustbaer]

Die erinnerung schrieb:

Zum Thema Threadsicherheit: Wie genau mache ich das?

Die einfachste Variante wäre in jeder Funktion die auf deine statische Membervariable zugreift eine (ebenso statische) Mutex zu locken.
Dummerweise kostet das auch einiges an Performance. So ein Mutex Lock + Unlock ist nicht ganz billig.
Im Vergleich dazu zig oder hunderte Primzahlen-Kandidaten durchzuspulen ist es vermutlich sehr billig.
Im Vergleich dazu einfach nur in einen Vektor reinzugreifen und eine Zahl daraus zurückzugeben ist es vermutlich eher nicht so billig.

[volkard]

Werner Salomon schrieb:

Thread-Safety ist im Kontext der Probleme aus Projecteuler i.A. schlicht überflüssig, und man könnte es relativ leicht hinzufügen.

Autsch. Fürs ProjektEuler brauchste normalerweise auch keinen Cache der Primzahlen. Und falls doch, füllt man sich einfach vorher einen vector damit.

Den Generator wie Iteratoren aussehen zu lassen, naja...
Da liegt auch das Problem mit der Thread-Safety.

Dein Vorschlag, die IsPrime auszulagern, ach nöö, so aber nicht. Soll schon, wenn man schon alle Primzahlen speichern will, die Speicherung auch benutzen dürfen.

[volkard]

Die erinnerung schrieb:

Werner Salomon schrieb:

template< typename T >
bool isPrime( const T& x )
{
    const T divisor_max = T(std::sqrt( double(x) )); // erfordert #include <cmath>
    for( Prime< T > i; *i <= divisor_max; ++i )
        if( x % *i == 0 )
            return false;
    return true;
}

Ich finde die Idee echt genial. Ich habe sie in einer leicht modifizierten Version umgestzt!

Aber wenn Du uns nicht auf dem Laufenden hältst, werden wir bald schrecklich aneinander vorbeireden.
Wenn Du DIESE Version benutzt hast, wozu dann überhaupt noch die Primzahlen speichern? Weder Dein Primfaktorenprogramm noch die anderen Übungen brauchen, daß Du im Primzahlenfeld vorwärts und rückwärts laufen kannst, oder?

[Werner Salomon]

Die erinnerung schrieb:

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen bietet es sich an, die Hilfen von boost zu nutzen. Siehe dazu den boost.iterator.adaptor

Das werde ich mir mal anschauen. Dennoch könnte ein wenig Hilfe nicht schaden, da ich sowas noch nie gemacht habe!

Ich habe Dir mal einen Iterator für (Pseudo-)Primzahlen gebastelt. Du musst nur noch die Methode dereference() für die Primzahl-Bestimmung erweitern. Die Methode base() liefert Dir den Index auf den Container storedPrimes .

#include <boost/iterator/iterator_adaptor.hpp>

template< typename T >
class Primes : public boost::iterator_adaptor< Primes< T >, 
    std::size_t,    // gibt den unterliegenden Typ an, wird inkrementiert, dekrementiert und mit offset addiert/subtrahiert
    T,              // value_type des Iterators
    std::random_access_iterator_tag, // Ja - ist tatsächlich random-access; braucht man nicht, kriegt man aber geschenkt
    const T,        // Referenz-Typ; const ist wichtig, damit ist es ein const_iterator
    std::ptrdiff_t  // 'Abstand' zwischen zwei Iteratoren
>
{
public:
    Primes() : iterator_adaptor_(0) {} // jetzt ist base()==0
    friend boost::iterator_core_access;
private:
    T dereference() const
    {
        switch( base() )
        {
        case 0: return T(2);
        case 1: return T(3);
        }
        return T(6)*(base() >> 1) + (base() & 1? 1: -1);
    }
};

.. schon ist der Iterator fertig. Man kann nun mit den übliche Methoden *,++,--,[] darauf zugreifen.
siehe http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/iterator_adaptor.html

Gruß
Werner

[Die erinnerung]

Also. Ich habe jetzt einige Vorschläge umgesetzt und die Klasse noch ein bischen erweitert.

Das mit dem iterator habe ich bis jetzt noch nicht umgesetzt. Werde ich die Tage dann mal machen. Dennoch würde ich hier gerne auf Boost verzichten, da man das ja bräuchte, sollte ich die Klasse hier in eine Bibliothek umwandeln. Finde ich nicht so günstig. (Boost habe ich installiert. Ich verwende es auch gerne.)
Ebenfalls habe ich die Primes.cpp nicht umbenannt, da VC++ 2010 damit nicht wirklich zurechtkommt.

Ich habe den Code im Startpost aktualisiert und hier werde ich den Code auch nochmal posten!

Primes.h:

#ifndef Primes_H_
#define Primes_H_

#include <algorithm>
#include <cmath>
#include <fstream>
#include <vector>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>

template<class T = size_t, class Container = std::vector<T>>
class Primes
{
private:
	// Member fields/methods
	size_t internalCounter;

	// Static fields/methods
	static Container storedPrimes;
	static const T two;

	static void fillContainer();
	static bool internal_isPrime(const T& number);

	static std::string generateAutoSaveFileName();
	static unsigned int generateHash(const std::string& str);

public:
	// Constructors
	Primes();
	Primes(const T& number);

	// Member fields/methods
	Primes<T, Container>& operator++();
	Primes<T, Container>& operator--();

	const Primes<T, Container> operator++(int);
	const Primes<T, Container> operator--(int);

	const T& operator*();
	const T& operator[](size_t pos);

	// Static fields/methods
	static size_t getSize();
	static size_t getPointerPosition();
	static bool isPrime(const T& number);

	static void writeToStream(std::ostream& write_out);
	static void readFromStream(std::istream& read_in);

	static void writeToFile(const std::string& fileName);
	static void readFromFile(const std::string& fileName);

	static void autoSave();
	static void autoLoad();
};

// Initialize static fields

template<class T, class Container>
typename Container Primes<T, Container>::storedPrimes;
template<class T, class Container>
typename const T Primes<T, Container>::two = T(2);

#include "Primes.cpp"

#endif

Primes.cpp:

#ifndef Primes_CPP_
#define Primes_CPP_

#include "Primes.h"

// ======================
// Private static methods
// ======================

// static void fillContainer()
template<class T, class Container>
void Primes<T, Container>::fillContainer()
{
	if(storedPrimes.size() == 0)
	{
		storedPrimes.push_back(T(2));
		storedPrimes.push_back(T(3));
	}
}

// static bool internal_isPrime(const T& number)
template<typename T, typename Container>
bool Primes<T, Container>::internal_isPrime(const T& number)
{
    const T divisor_max = T(std::sqrt(long double(number)));

    for(Container::iterator it = storedPrimes.begin(); it != storedPrimes.end(); ++it)
	{
        if(*it > divisor_max)
			return true;

		if(number % *it == 0)
            return false;
	}

    return true;
}

// static std::string generateAutoSaveFileName()
template<typename T, typename Container>
std::string Primes<T, Container>::generateAutoSaveFileName()
{
	stringstream stream;
	string hash;

	stream << hex << generateHash(string(typeid(Primes<T, Container>).name()));
	hash = stream.str();
	std::transform(hash.begin(), hash.end(), hash.begin(), ::toupper);

	return string("autosave_#") + hash + string(".primes");
}

// static unsigned int generateHash(const std::string& str)
template<typename T, typename Container>
unsigned int Primes<T, Container>::generateHash(const std::string& str)
{
	unsigned int hash = 0;
	size_t size = str.size();

	for(size_t i = 0; i < size; ++i) 
		hash = 65599 * hash + str[i];

	return hash ^ (hash >> 16);
}

// ============
// Constructors
// ============

// Primes()
template<class T, class Container>
Primes<T, Container>::Primes() : internalCounter(0)
{
	fillContainer();
}

// Primes(const T& number)
template<class T, class Container>
Primes<T, Container>::Primes(const T& number) : internalCounter(pos)
{
	fillContainer();
}

// ==============
// Public methods
// ==============

// Primes<t, Container>& operator++()
template<class T, class Container>
Primes<T, Container>& Primes<T, Container>::operator++()
{
	++internalCounter;

	return *this;
}

// Primes<t, Container>& operator--()
template<class T, class Container>
Primes<T, Container>& Primes<T, Container>::operator--()
{
	--internalCounter;

	return *this;
}

// const Primes<t, Container> operator++(int)
template<class T, class Container>
const Primes<T, Container> Primes<T, Container>::operator++(int)
{
	Primes<T, Container> tmp(*this);
	++internalCounter;

	return tmp;
}

// const Primes<t, Container> operator--(int)
template<class T, class Container>
const Primes<T, Container> Primes<T, Container>::operator--(int)
{
	Primes<T, Container> tmp(*this);
	--internalCounter;

	return tmp;
}

// const T& operator*()
template<class T, class Container>
const T& Primes<T, Container>::operator*()
{
	return this-operator[](internalCounter);
}

// const T& operator[](size_t pos)
template<class T, class Container>
const T& Primes<T, Container>::operator[](size_t pos)
{
	internalCounter = pos;

	T currentNumber = storedPrimes.back();

	while(pos >= storedPrimes.size())
	{
		if((std::numeric_limits<T>::max() - currentNumber) < 2)
		{
			std::string message;
			std::stringstream stream;

			stream << pos;

			message = "An overflow occured while trying to generate the "
				    + stream.str()
					+ "th prime number. Your number type is likely too small!";

			throw std::overflow_error(message.c_str());
		}

		currentNumber += two;

		if(internal_isPrime(currentNumber))
			storedPrimes.push_back(currentNumber);
	}

	return *std::next(storedPrimes.begin(), pos);
}

// =====================
// Public static methods
// =====================

// static size_t getSize()
template<class T, class Container>
size_t Primes<T, Container>::getSize()
{
	return storedPrimes.size();
}

// static size_t getPointerPosition()
template<class T, class Container>
size_t Primes<T, Container>::getPointerPosition()
{
	return internalCounter;
}

// static bool isPrime(const T& number)
template<typename T, typename Container>
bool Primes<T, Container>::isPrime(const T& number)
{
    const T divisor_max = T(std::sqrt(long double(number)));

    for(Primes<T, Container> i; *i <= divisor_max; ++i)
        if(number % *i == 0)
            return false;

    return true;
}

// static void writeToStream(std::ostream& write_out)
template<typename T, typename Container>
void Primes<T, Container>::writeToStream(std::ostream& write_out)
{
	if(write_out)
	{
		size_t size = storedPrimes.size();
		const size_t bytesForT = sizeof(T);

		write_out.write((const char *) &size, sizeof(size_t));

		for(Container::iterator it = storedPrimes.begin(); it != storedPrimes.end(); ++it)
		{
			write_out.write((const char *) &*it, bytesForT);
		}
	}
}

// static void readFromStream(std::istream& read_in)
template<typename T, typename Container>
void Primes<T, Container>::readFromStream(std::istream& read_in)
{
	if(read_in)
	{
		size_t size;
		const size_t bytesForT = sizeof(T);
		T tmp;

		storedPrimes.clear();

		read_in.read((char *) &size, sizeof(size_t));

		storedPrimes.reserve(size);

		for(size_t i = 0; i < size; i++)
		{
			if(!read_in.good())
				throw ios_base::failure("Failed to read from stream!");

			read_in.read((char *) &tmp, bytesForT);

			storedPrimes.push_back(tmp);
		}
	}
}

// static void writeToFile(std::string& fileName)
template<typename T, typename Container>
void Primes<T, Container>::writeToFile(const std::string& fileName)
{
	std::ofstream write_file;

	write_file.open(fileName.c_str(), ios_base::binary | ios_base::out);
	writeToStream(write_file);
	write_file.close();
}

// static void readFromFile(std::string& fileName)
template<typename T, typename Container>
void Primes<T, Container>::readFromFile(const std::string& fileName)
{
	std::ifstream read_file;

	read_file.open(fileName.c_str(), ios_base::binary | ios_base::in);
	readFromStream(read_file);
	read_file.close();
}

// static void autoSave()
template<typename T, typename Container>
void Primes<T, Container>::autoSave()
{
	const char* const fileName = generateAutoSaveFileName().c_str();
	std::ifstream read_file;
	std::ofstream write_file;

	read_file.open(fileName, ios_base::binary | ios_base::in);

	if(write_file)
	{
		size_t size;

		read_file.read((char *) &size, sizeof(size_t));
		read_file.close();

		if(size < getSize())
		{
			write_file.open(fileName, ios_base::binary | ios_base::out);
			writeToStream(write_file);
			write_file.close();
		}
	}
	else
	{
		read_file.close();
	}
}

// static void autoSave()
template<typename T, typename Container>
void Primes<T, Container>::autoLoad()
{
	const char* const fileName = generateAutoSaveFileName().c_str();
	std::ifstream read_file;

	read_file.open(fileName, ios_base::binary | ios_base::in);

	if(read_file)
	{
		size_t size;

		read_file.read((char *) &size, sizeof(size_t));

		if(size > getSize())
		{
			read_file.close();

			read_file.open(fileName, ios_base::binary | ios_base::in);
			readFromStream(read_file);
		}
	}

	read_file.close();
}

#endif

[hustbaer]

Die erinnerung schrieb:

Ebenfalls habe ich die Primes.cpp nicht umbenannt, da VC++ 2010 damit nicht wirklich zurechtkommt.

Klar kommt der damit zurecht.
Was gibt's denn für ein Problem?

[volkard]

so, der code ist also endlich so kompliziert und so lang, wie du kannst, ohne auch nur ein bisschen mehr zu können. schäm dich! bau nicht auch noch werners verkomplizierunen ein, es sind doch nur harmlose primzahlen, die keinem was getan haben.

[volkard]

Die erinnerung schrieb:

Ebenfalls habe ich die Primes.cpp nicht umbenannt, da VC++ 2010 damit nicht wirklich zurechtkommt.

Die Templates mögen nicht gerne in einer *.cpp leben. Irgendwas anderes läuft da schief.

Die erinnerung schrieb:

Ich habe den Code im Startpost aktualisiert

Schlecht! Wer jetzt den Thread nochmal nachliest, kann die bisherigen Antworten gar nicht verstehen.

Die erinnerung schrieb:

und hier werde ich den Code auch nochmal posten!

Gut.
Besser, als aneinander vorbeizureden.

[Werner Salomon]

Die Erinnerung schrieb:

template<typename T, typename Container>
void Primes<T, Container>::autoSave()
{
    const char* const fileName = generateAutoSaveFileName().c_str();
    std::ifstream read_file;
    std::ofstream write_file;
 
    read_file.open(fileName, ios_base::binary | ios_base::in);
 
    if(write_file)
    { // usw.

.. hast Du diesen Code mal getestet? Lasse Dir mal nach Zeile 8 den Inhalt von fileName ausgeben. Das ist so eine der Gemeinheiten von C++.

ansonsten: die Klasse wird zu fett - wenig Code ist der bessere Code.
Klassen für Eier legende Wollmilchsäue sind i.A. nicht brauchbar.

Das Speichern und Laden der berechneten Primzahlen kann man wirklich auslagern, falls es überhaupt Sinn macht.

Gruß
Werner

[Die erinnerung]

Ich melde mich nochmal kurz:

Ich habe jetzt leider nicht mehr so viel Zeit. Ich werde ein wenig an der Klasse weiterarbeiten und euch auf dem Laufenden halten.

Eine Frage bezüglich der "unnötigen Funktionen": Wäre es sinnvol diese in einer verschachtelten Helferklasse unterzubringen? Und diese dann in einer anderen Quelldatei zu definieren?

Das ist ein wenig Neuland für mich. Ausfürhliche Antworten zur Frage wären Spitze!

[volkard]

Die erinnerung schrieb:

Ich melde mich nochmal kurz:

Ich habe jetzt leider nicht mehr so viel Zeit. Ich werde ein wenig an der Klasse weiterarbeiten und euch auf dem Laufenden halten.

Sollten der Primzahlengenerator und der Primzahlengenerator::Iterator nicht zwei Klassen sein?

Die erinnerung schrieb:

Eine Frage bezüglich der "unnötigen Funktionen": Wäre es sinnvol diese in einer verschachtelten Helferklasse unterzubringen? Und diese dann in einer anderen Quelldatei zu definieren?

Eigentlich lädt man Primzahlen nicht, sondern berechnet sie schnell.