Klassenvorstellung: Primzahlen

Die erinnerung

volkard schrieb:

Ich fürchte, vor lauter Verliebtheit in die Generizität verlierst Du den Blick für was gebraucht wird und verbaust Dir Optimierungsmöglichkeiten.

Das ganze möchte ich vieleicht später als kleine Bibliothek anbieten. Und da es bistimmt Klassen gibt, die größere Zahlen als unsigned long long zulassen, wollte ich diese Möglichkeit dem Programmierer nicht wegnehemen.
ich könnte allerdings noch einen default-Type für T festlegen...

volkard schrieb:

bool prime? Wenn man künstliche Variablen braucht, Flags, um goto zu sparen, ist es immer eine Überlegung wert, ob man nicht etwas in eine Funktion auslagern möchte.

Ich habe eigentlich gelernt, dass man goto 's um jeden Preis vermeiden sollte.

volkard schrieb:

Und was soll das denn?!
if(!(prime = (currentNumber % *it) != 0))

Die Zeile überprüft, ob die aktuelle Zahl currentNumber duch den Wert im Iterator it teilbar ist und speichert den Wert dann in prime . Das wird dann invertiert, weil ich die Schleife nur verlassen möchte, wenn der Test fehlgeschlagen ist. Also es sich um keine Primzahl handelt.
Die Flag brauche ich, um nach der Schleife zu entscheiden, ob ich die Zahl currentNumber in der Liste der Primzahlen speichern soll, oder nicht.

hustbaer

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

Weiters sind deine Inkrement und Dekrement Operatoren etwas eigenwillig indem sie etwas anderes als eine Kopie von bzw. Referenz auf *this zurückgeben. Würde ich ebenfalls so nicht machen.

Das statische Member storedPrimes ist problematisch was Thread-Safety angeht.

Statt sprintf_s würde ich einen stringstream verwenden - die bessere Performance von sprintf_s spielt hier keine Rolle, und mit stringstream hast du eine potentielle Fehlerquelle (zu kleiner Puffer) weniger.

Der "is prime" Loop gehört in eine eigene Funktion. Zumindest wenn du diesen naiven Algorithmus verwendest (der alles andere als schnell ist). Dadurch sparst du dir die Hilfsvariable und das break .

Der Sinn des 2. Template-Parameters ist mir auch nicht ganz klar. Wieso sollte man wollen dass die Klasse etwas anderes als std::vector verwendet? Und unnötigerweise lass ich meinen Klassen nicht vorschreiben was sie intern zu verwenden haben.

Genaugenommen ist mir sogar der Sinn des 1. Template-Parameters nicht ganz klar, da es mMn. wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist ~~ 4 Mrd. Bis 4 Mrd. gibt es so Pi * Daumen 180 Mio. Primzahlen. Bei 4 Byte pro Zahl macht das 720 MB. Das liegt schon in der Grössenordnung wo man auf 32 Bit Systemen anfängt sich Sorgen um std::bad_alloc zu machen (die 720 MB müssen ja am Stück verfügbar sein!).
Und auf 64 Bit Systemen geht dir sowieso der Speicher aus bevor size_t überläuft.

Wieso du 2x ++ machst statt 1x += 2 ist mir auch nicht klar.

Dein Overflow-Test ist für signed Typen undefiniert. Besser wäre vor dem += 2 zu prüfen ob es noch geht. z.B. über (std::numeric_limits<T>::max() - currentNumber) >= 2 .
(Wenn du natürlich fix size_t verwendest, das per Definition unsigned ist, dann ist der Overflow-Test wieder OK.)

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

hustbaer

Die erinnerung schrieb:

Ich habe eigentlich gelernt, dass man goto 's um jeden Preis vermeiden sollte.

Und du hast nicht verstanden was volkard dir sagen wollte.
Du sollst da kein goto hinschreiben sondern den Loop in eine Funktion auslagern.

if( ! (prime = (currentNumber % *it) ! = 0))

hustbaer

Auweh, hätte ich fast übersehen...

primzahlen[2] = 42;
std::cout << "Die 2. Primzahl ist " << primzahlen[2] << ".\n";
std::cout << "Ne, ehrlich, ist so.\n";

Die erinnerung

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

Weiters sind deine Inkrement und Dekrement Operatoren etwas eigenwillig indem sie etwas anderes als eine Kopie von bzw. Referenz auf *this zurückgeben. Würde ich ebenfalls so nicht machen.

Wie würdest du es machen? Wie ja gesagt, mir fehlt die Übung.

hustbaer schrieb:

Das statische Member storedPrimes ist problematisch was Thread-Safety angeht.

Selbe Sache.

hustbaer schrieb:

Der "is prime" Loop gehört in eine eigene Funktion. Zumindest wenn du diesen naiven Algorithmus verwendest (der alles andere als schnell ist). Dadurch sparst du dir die Hilfsvariable und das break .

Ich habe das jetzt ausgelagert. Mir ist leider kein andere Algorithmus eingefallen!

hustbaer schrieb:

