Die größe eines Feldes zuerst berechnen, aber wie bekommt man das const?

Nimda

Also geht es nicht. Mist. Dann also dynamisch mal eben bis zu 800 MB...
Danke.

Windalf

lol wie hast du dir den vorgestellt 800 MB auf den Stack zu packen...
das wäre doch eh nicht gegangen

kannst ja mal

int main(){char x[100000000];}

ausprobieren...
wenns noch geht häng noch ne 0 dran ich bin sicher dein stack wirds dir übel nehmen

Nimda

Das geht schon! Mann muss nur die Auslagerungsdatei RICHTIG groß stellen, dann ein bischen Beten und dann klappt das.
Ich brauch die 800 MB, oder ich lese ein paar *nachrechnen* 65 Millionen mal auf eine Datei zu. Da ist der Stack doch schneller oder? Wenn er mich wie gesagt nicht vorher tötet.

SideWinder

Darf ich mal fragen warum du 800MB auf einmal benötigst. Das zwingt sogar aktuelle PC-Systeme in die Knie, egal ob Stack oder Heap.

MfG SideWinder

Walli

Nimda schrieb:

Ich brauch die 800 MB, oder ich lese ein paar *nachrechnen* 65 Millionen mal auf eine Datei zu. Da ist der Stack doch schneller oder? Wenn er mich wie gesagt nicht vorher tötet.

Wie wäre es wenn du in Blöcken von sagen wir mal 512kB verarbeitest? Das sollte um einiges performanter als 800MB in den virtuellen Speicher bzw. zig Millionen Zugriffe sein.

Nimda

Primzahlen.

Ich will Primzahlen im Bereich 2^64 suchen. Dazu muss sie durch alle Primzahlen bis 2^32 teilen, aber das sind immerhin noch 200 Millionen oder 800 MB. Ich kann die 800 MB umgehen, in dem ich die Primzahlen direkt aus der Datei lese und nutze, doch dass dauert entsprechend länger. Mal sehen, wie ich das löse.

edit.: Ich werde die wahrscheinlich auch in Blöcken lesen und benutzen müssen.

SideWinder

Dann bau dir am besten eine speicheroptimierende BigInt-Klasse die sehr große Zahlen möglichst gut im Speicher verteilt. Sobald du nämlich erst einmal Berechnung mit Zahlen durchführen musst die auf der Platte liegen (sei das nun durch direktes Arbeiten in einer Datei oder bei einem OS mit Speichermanager das Überlaufen das RAMs und das folgende Auslagern auf die Platte) brauchst du ewig bis du Ergebnisse hast.

Falls du wirklich mit sämtlichen Optimierungen immer noch 800MB benötigst empfehle ich dir sowieso auf ein größeres System als einen handelsüblichen PC umzusteigen. Der hat im Maximalfall derzeit 1024MB RAM und davon kannst du dir nicht einfach mal so 800MB davon ausborgen.

MfG SideWinder

volkard

Nimda schrieb:

Das geht schon! Mann muss nur die Auslagerungsdatei RICHTIG groß stellen, dann ein bischen Beten und dann klappt das.
Ich brauch die 800 MB, oder ich lese ein paar *nachrechnen* 65 Millionen mal auf eine Datei zu. Da ist der Stack doch schneller oder? Wenn er mich wie gesagt nicht vorher tötet.

der stack ist da nicht schneller als der heap.
der stack ist allgemein schneller, weil man new und delete spart, um den specher zu allokieren. bei 800MB ist aber das allokieren völlig vernachlässigbar im vergleich zum initialisieren.
außerdem gehts auf dem stack eh nicht so groß.

ich hab zufällig ne klasse, die die primzahlen bis 2^32 auf meinem celeron 400 in 90 sekunden auswirft. www.volkard.de/prime.rar

Nimda

DAS muss ich mir ansehen. Ich brauch Stunden auf meinem PC. Und das obwohl ich den Code soweit mir möglich optimiert habe.
Dabei fand ich übrigens raus, dass bei mir i++ anscheinend schneller ist als ++i. Hier in der FAQ stehts aber genau andersrum. Naja. Jetzt schau ich mir erst mal die Primzahlklasse an, die so schnell ist.

