Speichern von bekannten Sequenzen in c

Question

Ich arbeite an Projekt Euler # 14 in C und haben aus dem Grundalgorithmus gemustert; jedoch läuft es unerträglich langsam für eine große Zahl, z.B. 2.000.000 als wollte; Ich nehme an, weil sie die Sequenz immer und immer wieder zu erzeugen haben, obwohl es sollte ein Weg sein, speichern bekannte Sequenzen (zum Beispiel, wenn wir auf ein 16 bekommen, wissen wir aus Erfahrung, dass die nächsten Zahlen sind 8, 4, 2 , dann 1).

Ich bin nicht ganz sicher, wie diese mit fester Länge Arrays mit C zu tun, aber es muss einen guten Weg sein (die erstaunlich leistungsfähig ist, ist mir sicher). Vielen Dank im Voraus.

Hier ist, was ich zur Zeit habe, wenn es hilft.

#include <stdio.h>
#define UPTO 2000000

int collatzlen(int n);

int main(){
    int i, l=-1, li=-1, c=0;
    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);
    return 1;
}

/* n != 0 */
int collatzlen(int n){
    int len = 0;
    while(n>1) n = (n%2==0 ? n/2 : 3*n+1), len+=1;
    return len;
}

Answer 1

Ihr ursprüngliches Programm benötigt 3,5 Sekunden auf meinem Rechner. Ist es unerträglich langsam für Sie?

Meine schmutzig und hässlich Version benötigt 0,3 Sekunden. Es verwendet ein globales Array zum Speichern der Werte bereits berechnet. Und sie in Zukunft Berechnungen verwenden.

int collatzlen2(unsigned long n);
static unsigned long array[2000000 + 1];//to store those already calculated

int main()
{
    int i, l=-1, li=-1, c=0;
    int x;
    for(x = 0; x < 2000000 + 1; x++) {
        array[x] = -1;//use -1 to denote not-calculated yet
    }

    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen2(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);

    return 1;
}

int collatzlen2(unsigned long n){
    unsigned long len = 0;
    unsigned long m = n;
    while(n > 1){
        if(n > 2000000 || array[n] == -1){ // outside range or not-calculated yet
            n = (n%2 == 0 ? n/2 : 3*n+1);
            len+=1;
        }
        else{ // if already calculated, use the value
            len += array[n];
            n = 1; // to get out of the while-loop
        }
    }
    array[m] = len;
    return len;
}

Answer 2

Da dies im Wesentlichen ein Wegwerf-Programm (das heißt, wenn Sie es ausgeführt haben und bekam die Antwort, Sie gehen nicht es seit Jahren zu unterstützen :), ich würde vorschlagen, eine globale Variable, die die halten Längen von Sequenzen bereits berechnet:

int lengthfrom[UPTO] = {};

Wenn Sie Ihre maximale Größe ein paar Millionen, dann sind wir Megabyte Speicher zu sprechen, die sich leicht in RAM auf einmal.

passen sollte

Das oben wird die Array Nullen beim Start initialisieren. In Ihrem Programm - für jede Iteration, prüfen, ob die Array Null enthält. Ist dies der Fall - Sie werden bei der Berechnung gehen zu halten haben. Wenn nicht - dann wissen Sie, dass auf tragen würde weitergehen für so viele mehr Iterationen, so nur hinzufügen, dass auf die Zahl, die Sie bisher getan haben und du bist fertig. Und dann speichern Sie das neue Ergebnis im Array, natürlich.

Do für ein Array nicht versucht sein, von dieser Größe eine lokale Variable zu verwenden:., Die es auf dem Stapel zuweisen wird versuchen, die nicht groß genug sein wird, und wird wahrscheinlich abstürzen

Auch - denken Sie daran, dass die Werte mit dieser Sequenz sowie nach unten gehen, so dass Sie mit der in Ihrem Programm (wahrscheinlich das Array fertig zu werden brauchen länger, indem als UPTO Werte, und unter Verwendung eines assert() zum Schutz vor Indizes größer ist als die Größe des Arrays).

Answer 3

Wenn ich mich richtig erinnere, Ihr Problem ist nicht ein langsamer Algorithmus: Der Algorithmus, den Sie jetzt haben, ist schnell genug für das, was PE fordert Sie zu tun. Das Problem ist, Überlauf: Sie manchmal Ihre Zahl von 3 so oft am Ende multipliziert wird, dass es schließlich den Maximalwert übersteigt, der in einem signed int gespeichert werden kann. Verwenden Sie unsigned ints, und wenn das immer noch nicht funktioniert (aber ich bin mir ziemlich sicher, dass es der Fall ist), verwenden 64-Bit ints (long long).

Dies sollte sehr schnell laufen, aber wenn Sie es noch schneller machen wollen, die anderen Antworten bereits angesprochen, dass.