Rekursion aufteilen

Hi,

ich habe ein recht pikantes Problem, bei dem ich nicht so recht weiterkommen vermag.

Ich habe eine Funktion, die sich rekursiv aufruf, um alle Kombinationsmöglichkeiten durchzugehen.

Hier einmal der Code:

const unsigned char character_table [] =
{
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 

    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 
    'u', 'v', 'w', 'x', 'y', 'z', 

    ' ', '#', 
};
const unsigned long character_table_size = sizeof (character_table) / sizeof (character_table[0]);

void combi (char* value, unsigned long position = 0) 
{ 
    if (position == ::strlen (value))
    {
        printf ("%s\n", value);
        return;
    }

    for (unsigned long i = 0; i < character_table_size; ++i) 
    { 
        value [position] = character_table [i]; 

        combi (value, position + 1); 
    } 
} 

int main ()
{
    char value[] = "...."; // kann auch länger oder kürzer sein!

    combination (value);

    return 0;
}

Das läuft wunderbar, jedoch ist es mir etwas zu lam.

Folgendes: Ich habe 4 Prozessoren und wenn ich das Programm laufen lasse, läuft es nur auf einem Prozessor - die anderen dümpeln nur vor sich hin. Also dachte ich: Nimm Threads, um das Programm effektiv aufzuteilen, damit es schneller geht.

ABER: Dafür müsste ich der Funktion angeben, von wo bis wo sie laufen soll.

Beispiel:
Thread 1:
000000 bis 4x4x4x

Thread 2:
4x4x4x bis ######

Doch dies ist mit dieser Funktion dort oben, da Rekursion benutzt wird, nicht möglich und einen anderen Ansatz für so etwas kenne ich nicht.

Ich hoffe mir kann jemand bei dem Problem helfen.

Liebe Grüße
Euer Rekursiver.

*D*Evil

Hmm alle Kombinationsmöglichkeiten? Naja dann versteh ich nicht ganz was du da machst. Du kannst nur alle Kombinationsmöglichkeiten bereitstellen, wenn du mit 2 dimensionalen char-arrays oder einfach mit string-arrays arbeitest

Es sind 68 Belegungsmöglichkeiten. Dann darf man keines zurücklegen. Das ist doch Stochastik!

Ohne das jetzt genau anzuschauen, würde ich mal denken, dass du doch einfach die rekursive funktion in einem Thread mit "...." und in einem anderen mit "gggg" aufrufen kannst. Musst nur die abbruchbedingung noch änderen, damit die erste nur bis "gggf" zählt.

@ (D)Evil
68 Möglichkeiten?! Ich habe 39^4, ein bissel krasser unterschied. 39^n öglichkeiten bereitstellen ist nonsens.

Tipp: Programm mal starten.

@fdsfsd
das ist nicht möglich.

*D*Evil

? Für die erste Stelle gibt es 68 Möglichkeiten, für die 2. 67 usw. ...
Also character_table_size sollte 68 sein

Dann musst du halt deinen Algorithmus so umschreiben, dass es geht

Th

Der Flaschenhals bei deinem Programm sind eher die beiden Funktionen "strlen" und "printf".
Denn bei einer Konstanten und keiner Ausgabe würde das Programm bei 4 Zeichen gerade mal bis 38^4 = 2Mio zählen, also unter 1 Sekunde laufen...
Und Threads würden das Programm eher verkomplizieren und die Ausgabe wäre durcheinander (anstatt sequentiell).

@Th
printf ist nur testweise und tut nicht weh, selbst wenn ich es nur alle 10000 durchläufe ausgebe ist das ein witz. um strlen zu ersetzen kenne ich leider keine bessere lösung.

klar bei 4 zeichen ist das ein witz, jedoch da es N sein sollen kann es bei 7 zeichen schon EXTREM lange dauern, nämlich mehrere stunden auf nem 1,6 Quad Core. Die Zeit wächst exponenziell an. Wie ich schon sagte: N Zeichen, nicht immer 4!

Dazu geht es mir nicht um die Ausgabe, da die nur Testweise ist. Ob das Programm nun verkompliziert wird ist mir relativ egal. Wenn ich über 10 stunden brauche um eine länge von 20 Zeichen durchzuhasseln auf einem Prozessor (wo 4 sind), ist das nicht mehr akzeptabel. 3,3 Stunden schon eher. Daher bitte keine Debatte um so etwas.

@fdsfsd
da ich geschrieben habe, das mir keine bessere lösung einfällt, ist dein posting das letzte.

@(D)Evil
Ich kann dir leider noch nicht folgen... Hast du das Programm überhaupt gestartet?

Nochmals danke für jede Hilfe.

vor ner weile gabs schon mal das gleiche problem und lösungen dazu die an beliebiger stelle gestartet werden können

fdsfsd schrieb:

vor ner weile gabs schon mal das gleiche problem und lösungen dazu die an beliebiger stelle gestartet werden können

wärest du so nett und könntest link geben? mit der suchfunktion mit den stichworten "rekursion" finde ich kein topic dazu.

Th

Ist denn die Reihenfolge der Abarbeitung egal?
Ich tippe darauf, daß du einen Serien-Nummer-Cracker schreiben willst -)

Dann unterteil deine rekursive Funktion in zwei, die erste durchläuft einfach jeweils das erste Zeichen für genau 1/4 des Bereichs (38/4), und die untergeordnete für alle weiteren Positionen alle Zeichen (so wie bisher).

Und dann startest du 4 Threads mit jeweils dem passenden Bereich (je nach Betriebssystem mußt du dann entsprechende Funktionen aufrufen: POSIX bzw. WinAPI oder andere plattformübergreifenden Implementierungen, z.B. boost:threads).

Und statt strlen() kannst du doch einfach diesen Wert in eine (globale) Variable packen und dann abfragen, denn innerhalb der Rekursion ändert sich dieser Wert ja nicht!!!

Wie hoch kann denn N bei dir werden? Schon für 8 hast du 10^12 verschiedenen Kombis (d.h. selbst bei 10Mio pro Sekunde bräuchtest du ca. 5 Tage!!!)

Rekursiver schrieb:

fdsfsd schrieb:

vor ner weile gabs schon mal das gleiche problem und lösungen dazu die an beliebiger stelle gestartet werden können

wärest du so nett und könntest link geben? mit der suchfunktion mit den stichworten "rekursion" finde ich kein topic dazu.

Weil Rekursion dafür wohl das falsche Wort ist. Such mal nach "Kombinationen" oder sowas. Und nicht nur die Überschriften lesen, die sind meistens Müll.

@fdsfsd
Da finde ich leider nur Topics mit Permutation, doch das ist leider nicht das was ich benötige - oder doch?

Badestrand

Doch, Permutation müsste richtig sein.

Noch eine kleine Idee meinerseits: Die Idee von Th ist gut, die Rekursion zu 'teilen'. Evtl kannst du dir aber auch überlegen, die Berechnungen als 'Jobs' zu erstellen, also dass du eine Liste von Jobs hast. Dann startest du X Threads, wobei entweder jedem Thread sofort je Y Jobs zugewiesen werden, oder aber sich die Threads nach jedem fertigen Job einen neuen holen. Mit den Jobs kannst du die Berechnung leichter auf mehrere Rechner verteilen, du musst nur noch Kommunikation einbauen und eben Jobs zuweisen.

Ich bin mir aber grad unsicher, ob sich Permutationen wirklich sinnvoll aufteilen lassen, da du ja auch Vorberechnungen benutzt/benutzen kannst. Hab aber grad keine Lust nachzudenken, wollt jetzt vor den Fernseher

oh, wurde dieser Link schon gepostet?

@Badestrand
Aber eine Permutation ist doch nur die Kombination aus gegebenen buchstaben in der länge ihrer anzahl. ich benötige doch die kombination aus gegebenen buchstaben in der länge, welche nicht mit der anzahl buchstaben in beziehung steht? jedenfalls weiß ich nicht was mir das bringt.

Badestrand

Rekursiver schrieb:

@Badestrand
Aber eine Permutation ist doch nur die Kombination aus gegebenen buchstaben in der länge ihrer anzahl. ich benötige doch die kombination aus gegebenen buchstaben in der länge, welche nicht mit der anzahl buchstaben in beziehung steht? jedenfalls weiß ich nicht was mir das bringt.

Liegt wahrscheinlich an mir, aber ich krieg den Sinn des Satzes grad nicht
Hab dein Programm mal bei mir durchlaufen lassen, für character_table = { 'a', 'b', 'c'}; ergäbe sich doch

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
...
ccc

oder nicht?

Badestrand schrieb:

Rekursiver schrieb:

@Badestrand
Aber eine Permutation ist doch nur die Kombination aus gegebenen buchstaben in der länge ihrer anzahl. ich benötige doch die kombination aus gegebenen buchstaben in der länge, welche nicht mit der anzahl buchstaben in beziehung steht? jedenfalls weiß ich nicht was mir das bringt.

Liegt wahrscheinlich an mir, aber ich krieg den Sinn des Satzes grad nicht
Hab dein Programm mal bei mir durchlaufen lassen, für character_table = { 'a', 'b', 'c'}; ergäbe sich doch
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
...
ccc
oder nicht?

Ja, aber ich habe mehr zeichen in der character_table als der string lang ist - daher bringt mir permutation nichts, jedenfalls würde mir nicht einfallen wie.

die tun das was du willst
http://www.c-plusplus.net/forum/viewtopic-var-t-is-199754-and-highlight-is-*kombinationen*.html