edit.: Ich kann sie nicht runterladen. Er sagt mir, dass die Adresse nicht mehr Existiert. Kannst du sie dann bitte Posten? Oder anderswie zugänglich machen. Ich will wissen, wie man SO schnell Primzahlen berechnet.

volkard

Nimda schrieb:

DAS muss ich mir ansehen. Ich brauch Stunden auf meinem PC. Und das obwohl ich den Code soweit mir möglich optimiert habe.

naja, ich hab an der funktion isPrime() während meines studiums mehr als ein halbes jahr lang geschraubt.

Dabei fand ich übrigens raus, dass bei mir i++ anscheinend schneller ist als ++i. Hier in der FAQ stehts aber genau andersrum.

eigentlich sollten die beiden gleich schnell sein.
bei selbstgebauten typen gewinnt a=++i meist, weil bei a=i++ noch ne kopie des alten wertes angelegt werden muss. mit konstruktoraufruf und dem ganen krm vielleicht noch.
bei ints gewann früher a=++i meist, weil der resultierende code oft einen befehl weniger hatte.
heute gewinnt a=i++ oft, weil der effekt von ++ später irgendwann von irgendeiner vielleicht mal frei werdenden alu berechnet werden kann, ach, keinen juckt's. aber bei a=++i muss due zuweisung warten, bis der effekt von ++ gewirkt hat. ok, nur einen takt, aber das nervt ja auch.

edit.: Ich kann sie nicht runterladen. Er sagt mir, dass die Adresse nicht mehr Existiert. Kannst du sie dann bitte Posten? Oder anderswie zugänglich machen. Ich will wissen, wie man SO schnell Primzahlen berechnet.

ups. jo. gerade bemerke ich, daß ich ja heute meine homepage reseted habe und neu anfange. ich schieb die prime.rar sofort drauf.

edit: uih, das ist irgendwie ne alte version. naja, so sah mein stil vor zwei jahren aus.

Deadlef

@Nimda:
Es gibt den für diese Aufgabe gern und häufig verwendeten Algorithmus "Sieb des Erathosthenes", ein sehr schneller algorithmus, der allerdings für jede Zahl bis zur gewünschten maximalen Zahl jeweils eine Speicherstelle benötigt. Er funktioniert so:
zunächst wird angenommen, jede Zahl sei eine Primzahl.
Von dort ausgehend wird, beginnend mit der 2 (also der ersten wirklichen Primzahl) jedes Vielfache einer als Primzahl bekannten Zahl als nicht-Primzahl gekennzeichnet. Also für die ersten Schritte sieht das so aus:

2:
4 6 8 10 12 14 16 18 20 22 24 26 28 30 -> jetzt bekannt als Nicht-Primzahlen
3:
6 9 12 15 18 21 24 27 30 -> s.o.

Jetzt wären also noch Primzahlen:
5 7 11 13 17 19 23 25 29
                    !

Die einzige noch nicht als Primzahl erkannte Zahl unter 30 ist damit die 25. Ein verdammt schnelles Verfahren also. Leider auch hier das Problem, dass der benötigte Speicher selbst mit Bitfeldern auf Terabytemaße anwächst, wenn man bis 2⁶⁴ gehen will.

volkard

Deadlef schrieb:

Ein verdammt schnelles Verfahren also. Leider auch hier das Problem, dass der benötigte Speicher selbst mit Bitfeldern auf Terabytemaße anwächst, wenn man bis 2⁶⁴ gehen will.

jo. sauschnell ist es. auf dem 64-er in basic v2 braucht es pro primzahl ca 1/60 sekunde, und das unabhängig davon, wie viele zahlen man berechnet.
man schafft größere bereiche, indem man abschnittsweise vorgeht. zuerst von 0 bis 9999 (zahlen von 0 bis 99 zum ausstreuchen benutzen), dann von 10000 bis 19999 (zahlen von 0 bis 141 zum ausstreichen benutzen), dann... dann von x bis y (zahlen von 0 bis sqrt(y) zum ausstreichen benutzen). könnte schneller sein, als ramzugriffe (oder gar schreckliche plattenzugriffe) zu machen. deswegen hab ich das feld nur 64k gross gemacht (damits besser im prozessorcache liegt) und die streichzahlen lass ich von nem mini-sieb bauen (das allerdings fehlerhafterweise zur zeit von ner sieblisen isPrime() gefüttert wird, statt von sich selbst).