el almacenamiento de secuencias conocidas en c

Question

Estoy trabajando en Proyecto Euler Nº 14 en C y tienen descubierto el algoritmo básico; sin embargo, se ejecuta insoportablemente lento para un gran número, por ejemplo, 2.000.000 como se quiera; Supongo porque tiene que generar la secuencia una y otra vez, a pesar de que no debe haber una manera de almacenar secuencias conocidas (por ejemplo, una vez que tengamos a un 16, sabemos por experiencia previa que los próximos números son 8, 4, 2 , a continuación, 1).

No estoy exactamente seguro de cómo hacer esto con matriz de longitud fija de C, pero debe haber una manera buena (que es increíblemente eficiente, estoy seguro). Gracias de antemano.

Esto es lo que tengo actualmente, si ayuda.

#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

Su programa original necesita 3,5 segundos en mi máquina. Es insoportablemente lento para usted?

Mi sucia y fea versión necesita 0,3 segundos. Se utiliza una matriz global para almacenar los valores ya calculados. Y utilizarlos en los cálculos futuros.

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

Dado que este es esencialmente un programa de usar y tirar (es decir, una vez que ejecuta este programa y tiene la respuesta, usted no va a estar apoyando durante años :), sugeriría tener una variable global para mantener la longitudes de secuencias ya calculado:

int lengthfrom[UPTO] = {};

Si su tamaño máximo es de unos pocos millones, entonces estamos hablando megabytes de memoria, que debe caber fácilmente en la memoria RAM a la vez.

Lo anterior será inicializar la matriz a ceros en el inicio. En su programa - para cada iteración, compruebe si la matriz contiene cero. Si lo hace - que tendrá que seguir adelante con el cálculo. Si no - entonces usted sabe que el ejercicio de continuaría para que muchas más iteraciones, por lo que sólo tiene que añadir al número que has hecho hasta ahora y ya está. Y luego almacenar el nuevo resultado en la matriz, por supuesto.

no tener la tentación de utilizar una variable local para una matriz de este tamaño:., Que tratará de asignarlo a la pila, lo cual no será lo suficientemente grande y es probable que bloquee

También - recuerde que con esta secuencia los valores suben así como hacia abajo, por lo que tendrá que hacer frente a que en su programa (probablemente por tener la matriz ya que los valores UPTO, y usar un assert() para protegerse de los índices mayor que el tamaño de la matriz).

Answer 3

Si no recuerdo mal, el problema no es un algoritmo lento: el algoritmo que tiene ahora es lo suficientemente rápido para PE le pide que haga. El problema es desbordamiento: a veces terminan multiplicando su número por 3 tantas veces que con el tiempo se exceda el valor máximo que se puede almacenar en un int firmado. Utilice enteros sin signo, y si esto sigue sin funcionar (pero estoy bastante seguro de que lo hace), el uso de 64 bits enteros (long long).

Esto debe correr muy rápido, pero si desea hacerlo aún más rápido, las otras respuestas que ya trata de eso.