Iterative oder Rekursive? Geschwindigkeit

lottofee2010

Hallo zusammen,

eigentlich schreibe ich Programme in Java, aber mein Lehrer verlangt jetzt das ich ein C Programm schreibe, welches dann auf einem openVMS System laufen soll.
Das Programm soll die Lottozahlen-Kombinationen mit Superzahl ermitteln, und dann eine bestimmte Kombination erfassen.
Ich habe das ganze mir erst einmal in Java geschrieben und dann Stück für Stück in C übersetzt, leider ist das ganze nicht so performant wie erwünscht.

Ich habe das einmal Iterative (Methode "doititeratvie") und Rekursive(Rekursive"doitit") gemacht:

Kennt jemand eine Möglichkeit das ganze zu beschleunigen?
Zurzeit brauche ich:
Iterative: 17 Sekunden.
Rekursive: 18 Sekunden.

Ich würde gerne unter eine Sekunde kommen für die letzte Kombination, weil ich das auch in Java(mit Windows XP) geschafft habe.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/************************
 * Variablen Deklaration *
 *************************/

int stop = 0; // boolean
int *zahlen[6];
int *zahlenMitSZ[7];
int *searchedCombi[]={44,45,46,47,48,49,9};
int aus = 49;
int anzZahlen = 6;
int zeile = 1;

/************************
 * Methoden             *
 *************************/

void printConsole(){
  char mitSZ[20];
  char buffer[20];
  strcpy(mitSZ,"");
  int j = 0;
  for (j=0; j< 6; j++){
    strcpy(buffer, "");
    sprintf(buffer, " %d", zahlen[j]);
    strcat(mitSZ,buffer);
  }
  strcat(mitSZ,"\0");
  for(int i = 0;i<10;i++){
    printf("%s %i\n",mitSZ,i);
    zeile++;
  }
}

void searchCombination(){
  memcpy(zahlenMitSZ,zahlen,sizeof(zahlen));
  for(int i=0;i<10;i++){
    zahlenMitSZ[6] = i;
    if(memcmp(zahlenMitSZ,searchedCombi,sizeof(zahlenMitSZ))==0){
       printf("Kombinationin in Zeile: %d (%i) gefunden!\n",zeile,zeile);
       stop = 1;
    }else{
       zeile++;
    }
  }
}

/************************
 * Rekursive            *
 *************************/
void doit(int fehlen, int start){
  if(zeile >= 10){
   // stop =1;
  }
  if (stop == 0) {
    if (fehlen > 0) {
      for (int i = start; i <= aus; i++) {
        int len=sizeof(zahlen)/sizeof(int);
        zahlen[len - fehlen] = i;
        doit(fehlen - 1, i + 1);
      }
    } else {
      //printConsole();
      searchCombination();
    }
  }
}

/************************
 * Iterative             *
 *************************/

void doititeratvie(){

 int i,j,k,l,m,n=0;
 for (i = 1; i <= 49; i++) {
  for (j = i + 1; j <= 49; j++) {
   for (k = j + 1; k <= 49; k++) {
    for (l = k + 1; l <= 49; l++) {
     for (m = l + 1; m <= 49; m++) {
      for (n = m + 1;n <= 49; n++) {
       if (i != j && i != k && i != l && i != m && i != n && j != k && j != l && j != m &&
           j != n && k != l && k != m && k != n && l != m && l != n && m != n){
              zahlen[0] = i;
              zahlen[1] = j;
              zahlen[2] = k;
              zahlen[3] = l;
              zahlen[4] = m;
              zahlen[5] = n;
              searchCombination();
}}}}}}}

}

int main(int argc, char *argv[])
{
  printf("Programm Kombinationen start.\n");
  clock_t prgstart, prgende; //Definierung der Variablen
  prgstart=clock();          //CPU-Zeit zu Beginn des Programmes
  //doit(anzZahlen,1);
  doititeratvie();
  if(stop ==0){
    printf("keine Kombination gefunden!\n");
  }
  prgende=clock();          //CPU-Zeit am Ende des Programmes
  printf("Laufzeit %.2f Sekunden\n",(float)(prgende-prgstart) / CLOCKS_PER_SEC);
  printf("Programm Kombination ende.\n");
  return EXIT_SUCCESS;
}

