Problem mit großen Zahlen/Datenmengen

dataworm

Hallo,

ich bin noch eher unerfahren mit C++ und wollte daher an einem kleinen Projekt arbeiten. Dabei wird auch mit großen Zahlen und Datenmengen gearbeitet.
Zur besseren Übersicht habe ich den Code ein wenig reduziert.

In der Test.cpp lässt sich die Konstante INPUT definieren. Bei einem Wert von 10 oder 11 funktioniert der Code noch einwandfrei.
Geht man jedoch weiter nach oben (wodurch mit deutlich größeren Zahlen gerechnet wird und auch die Datenmenge auf ein Vielfaches ansteigt), so kommt es zu Problemen.
Das Programm bleibt dann entweder stecken (kommt einfach nicht zum Ende und CPU und Ram-Auslastung im Task-Manager bleibt auch unverändert) oder wird mit der Windows-Meldung abgebrochen, dass nach einer Lösung gesucht wird...
Welcher Fall eintritt hängt dann teilweise vom verwendeten Compiler ab (habe schon netbeans mit cygwin und visual studio ausprobiert).
Bei Visual Studio habe ich es auch schon als 64 bit Version versucht. Auf diese Weise konnte ich INPUT wenigstens noch eins höher setzen, bevor die Probleme wieder auftreten.

Weiß vielleicht jemand wo genau die Problematik liegt bzw. wie man sie lösen kann?

Test.cpp

#include "stdafx.h"

#include <cstdlib>
#include <iostream>

using namespace std;

#include "Permutations.h"

#define INPUT 11

int _tmain(int argc, _TCHAR* argv[])
{

	cout << "Daten initalisieren...";
	Permutations perm(INPUT);
	cout << "Done!" << endl;

    return 0;
}

Permutations.cpp

#include "stdafx.h"

#include <cstdlib>
#include <iostream>

#include "Permutations.h"

#define MAX_PERM_RANG 16

using namespace std;

Permutations::Permutations(unsigned int n) {
    rang = n;
    if (rang > MAX_PERM_RANG) rang = MAX_PERM_RANG;
	unsigned long size = fak(n);
	permstructs = (permStructure_t*) malloc(size*sizeof(permStructure_t));
	createPermStructures(n);
}

unsigned long Permutations::fak(int n) {
    if (n == 0) return 1;
    return n * fak(n - 1);
}

void Permutations::createPermStructures(int n) {
    if (n < 2) return;
    if (n == 2) {
        Permutations::permstructs[0].basePermStructureID = 0;
        Permutations::permstructs[0].insertionPosition = 0;
        Permutations::permstructs[1].basePermStructureID = 0;
        Permutations::permstructs[1].insertionPosition = 1;
        return;
    }
    createPermStructures(n - 1);
    double k = fak(n - 2);
    double limit = k * (n - 1);
    unsigned int m = limit;
    for (unsigned long i = 1; i < (n - 1); i++) {
        for (unsigned long j = 0; j < limit; j++) {
            Permutations::permstructs[m].basePermStructureID = Permutations::permstructs[j].basePermStructureID + i*k;
            Permutations::permstructs[m].insertionPosition = Permutations::permstructs[j].insertionPosition;
            m++;
        }
    }
    for (double i = 0; i < limit; i++) {
        Permutations::permstructs[m].basePermStructureID = i;
        Permutations::permstructs[m].insertionPosition = n - 1;
        m++;
    }
}

Permutations.h

#ifndef PERMUTATIONS_H
#define	PERMUTATIONS_H

#include <String>

using namespace std;

typedef struct struct_permStructure {
    unsigned long basePermStructureID;
    char insertionPosition;
} permStructure_t;

class Permutations {

public:
    Permutations(unsigned int numberOfElements);

private:
    int rang;
    permStructure_t* permstructs;

    unsigned long fak(int n);
    void createPermStructures(int n);
};

#endif	/* PERMUTATIONS_H */

Danke vorab!
DataWorm

vario-500

also, das funktioniert bei mir bis zur 34 als eingabe (visual studio 2010, 32 bit):

#include <iostream>

unsigned long fak(unsigned long n) {
    if (n == 0) return 1;
    return n * fak(n - 1);
}

int main()
{
	unsigned long eingabe;
	std::cin >> eingabe;
	unsigned long f = fak(eingabe);
	std::cout << f << std::endl;
	system("pause");
}

d.h. kann es nicht am input liegen. es wäre natürlich gut zu wissen, wann sich das programm genau aufhängt, bzw. du lieferst uns ein compilierbares minimalbeispiel. außerdem benutzt du c funktionen zur speicherverwaltung. das brauchst du in c++ überhaupt nicht, da gibt es new / delete bzw new[] / delete[] (bei dir wird auch kein speicher frei gegeben). aber das brauchst du in c++ auch nicht so heufig und letzteres eigentlich gar nicht. benutzte sdt::vector oder std::array, je nachdem ob die größe fest ist oder nicht.

dataworm

Okay danke, das werde ich versuchen bei Gelegenheit anzupassen! Musste in letzter Zeit eher etwas mit C arbeiten und bin OOP mehr in Sprachen wie Java oder PHP gewöhnt. Muss ich eindeutig noch etwas in C++ eingewöhnen!

Also ich habe ebenfalls Visual Studio 2010, doch ab Input 12 stürzt er bei mir ab mit der Windows-Meldung "Test.exe funktioniert nicht mehr".
Woran könnte das sonst noch liegen?

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!