array von long long in file speichern

Hallo!

Ich hab folgendes Problem:
Ich ein Programm, das mir die erste Milliarde Primzahlen berechnet, abgespeichert in einem unsigned long long array. Wenn ich das in eine Textdatei abspeichere, sind das schon mal 55 MB. Jetzt will ich aber das Programm auf eine Billion Primzahlen erweitern, und da wirds dann sicher Probleme geben. Deswegen ists sicher besser, die Zahlen dann als Bits zu speichern und nicht als Text. Kann mir jemand schreiben, wie man das macht?
Dann noch eine Frage:
Ich nehm mal an, dass dieses File dann trotzdem ziemlich groß wird, deswegen weiss ich nicht genau, wie ichs handhaben soll, wenn ich die Daten wieder einlesen will. Wenn ich ein File mit dem Filestream öffne, wird dann die ganze Datei in den Hauptspeicher gelesen? Ich hab nämlich schon so enorme Rechenzeiten. Gibts da irgend eine gute Lösung um mit so großen Files umzugehen?

Danke für jede Hilfe!
Christian

Jester

Um die Zahlen kompakter zu speichern und wieder zu lesen müßte es eigentlich genügen, den stream binär zu öffnen.

MfG Jester

std::ofstream Datei; 
Datei.open("Primzahlen.txt",std::ios::out | std::ios::binary); 

if (!Datei)
{
   std::cerr << "Fehler!";
   return 0;
}

Datei.write(array_[i], strlen(array_[i]));
Datei.close();

Maschi

Du kannst es notfalls in mehrere Dateien aufteilen, aber ich denke, dass bei den meisten Implementierungen nicht sofort die ganze Datei in den Buffer gelesen wird.

volkard

chrisslate schrieb:

Ich ein Programm, das mir die erste Milliarde Primzahlen berechnet, abgespeichert in einem unsigned long long array. Wenn ich das in eine Textdatei abspeichere, sind das schon mal 55 MB. Jetzt will ich aber das Programm auf eine Billion Primzahlen erweitern, und da wirds dann sicher Probleme geben. Deswegen ists sicher besser, die Zahlen dann als Bits zu speichern und nicht als Text.

einspruch, euer ehren!

und das nächste mal rechne selber nach.

berechnen wir doch mal, was es kostet, alle primzahlen bis 2^n abzuspeichern.
a) wie speichern sie als binärzahlen. wievieleprimzahlen bis 2^n gibt es überhaupt? nehmen wir doch einfach die übliche abschätzung, von 1 bis x gibt es x/ln(x) primzahlen. dann brauche ich für die primzahlen bis 2^n ungefähr 2^n/ln(2n)*n bit.
wäre ich jetzt gut in rechnen, könnte ich das sogar vereinfachen. bin aber nur in mathe fit und sehe, daß die verfahren a) und b) in der gleichen gegend bleiben. muß leider jetzt mühsam rechnen, sonst glaubst du es mir wohl nicht.

2^n/ln(2^n)*n
=
2^n/(ln(2)*n)*n
=
2^n/ln(2)
=
0,693147180559... * 2^n

b) wir nehmen ein bit pro zahl zwischen 1 und 2^n und markieren da die binärzahlen.
kosten: 2^n bit.

frage: was ist billiger?
antwort: die auflistung als binärzahlen.

wollen wir aber mal die zahlen von 1 bis 1e12 abspeichern, also von 1 bis 2^40 und haben nur 64-bittige ints, dann kostet es uns um den faktor 64/40 mehr als obige rechnung sagt, und schaut her und stellt fest, daß 64/40*ln(2)=1.10 und wir brauchen gerade mal 10% mehr als mit der bitfeld-datstellung.

Kann mir jemand schreiben, wie man das macht?

ja. aber ich würde dir leiber sagen, wie du dein problem löst, statt dir zu sagen, wie du unfug machst.

Ich nehm mal an, dass dieses File dann trotzdem ziemlich groß wird, deswegen weiss ich nicht genau, wie ichs handhaben soll, wenn ich die Daten wieder einlesen will. Wenn ich ein File mit dem Filestream öffne, wird dann die ganze Datei in den Hauptspeicher gelesen? Ich hab nämlich schon so enorme Rechenzeiten. Gibts da irgend eine gute Lösung um mit so großen Files umzugehen?

jetzt werden die fragestellungen besser. wie vermeidest du enorme rechenzeiten?
ich frage am besten erstmal, wozu du eine so riesige primzahlenliste brauchst. um zufällige zahlen auf primalität zu prüfen oder um immer wieder ne liste aller primzahlen durchzugehen (und zum beispiel nen primzahlentester zu rüfen).

ich gehe mal von letzterem aus. dann mach es so:
nimm einen einigermaßen guten vortest, der dir meistens korrekt verrät, ob eine zahl prim ist. also sagen wir mal faktortest auf primteiler zwischen 2 und 31 und dann SPRP mit zwei hübschen basen.
und dann speicher nur die zahlen, die von dem vortest falsch bewertet wurden! das könnten dann schon um den faktor 1e6 weniger sein.
oder einen schnelleren test, sagen wir mal auf dir faktoren 2, 3 und 5 mit einer division (durch 30) und einem PRP-test auf basis 2.

und wo steckt überhaupt die viele rechenzeit in deinem prog? bis 1e9 liefert mein eratosthenes-sieb die zahlen in 90 sekunden. ist zwar viel lahmer, als eine 1GB-datei zu lesen, aber sooo viel lahmer auch wieder nicht und die platte bleibt kalt dabei.

Hallo!

Danke für die anregenden Gedanken. Du hast Recht, was den Speicher betrifft. Hab mir das alles mal durch denk Kopf gehen lassen und werd das Programm jetzt ganz anders aufbaun.

Lg
Christian