Der Sinn des 2. Template-Parameters ist mir auch nicht ganz klar. Wieso sollte man wollen dass die Klasse etwas anderes als std::vector verwendet? Und unnötigerweise lass ich meinen Klassen nicht vorschreiben was sie intern zu verwenden haben.

Wer weiß. Vieleicht hat der Nutzer einen effiktiveren Container zur Verfügung, oder möchte einfach einen anderen verwenden. Macht std::vector ja genau so. (mit dem allocator)

hustbaer schrieb:

Genaugenommen ist mir sogar der Sinn des 1. Template-Parameters nicht ganz klar, da es mMn. wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist ~~ 4 Mrd. Bis 4 Mrd. gibt es so Pi * Daumen 180 Mio. Primzahlen. Bei 4 Byte pro Zahl macht das 720 MB. Das liegt schon in der Grössenordnung wo man auf 32 Bit Systemen anfängt sich Sorgen um std::bad_alloc zu machen (die 720 MB müssen ja am Stück verfügbar sein!).
Und auf 64 Bit Systemen geht dir sowieso der Speicher aus bevor size_t überläuft.

Wenn jemand z.B. eine eigene Zahlenklasse oder ähnliches hat, oder einfach einen kleineren Bereich haben will. Wer weiß.
(P.S.: Ich war selbst schon mal in solch einer Situation, in der ich eine Templateklasse hätte besser brauchen können)
(P.P.S.: Ich persönlich kenne nämlcih zwei recht spezielle Klassen. Die eine ist eine Zahlenklasse, die weit über jeden normalen Datentyp herausgeht. Die andere ist eine Containerklasse, die wenn sie zu viel RAM verbraucht gezielt auf die Festplatte auslagert. Somit kann sie deutlcih mehr als der RAM speichern.)

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

Primzahlen... Wer braucht die nicht??? (Primzahlen, fand ich halt schon immer interessant. Und ich habe mir einen kleinen Primfaktorenzerleger programmiert. Da verwende ich die Klasse)

hustbaer schrieb:

Auweh, hätte ich fast übersehen...

primzahlen[2] = 42;
std::cout << "Die 2. Primzahl ist " << primzahlen[2] << ".\n";
std::cout << "Ne, ehrlich, ist so.\n";

Habs gefixt! habe ja ganz vergessen, dass man die Refferenzen const machen muss/sollte!

P.S.: Danke für die konstruktive Kritik und die Verbesserunsgvorschläge.
Ich habe außerdem die Klasse im Startpost aktualiesiert!

knivil

wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist

Ich haette auch gern auf 32 Bit Systemen 64 Bit Primzahlen. Fuer einzelne verwende ich dort auch uint64_t.

Bei 4 Byte pro Zahl macht das 720 MB

Unter Verwendung von prime wheels und Bitsets kann der Speicherbedarf drastisch reduziert werden.

Tja zur Klasse ... ich mach es anders. Hierarchisch:
1.) prime_wheel - Spezifierziert das Pimzahlsieb zur Erzeugung von Primzahlen/Sieben
2.) primes - Container mit allen Primzahlen in einer bestimmten Range (echt vorhanden, Speicherbedarf O(n) )
3.) prime_sieve - Pseudocontainer fuer Primzahlen in bestimmter Range (nicht echt vorhanden, ezeugt beim Iterationsprozess, Speicherbedarf O(k), wobei k fix im Bereich des L1-Caches liegt)

Alle beiden Containertypen liefern Iteratoren um mit den Primzahlen zu arbeiten.

Btw. deine is isPrime-Funktion ist falsch. Eine gegebene Zahl kann durch Primzahlen ausserhalb deines Containers teilbar sein.

Die erinnerung

knivil schrieb:

Btw. deine is isPrime-Funktion ist falsch. Eine gegebene Zahl kann durch Primzahlen ausserhalb deines Containers teilbar sein.

Nicht in dem Zusammenhang, in dem ich sie aufrufe. Ich prüfe ja alle ungeraden Zahlen der Reihe nach. Also sind (wenn ich die Funktion aufrufe) alle Primzahlen, die kleiner als die Zahl sind, vorhanden.

EDIT:

Ich habe die Performance der isPrime -Funktion erhöht.

Nathan

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

RandomAccessIteratoren brauchen operator[].

hustbaer

knivil schrieb:

wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist

Ich haette auch gern auf 32 Bit Systemen 64 Bit Primzahlen. Fuer einzelne verwende ich dort auch uint64_t.

Bei 4 Byte pro Zahl macht das 720 MB

Unter Verwendung von prime wheels und Bitsets kann der Speicherbedarf drastisch reduziert werden.

Ich meinte das schon im Zusammenhang mit seiner Implementierung.

hustbaer

Nathan schrieb:

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

RandomAccessIteratoren brauchen operator[].

Die liefern aber nicht das zurück was sein operator[] zurückliefert.

knivil

hustbaer schrieb:

Ich meinte das schon im Zusammenhang mit seiner Implementierung.

Ja, die Antwort war auch eher dayu gedacht, um yu yeigen, wo die Reise hingehen sollte.