Vielen Dank im voraus

mfg lottofee

SeppJ

Also das Programm ist ja schon einmal voller Fehler und sollte eigentlich gar nicht funktionieren oder wenn dann nur mit Glück.

Was soll es denn genau tun? Als allgemeinen Leitfaden darfst du davon ausgehen, dass iterative Algorithmen viel schneller sind als rekursive.

cooky451

Kannst du mal beschreiben was dein Programm eigentlich machen soll? Denn der Code ist offen gesagt.. ich sag es lieber mal nicht offen. Aber auch in Java sind globale Variablen nicht so der Hit, oder? Woher hast du diesen Stil?

camper

lottofee2010 schrieb:

if (i != j && i != k && i != l && i != m && i != n && j != k && j != l && j != m &&
           j != n && k != l && k != m && k != n && l != m && l != n && m != n){

Diese Abfrage scheint mir überflüssig zu sein. Das Schleifenende könnte man auch je nach Variable etwas einschränken, das dürfte allerdings keinen großen Gewinn bringen.

Edit: Den gesamten Rest des Programmes habe ich mir gar nicht erst angeschaut.

knivil

int *searchedCombi[]={44,45,46,47,48,49,9};

Failed. Nimm erstmal das * weg. Auch bei den anderen Arrays.

Wenn ich das richtig sehe, moechtest du nur ueber (49*48*47*46*45*44*9) (ca. 90 * 10^9) Moeglichkeiten iterieren?

weil ich das auch in Java(Windows XP! nicht openVMS) schaffe.

Hast du maximale Optimierung eingeschaltet?

Wutz

lottofee2010 schrieb:

Ich habe das ganze mir erst mal in Java geschrieben und stück für stück in c übersetzt, leider ist das ganze nicht so performat wie erwünscht.

Tja, das liegt dann aber an dir und nicht an C.

http://ideone.com/XeMkg

Grundlegend wird das Problem darin bestehen, dass es nun mal knapp 126 Millionen Kombinationen gibt. Wenn die alle durchlaufen werden sollen, braucht es halt ein bisschen.

Dass der C-Code auf der VMS-Maschine langsamer läuft als der Java-Code auf der XP-Maschine wird im Zweifel daran liegen, dass (jetzt mal wild geraten) die VMS-Maschine deutlich älter sein wird - eine alte DEC Alpha womöglich? Jedenfalls läuft dein Code bei mir ohne Änderungen in weniger als zwei Sekunden durch, selbst ohne Compileroptimierungen.

Es gibt allerdings ein paar Tricks, wie man da noch mal ein bisschen was runterholen kann, und in C sind wir ja auch nicht ganz so zimperlich, was Speicher angeht, nicht wahr?

Also: Zunächst mal sollten wir die Menge des zu vergleichenden Speichers reduzieren. Statt

int zahlen[7];

besser

unsigned char zahlen[7];

Das allein zieht in meinen Tests schon mal rund 30% runter. Wo mir aber dabei auffällt, dass zahlen ziemlich klein wird, sieht der memcmp-Aufruf allein schon dadurch teuer aus, dass er ein Funktionsaufruf ist. Was soll ich für solchen Kleinkram hin- und herspringen? Machen wir

unsigned char zahlen[8]; /* Andere Arrays entsprechend */

daraus, sorgen dafür, dass im hintersten Byte immer ein fester Wert (im Zweifel 0) steht, und schreiben als Vergleich statt

if(0 == memcmp(zahlen, combo, sizeof(zahlen))) ...

schlicht

if(*(uint64_t*)zahlen == *(uint64_t*) combo) ...

Damit krieg ich das ganze auf etwa ein Viertel der ursprünglichen Laufzeit runter. Caveat: uint64_t ist erst in C99 vorhanden; bei alten Compilern oder MSVC musst du dir einen 64-Bit-Integertypen möglicherweise wo anders besorgen. Auf VMS sollte es mich nicht wundern, wenn du in <inttypes.h> fündig würdest, für MSVC gibt es unsigned __int64. #ifdef ist dann dein Freund.

lottofee2010

WoW, erstmal vielen Dank für die vielen Antworten. bin sehr begeistert!

SeppJ schrieb:

Also das Programm ist ja schon einmal voller Fehler und sollte eigentlich gar nicht funktionieren oder wenn dann nur mit Glück.
Was soll es denn genau tun? Als allgemeinen Leitfaden darfst du davon ausgehen, dass iterative Algorithmen viel schneller sind als rekursive.

Das iterative Algorithmen viel schneller sind, habe ich auch hier irgendwo im Forum gelesen, leider habe ich mich damit schwer getan, wie man an den 6 for schleifen erkennen kann.

Irgendwie habe ich das schon erwartet, das es voller Fehler sein wird, aber ich möchte es ja lernen,
also habe ich nicht einfach gefragt, ob es mir jemand macht, sondern versucht, etwas compelierbares zu schreiben.
Die openVMS Maschine Compeliert mit vielen Warnungen, dass alle meine Wertzuweisungen in die Arrays von int zu pointer int umgewandelt werden. Hier zum Beispiel:

int *searchedCombi[]={44,45,46,47,48,49,9};

int *searchedCombi[]={44,45,46,47,48,49,9};
......................^
%CC-W-CVTDIFTYPES, In the initializer for searchedCombi[0], "44" of type "int", is being converted to "pointer to int".
at line number 13 in file $1$DGA101:<LTG.CXX.KOMBINATION>KOMBINATIONEN.C;41

int *searchedCombi[]={44,45,46,47,48,49,9};
.........................^
%CC-W-CVTDIFTYPES, In the initializer for searchedCombi[1], "45" of type "int", is being converted to "pointer to int".
at line number 13 in file $1$DGA101:<LTG.CXX.KOMBINATION>KOMBINATIONEN.C;41

cooky451 schrieb:

Kannst du mal beschreiben was dein Programm eigentlich machen soll? Denn der Code ist offen gesagt.. ich sag es lieber mal nicht offen. Aber auch in Java sind globale Variablen nicht so der Hit, oder? Woher hast du diesen Stil?

Wenn man es genau nimmt bringe ich mir das selber bei weil mein Berufsschullehre einfach gesagt unfähig ist. Der will immer nur sehen und es muss auf anhiebt funktionieren...

Was das Programm später eigentlich machen "sollte":
Ich übergebe eine Lotto Kombinationen Bsp.: Zahlen: 1 2 3 4 5 7 SuperZahl 0
und mein Programm gibt dann die Kombinationsnummer zurück, in dem oben genannten Beispiel wäre das dann 11.
Beispiele:

1 2 3 4 5 6 0 --> 1
1 2 3 4 5 6 1 --> 2
1 2 3 4 5 6 2 --> 3
..
1 2 3 4 5 6 9 --> 9
..
44 45 46 47 48 49 0 --> 139838151
44 45 46 47 48 49 9 --> 139838160

Vielen Dank für dein Tipps seldon, ich werde gleich mal versuchen diese umzusetzen.

seldon schrieb:

Dass der C-Code auf der VMS-Maschine langsamer läuft als der Java-Code auf der XP-Maschine wird im Zweifel daran liegen, dass (jetzt mal wild geraten) die VMS-Maschine deutlich älter sein wird - eine alte DEC Alpha womöglich? Jedenfalls läuft dein Code bei mir ohne Änderungen in weniger als zwei Sekunden durch, selbst ohne Compileroptimierungen.

Ja, da hast du recht, die VMS-Maschine ist um einiges älter, ich habe mal mein Java code leicht abgewandelt ausgeführt und dieser ist deutlich langsamer, liegt bei über 30 Sekunden.

An alle vielen Dank.

Ps.: Es sind genau 139838160 verschiedene Kombinationen ;-D.

mfg die lottofee

lottofee2010

Wutz schrieb:

lottofee2010 schrieb:

Ich habe das ganze mir erst mal in Java geschrieben und stück für stück in c übersetzt, leider ist das ganze nicht so performat wie erwünscht.

Tja, das liegt dann aber an dir und nicht an C.

http://ideone.com/XeMkg

Danke für deinen Code, der funktioniert super, braucht auf der VMS Maschnie 2,5 Sekunden.

Ich will und muss es aber lernen, deshalb hilft mir das jetzt nicht weiter, Erklärungen wo und wie jetzt die Unterschiede bestehen, wären super.

Aber danke, dass du dir die Mühe gemacht hast.

mfg lottofee

EDIT:

Ah leider ist die SuperZahl nicht berücksichtigt worden, bei Berücksichtigung(habe es mal erweitert und compeliert und ausgeführt) dieser, braucht die VMS Maschine leider fast 26 Sekunden.

Wenn mir jetzt jemand den unterschiedlichen Performance Ergebnisse des Sourcecode von wutz(25s) und mir(18s) erklären könnte?

Wobei der von wutz viel einfacher zu lesen ist und keine Warnungen oder Fehler beim compelieren aufweist.

aber trotzdem vielen Dank!

Ah. Ich dachte, es gäbe nur Superzahlen zwischen 1 und 9 -- ich spiel kein Lotto und bin mit den Regeln nicht so firm. Meine Einschätzung, dass es sich nicht lohnt, ändert sich dadurch aber nicht.

Was deine Compilerwarnungen angeht: die solltest du ernst nehmen und ausräumen. Der Compiler warnt dich, dass alle Arrayzuweisungen Zeiger aus Zahlen machen, weil

int *zahlen[6];

ein Array von sechs Zeigern auf int definiert. Du meinst aller Wahrscheinlichkeit nach

int zahlen[6];

...was ein Array von sechs Integern ist.

Ansonsten hat Wutz im Wesentlichen die globalen Variablen entfernt und durch Parameter ersetzt. Das ist im Prinzip gut - globale Variablen haben eine ganze Reihe von Problemen, die dich spätestens, wenn du das erste mal mit Threads hantierst, einholen werden (deswegen wärst du gut beraten, sie dir gar nicht erst anzugewöhnen) - aber bei ihm etwas umständlich umgesetzt. Mit einem Array wäre man m.E. besser dran.

Ich werf dann auch mal mein Stück Code in die Runde:

#include <inttypes.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

/* 8 Einträge scheinen einer zu viel zu sein, aber wir brauchen
 * 8 Byte, um unten zu uint64_t punnen zu können
 */
typedef unsigned char ziehung_t[8];
typedef union {
  ziehung_t ziehung;
  uint64_t  punned;
} ziehung_punner_t;

void search_combo(ziehung_t gesucht) {
  ziehung_punner_t target, buffer;
  unsigned char *p = buffer.ziehung;
  int count = 0;

  memcpy(target.ziehung, gesucht, sizeof(ziehung_t));
  buffer.ziehung[7] = target.ziehung[7]; /* unbenutztes Byte angleichen */

  for(p[0] = 1       ; p[0] <= 49; ++p[0]) {
    for(p[1] = p[0] + 1; p[1] <= 49; ++p[1]) {
      for(p[2] = p[1] + 1; p[2] <= 49; ++p[2]) {
        for(p[3] = p[2] + 1; p[3] <= 49; ++p[3]) {
          for(p[4] = p[3] + 1; p[4] <= 49; ++p[4]) {
            for(p[5] = p[4] + 1; p[5] <= 49; ++p[5]) {
              for(p[6] = 0       ; p[6] <  10; ++p[6]) {
                ++count;
                if(buffer.punned == target.punned) {
                  int i;
                  for(i = 0; i < 7; ++i) {
                    printf("%d ", p[i]);
                  }
                  printf(" -- gefunden in Versuch %d\n", count);
                }                
              }
            }
          }
        }
      }
    }
  }
}

int main() {
  ziehung_t gesucht = { 44, 45, 46, 47, 48, 49, 9 };
  clock_t bench[2];

  bench[0] = clock();
  search_combo(gesucht);
  bench[1] = clock();

  printf("%f Sekunden\n", (double)(bench[1] - bench[2]) / CLOCKS_PER_SEC);

  return 0;
}

Der grundsätzliche Algorithmus ist natürlich unverändert; der große Unterschied ist, dass memcmp nicht benötigt wird. In diesem speziellen Fall, wo so wenig Speicher zu vergleichen ist, kann man einen deutlich schnelleren Ersatz benutzen. Zunächst ist wichtig, mit

typedef unsigned char ziehung_t[8];

die Darstellung einer Ziehung auf (weniger als) 8 Byte zurechtzustutzen - größere Zahlen als 255 werden ja bei einer Lotterie im Allgemeinen nicht gezogen. unsigned char ist immer 1 Byte breit, ziehung_t dementsprechend hier 8 Byte. Für den Vergleich von 8 Byte auf einmal gibt es auf so ziemlich allen Rechnern, die heute noch in Betrieb sind, spezielle Opcodes, und ich vermute, dass das auf deiner DEC auch der Fall sein wird. Wir wollen also das Array von 8 Byte quasi als 8-Byte-Integer interpretieren und mit einem anderen seiner Art auf diese Weise vergleichen.

Das Herzstück dieser Methode ist die Union

typedef union {
  ziehung_t ziehung;
  uint64_t  punned;
} ziehung_punner_t;

. Eine Union ist ein spezieller Datentyp, dessen Member an der selben Stelle im Speicher liegen. Wenn ich in ziehung herumschreibe, ändert sich auch der Wert von punned -- welchen Wert punned dann genau hat, ist mir unbekannt (und auch gleichgültig); ich weiß aber, dass, wenn der Member ziehung zweier ziehung_punner_t den gleichen Wert hat, auch ihre punned-Member gleich sind, weil sie an den gleichen Stellen im Speicher liegen und gleich groß sind (daher auch unsigned char[8]). In gewisser, für unsere Zwecke ausreichender Weise ist punned eine Darstellung von ziehung als 8-Byte-Integer.

Das erlaubt es mir, in der innersten Schleife mit

if(buffer.punned == target.punned)

acht an dieser Stelle liegende Bytes (uint64_t ist 8 Byte breit) auf einmal zu vergleichen, ohne eine Funktion aufzurufen oder eine Schleife zu durchlaufen.

lottofee2010

Morgen seldon,

vielen Dank für deine Hilfestellung, die hat mir auf jeden Fall weiter geholfen, deine Erklärungen waren sehr verständlich, in Java hatte ich noch nie solche Probleme aber ich lerne ja noch und evtl. tritt so was ja mal auf. Mit C werde ich wahrscheinlich in meiner Ausbildung noch einmal zu tun bekommen, jetzt weiß ich wo ich Hilfe finden kann.

Bitte häng mich nicht, aber ist der Fehler in deinem Code gewollt?

clock_t bench[2];

  bench[0] = clock();
  search_combo(gesucht);
  bench[1] = clock();

  printf("%f Sekunden\n", (double)(bench[1] - bench[2]) / CLOCKS_PER_SEC);

Sollte es nicht so lauten:

printf("%f Sekunden\n", (double)(bench[1] - bench[0]) / CLOCKS_PER_SEC);

Dein Code wird eindeutig am schnellsten ausgeführt: mit 3,74 Sekunden. Ich gehe jetzt mal davon aus, dass ich an Geschwindigkeit nicht mehr rausholen kann, oder?

Schön wäre noch zu wissen, warum der Code von Wutz langsamer ist als meiner(der mit den Fehlern)?
Ich vermute mal, dass ihr die Geschwindigkeitsunterschiede nicht so einfach nachvollziehen könnt, auf meiner XP Maschine sind nämlich alle Programme unter einer Sekunde geblieben.
Wutz: ~25 Sekunden
lottofee(ich): ~18 Sekunden
seldon: ~4 Sekunden //die Performance hier kann ich nachvollziehen.

vielen Dank an alle, dir mir geholfen haben

herzliche Grüße die lottofee^^ :p

Ja, da hast du natürlich recht. Dummer Flüchtigkeitsfehler.

Dass Wutzs Code langsam ist, liegt daran, dass er eine Menge Overhead für die Gleichheitsprüfung hat (und die macht ja fast die ganze Laufzeit des Programms aus). Er zählt mit Integern, wirft die für jede Kombination in einen Funktionsaufruf, wo sie in ein Array zusammengesetzt werden, das dann erst zu memcmp kommt. Das bedeutet schlimmstensfalls, dass jedes Mal sechs ints auf den Stack gepusht werden, in die Funktion gesprungen, die ints da zu einem Array zusammengesetzt werden, dann ein Zeiger darauf genommen und an memcmp gegeben wird, was einen weiteren Funktionsaufruf mit allem drum und dran bedeutet. Der Compiler wird davon im Zweifel einiges wegoptimieren können, aber blitzschnell wird das auf die Weise halt nicht.

Zum Thema weitere Optimierungen: Das kommt ein bisschen drauf an. Wenn die Maschine mehrere Prozessoren oder Prozessorkerne hat, was bei einer VMS-Maschine durchaus sein kann, könnte man die Rechenlast auf mehrere Prozessoren verteilen und so etwas herausholen. Wenn das nicht der Fall ist, wird man damit aber im Zweifel eher etwas verlieren. Genaueres kann ich dir nicht sagen, ohne die Maschine zu kennen, auf der das ganze laufen soll.

lottofee2010

seldon schrieb:

Zum Thema weitere Optimierungen: Das kommt ein bisschen drauf an. Wenn die Maschine mehrere Prozessoren oder Prozessorkerne hat, was bei einer VMS-Maschine durchaus sein kann, könnte man die Rechenlast auf mehrere Prozessoren verteilen und so etwas herausholen. Wenn das nicht der Fall ist, wird man damit aber im Zweifel eher etwas verlieren. Genaueres kann ich dir nicht sagen, ohne die Maschine zu kennen, auf der das ganze laufen soll.

Um ehrlich zu sein, kenne ich mich mit dem der VMS nur so weit aus, das ich navigieren, editieren und compelieren kann ^^ aber ein paar Informationen habe ich noch:

Alpha Server 1200 5/400 4MB mit 2 CPU's

Aus der Konsole(PuTTY) bekomme ich folgende Info's:

[7m[1m#6 AlphaServer 1200  /  1 GB        [0m
   [7m[1m#6 OpenVMS V7.3-2                   [0m

Ich hoffe, dass sind die Informationen die nötig sind, um mir zu helfen

Ps.: die Maschine soll schon ca 10 Jahre im Einsatz sein.

Naja, es steht ja dran: mit 2 CPUs. Denkbar also, dass man die Laufzeit etwa halbieren kann, wenn man mit mehreren Threads arbeitet.

Der Wert von "etwa" ist schwer einzuschätzen; ich weiß nicht, wie gut ein zehn Jahre altes VMS im Vergleich zu heutigen Systemen mit der Threadzahl skaliert, und es ist auch nicht ganz trivial, die Last gleichmäßig aufzuteilen - die Schleifen werden ja im hinteren Teil deutlich kürzer. Auch kommen neue Designentscheidungen auf einen zu -- der wievielte Versuch die Kombination gefunden hat, ist, wenn mehrere Versuche gleichzeitig durchgeführt werden, eine Definitionsfrage.

Ich kann mir aber auch nicht vorstellen, dass man Multithreading von euch erwartet. Das Thema ist weitläufig und nicht ohne Tücken (insbesondere, weil hier eine Zählvariable von mehreren Threads gleichzeitig benutzt wird), und den theoretischen Unterbau zu erklären würde den engen Rahmen eines Forumsposts wohl sprengen. Wahrscheinlich ist selbst der Type-Punning-Trick mehr als dein Lehrer sich vorgestellt hat.

Es ist halt stumpf so, dass eine alte Alpha kein neuer Core 2 ist.

Mal was ganz anderes: Ist das ganze wirklich als Übung im Schleifenschachteln gedacht, oder geht es nur darum, die Ordinalzahl der Kombination rauszukriegen? Ich könnte mir vorstellen (ohne die Arbeit jetzt gemacht zu haben), dass man das auf mathematischen Wege direkt herauskriegen könnte.

Ist wohl so wie mit dem "kleinen Gauß" (Summe der ersten n Zahlen)

Rekursiv ist schick.
Itertiv ist einsichtiger.
Gauß ist schnell. Man muss aber vorher nachdenken.

lottofee2010

Mit "Lehrer" ist mein Ausbilder gemeint, ich bin im 2. Lehrjahr meiner Ausbildung zum Fachinformatiker und habe viel Spaß :-P.

Also mein Ausbilder will später eine Kombination eingeben können und daraufhin soll dann die Nummer der Kombination zurückgegeben werden, das ganze so schnell wie möglich und damit ich es schwerer habe, soll ich das ganze in C auf dem openVMS System schreiben. (Habe ich vorher noch nie gemacht, weder C noch kannte ich das System). Da ich mit meinen Java Tests ziemlich zufrieden war, dachte ich, dass ich es in C mindestens genau so umsetzen könnte, was ja leider nicht der Fall war, habe wohl zu voreilig gehandelt.

Also geht es im Grunde nur um die Ausgabe der "Ordinalzahl", wie du so schön gesagt hast.

Wenn ich das richtig verstanden habe, gibt es möglicherweise eine mathematische Gleichung, die mich viel schneller und einfacher ans Ziel bringt?

Tja das bedeutet, ich sollte mich lieber mit Mathe beschäftigen, als mit der Performanceoptimierung...

volkard

lottofee2010 schrieb:

Tja das bedeutet ich sollte mich lieber mit Mathe beschäftigen als mit der Performanceoptimierung...

So halb und halb.
Aber ja, auf jeden Fall das Verfahren selbst verbessern, gegebenenfalls sogar vereinfachen, memcmp oder sowas bringt nix, sondern raubt Dir zunächst nur viele Möglichkeiten.

Also ich überlege mal ohne Zusatzzahl.
Es gibt (49 über 6) Kombinationen.
Also sind alle Doppelzahlen weg und alle unsortieren Kombinationen auch (also ohne Beachtung der Reihenfolge).
Aha. Das macht es doppelt schwierig.

Mich will folgender Gedanke nicht loslassen: Wenn es mit Beachtung der Reihenfolge und mit Mehrfachnennungen wäre, könnte man einfach
(((((((a*49)+b)*49+b)*49+c)*49+d)*49+e)*49+f)
ausgeben (alles 0-basiert), und alle Schleifen weglassen.

Weiß nicht, ob man da weiter bohren sollte.

Wenn du in der Lösung von Wutz nicht ++z nimmst sondern

for (n = m + 1;n <= 49; n++)
 if (searchCombination(tip,i,j,k,l,m,n,z)) return;
 else z+=10;

dann brauchst du zu z nur noch die Superzahl + 1 addieren und du hast die Ordinalzahl.
Den Rest kannst du sicher genau so eliminieren.

@volkard
Die Gruppe {1,2,3,4,5,6,0} bekommt die Ordinalzahl 1
Die Gruppe {1,2,3,4,5,6,1} bekommt die Ordinalzahl 2

Vielleicht sollte man das mal im Matheforum nachfragen.

Naja, es ist halt ne geschachtelte Summe über Binomialkoeffizienten. In LaTeX:

O = S + 10 \sum_{i=1}^{6}\sum_{j=a_{i-1}}^{a_i} {{49 - j} \choose {6 - i}}

wobei O die Ordinalzahl, S die Superzahl und a eine Folge mit a0 = 0, a1 = kleinste gezogene Zahl, a2 = nächsthöhere Zahl... seien.

Die Umsetzung ist dann ziemlich simpel, aber ein bisschen was will ich der Lottofee ja auch noch zu tun lassen.