Problem mit großen Zahlen/Datenmengen

[vario-500]

hast du es mit meinem beispiel probiert? und wenn nicht, mach es und schau mit dem debugger nach, an welcher stelle genau das passiert.

[dataworm]

Ups, mir ist eben erst das veränderte Beispiel aufgefallen!
Ja das funktioniert natürlich soweit erstmal problemlos, aber die Fakultät war ja auch nicht mein Problem.

In meinem Programm wird ja nicht nur eine Fakultät berechnet. Da wird ja noch einiges mehr gemacht und das im Extremfall sogar mit Zahlen bis zu pow(fak(INPUT),INPUT), was natürlich auch gleich nochmal ganz andere Dimensionen annimmt. Vielleicht kommt es damit auch zu ähnlichen Problemen wie die Fakultät mit 35.

[SeppJ]

Etwas typisches was hier passieren kann ist, dass die Fakultät überläuft und du dann ein negatives Argument für malloc bekommst. Ansonsten hör einfach mal auf zu spekulieren und schnapp dir einen Debugger. Das bringt nichts, rumzuraten, wo der Fehler sein könnte. Da du einige gefährliche Programmiermuster in deinem Programm hast (new statt malloc wurde dir z.B. eine aussagekräftigere Exception schmeißen, anstatt abzustürzen), kann der Fehler überall sein.

Was soll das Programm überhaupt tun? Derzeit verbrät es nur planlos viele Ressourcen. Und du kennst die Algorithmen der Standardbibliothek zum Umgang mit Permutationsfolgen, oder?

[dataworm]

Okay dann werde ich das Programm erst einmal entsprechend umschreiben.

Nein diese Algorithmen sind mir nicht bekannt, ich hatte mir nach einer schlaflosen Nacht selbst einen Algorithmus überlegt und nicht näher nachgeforscht.
Ist für mich so eine Art Denksport-Übung, bei der ich eben nicht nur etwas C++ lerne sondern gleich auch etwas Algorithmik, auf Effizienz zu achten, zu optimieren... Und später soll das ganze auch auf Cuda oder einen Cluster ausgeweitet werden...

Edit:
Also mit new und Debugging bekomme ich nun wirklich neue Informationen, offenbar kann kein Speicher allokiert werden. Warum ist mir aber noch nicht ganz klar!

Unbehandelte Ausnahme bei 0x7630b9bc in Test.exe: Microsoft C++-Ausnahme: std::bad_alloc an Speicherposition 0x004dfd00..

[Caligulaminus]

12! ist 479.001.600.

Deine permStructure_t dürfte mindestens acht byte groß sein.

Was passiert wohl bei malloc(size*sizeof(permStructure_t)) ?

[dataworm]

Na es würde wohl meinen Ram sprengen! Aber müsste das Betriebssystem in diesem Fall nicht automatisch die nächste Hierarchie hinzuziehen und einige Daten des Arbeitsspeichers auf die Festplatte auslagern?

[Caligulaminus]

Auf jeden Fall wird's spätestens jetzt zäh.
Ich weiß nicht, ob dein Windows mit sowas umgehen kann. Bei 32Bit-Windows bist Du hier eh schon an der theoretischen Grenze.
Und bei 13! kratzen wir schon an der 50-Gig-Marke.
Ich denke, der Ansatz ist für einen Desktop-PC einfach nicht ganz der richtige.

[dataworm]

Das stimmt wohl. Wollte eh bis maximal 16 gehen, aber da muss ich wohl auch noch einige Jahre auf den entsprechenden Fortschritt warten!
Ich werde den Code wohl entsprechend umbauen, so dass die entsprechende einzelne Permutation immer erst auf Anfrage generiert wird (oder bestenfalls Permutation bis 9 Elemente gespeichert werden).

Hab auch grad mal schnell geschaut, was die Laufzeitumgebung von C++ zu Permutationen anbietet. Wenn ich das richtig sehe, dann sind die meisten Algorithmen auch nur dazu befähigt sich von einer Permutation zur nächsten zu hangeln. Wenn man aber beispielsweise mal direkt die 1000. Permutation ohne Wiederholung (nach lexikographischer Sortierung) wissen will, dann versagen diese offenbar. Bzw. man müsste sich vom Anfang aus 999 mal vorwärts hangeln, was natürlich keineswegs effizient ist.

Kennt jemand noch andere Algorithmen, die etwas direkter eine solch konkrete Permutation bestimmen können?

[Caligulaminus]

Kennt jemand noch andere Algorithmen...

Such' mal. Die Mathematik ist hier wohl der einzige Retter. Würde mich nicht wundern, wenn die Suche zu diesem Thema schnell spannende Lektüre für mehrere Abende zutage fördern sollte.

[dataworm]

Habe ich bereits ein wenig, aber ich habe bisher höchstens einen Algorithmus gesehen, der diese direkte Bestimmung möglicherweise beherrschen könnte (wenn man den Algorithmus entsprechend anpasst).
Ist für mich momentan ein Grund mehr bei meinem Algorithmus zu bleiben. Denn da ich wie man sieht ja leider nicht beliebig lange Permutations-Listen generieren lassen kann, muss ich wohl leider jeweils die gewünschte Permutation einzeln erstellen lassen.

Aber ich denke ich kann vielleicht eine Misch-Variante sehr gut verwenden!