Ansonsten:

#include "Primes.cpp"

Bitte nenne die Datei "Primes.impl" oder "Primes.incl" oder ... . Die Endung cpp wird von den meisten IDEs automatisch als Uebersetzungseinheit betrachtet.

hustbaer

Die erinnerung schrieb:

Habs gefixt! habe ja ganz vergessen, dass man die Refferenzen const machen muss/sollte!

Ich würde die eher einfach by-value zurückgeben.

Die erinnerung schrieb:

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

Primzahlen... Wer braucht die nicht??? (Primzahlen, fand ich halt schon immer interessant. Und ich habe mir einen kleinen Primfaktorenzerleger programmiert. Da verwende ich die Klasse)

Ich brauch praktisch nie Primzahlen.

Und wenn doch, dann eher eine Funktion der ich eine Zahl geben kann, die mir die nächste Primzahl die >= oder <= dieser Zahl ist zurückgibt.

Aber für "gib mir die ersten N Primzahlen" hatte ich bisher noch nie bedarf. Ausgenommen bei diversen "Programmieraufgaben" wo genau das gefragt war.

Werner Salomon

Hallo,

Kritik hast Du ja schon reichlich geerntet, also ich finde so eine Klasse gut! Gut deshalb weil man das ganze Brimborium mit den Primzahlen hinter dieser Schnittstelle gut unterbringen kann.
Das muss ich sogar gut finden, da ich mir vor Jahren selbst so ein Ding gebaut habe

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

liegt wohl daran, dass Du noch nie ein Problem aus projecteuler.net bearbeitet hast.

Zwei Dinge rufen dann doch nach Verbesserungsbedarf.
1.) Du kannst deutlich an Performance gewinnen, wenn Du bei der Suche nach einem möglichen Teiler nur bis <=sqrt(number) statt bis number läuft. Dies macht sich umso stärker bemerkbar, je größer die Primzahlen werden.
2.) Die Funktion zur Bestimmung ob eine Zahl eine Primzahl gehört isoliert - hast Du schon gemacht.

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

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.

Ich finde es gut, wenn Du Deine Klasse hier zur Diskussion stellst.
Gruß
Werner

Die erinnerung

Werner Salomon schrieb:

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

Könntest du etwas konkreter werden? Ich verstehe leider nciht ganz, was du meinst.

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!

Außerdem danke für deine aufbauende Worte. Und für den Tipp mit der Wurzel. Ich hatte jetzt vorübergehend den zu überprüfenden Wert quadriert und mit der Zahl verglichen. Diese methode ist besonmders bei goßen Primzahlen deutlich effizienter. Habe ich auch in meinen Test festgestellt!

Werner Salomon

Die erinnerung schrieb:

Werner Salomon schrieb:

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

Könntest du etwas konkreter werden? Ich verstehe leider nciht ganz, was du meinst.

Einfach eine Funktion, in der die Klasse Prime wieder benutzt wird - also etwa so:

// --   freie Funktion 'isPrime' liefert 'true', falls x eine Primzahl ist.
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;
}

.. und die benutzt Du dann wie gehabt in const T& Primes<T, Container>::operator[](size_t pos) . Eventuell musst Du noch einen Prototyp vor die Klasse schreiben.

Gruß
Werner

hustbaer

@Werner Salomon
Das meinte ich ja: ausserhalb von diversen "Übungen" hab' ich noch nie Primzahlen gebraucht. Ich meinte mal welche zu brauchen als ich für ein Projekt nen eigenen Hashtable implementieren wollte. Hat sich dann aber - wie es meist der Fall ist - herausgestellt, dass es nicht sinnvoll/nötig ist hier was selbst zu basteln.

Und sollte ich je welche brauchen, dann such ich mir ne passende Library, die dann auch entsprechend schnell ist

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

Naja, ist sie eben nicht. Sie tut bloss ein bisschen ähnlich wie ein Iterator. Das war ja auch einer meiner Kritikpunkte.

Guck dir mal die Returnwerte der ++/-- Operatoren an und was der [] Operator macht...

Und Funktionen die nicht Thread-safe sind sind mir generell ein Greul. Genau so wie Funktionen die ungefragterweise mächtig Speicher verbrauchen, und diesen nach Aufruf der Funktion nicht mehr freigeben. Beides ist hier gegeben. Dummerweise hab' ich keinen Vorschlag wie man das besser machen kann, ohne gleichzeitig die Verwendung wesentlich unparktischer zu machen...

Werner Salomon

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

Naja, ist sie eben nicht. Sie tut bloss ein bisschen ähnlich wie ein Iterator. Das war ja auch einer meiner Kritikpunkte.

Guck dir mal die Returnwerte der ++/-- Operatoren an und was der [] Operator macht...

Ja - ich bin absolut Deiner Meinung. Habe mich bloss falsch ausgedrückt.
So eine Klasse wie Prime ist vom Konzept her ein Iterator und sollte sich natürlich auch so verhalten, dass heißt z.B. im operator++ ein return *this; und kein Value.

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.

Gruß
Werner

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