ideas para mejorar velocidad de código nofibonacci.

[HackmanC]

Hola,

Iniciado por Instru

... Para poder lograr construir un algoritmo mas eficiente hay que saber un poco de analisis de algoritmos. Aunque sea lo mas basico. ...
... Una de las primeras cosas que hay que intentar cambiar para hacer un algoritmo mas eficiente es quitar en lo mas que se pueda los ciclos anidados. ...

Esos dos enunciados son posiblemente lo mejor que haya leido de programación en mucho tiempo.

Iniciado por Instru

int vector[300000];
...
{
if(i==vector[j-2]+vector[j-1])
{
[/CODE]

Posiblemente no es necesario guardar toda la lista, simplemente los últimos dos valores, y en cada ciclo se hace una suma y dos restas por lo que se agrega un par de ciclos de procesador.

Iniciado por sam90

... Ademas si te fijas tarda casi lo mismo que el otro codigo. Yo creo que la gran diferencia de tiempo se esta perdiendo en el hecho de escribir en pantalla.

Definitivamente es cierto, un lenguaje más complejo siempre conlleva mas operaciones, cout hace muchas operaciones internamente, (comparado con el int 21 de assembler).

Iniciado por sam90

Código C:

for (i = 4 ; i < N ; i++)
  if ( (i != 3 && i != 5 && i != 8 && i != 13 && i != 21 && i != 34 && i != 55 && i != 89 && i != 144 )  && (i != 233 &&  i != 377 && i != 610 && i !=987 && i !=1597 && i !=2584 && i !=4181 && i !=6765 && i !=10946 &&  i != 17711 && i != 28657 && i != 46368 && i != 75025 && i != 121393 && i != 196418 && i != 317811 ))
      cout << i << " ";
 

Por cada ciclo se van a realizar tantas comparaciones que no creo que optimize mucho el código, cuando vaya por el 28657 se van a realizar mínimo 10 'not equals' por cada número, lo cual no creo que sea eficiente.

Iniciado por sam90

... Desde Qbasic que notaba esa letencia si imprimia en pantalla mientras calculaba cosas. Asi que creo que debe ser el problema de las llamadas al sistema para imprimir en pantalla lo que lo deben demorar. ...

Definitivamente un print de QBasic no ejecuta una interrupción de video simplemente, internamente realiza muchas operaciones.

Ahora bien ... no sé si yo no entendí algo .. pero realmente optimizado sería 'ALGO' así, a menos que yo no haya entendido el problema:

Código C:

int a = 1;
    int b = 2;
 
    int i;
    int p = a + b;
 
    for (i = p; i < 300; i++) {
        if (i == p) {
            a = b;
            b = i;
            p = a + b;
        } else {
            printf ("%d\n", i);
        }
    }
 

Se usa poca memoria y se cambian los valores solamente cuando es el siguiente de la serie, además no se suma ni resta en cada ciclo, solamente cuando encuentra un número de la secuencia, posiblemente me ahorro mucho con el printf, pero ya es cuestion de usar el cout, para obtener la misma velocidad de antes. Si las variables se almacenan en registros del procesador, el código va a ser sumamente rápido.

Saludos,