ideas para mejorar velocidad de código nofibonacci.

[Tortoiseius]

Bueno, primeramente hola y no vengo a que me hagan la tarea , mas bien vengo a que me ayuden a mejorar el tiempo de ejecución de este programa que hice o bien si se les ocurre un algoritmo mejor pues sería bien recibido, pero explicado por que quiero aprender : ).

El programa tiene que resolver el mayor de los casos en tiempo <= 1 segundo y el mio tarda como 7.
aqui el problema en una imagen:


otro ejemplo de entrada: 13
otro ejemplo salida:4 6 7 9 10 11 12

¿Cómo podría hacerlo mas rápido, hasta tiempo <=1 segundo ? D:

#include <cstdlib>
#include <iostream>

using namespace std;



int vector[300000];
int main()
{

int numero,j,i,N;

cin>>N;

vector[0]=1;
vector[1]=2;
i=1;
while(numero<N)
{ i++;
vector[i]=vector[i-2]+vector[i-1];

numero=vector[i-1];
while(numero<vector[i]){
numero++;
if(numero!=3&&numero!=vector[i-1]&&numero!=vector[i]&&numero<N)
cout<<numero<<" ";
}
}
return 0;
}

mi algoritmo es simple, creo un numero fibonacci, me regreso al anterior numero fibonacci y cuento a la vez que imprimio hasta llegar al numero fibonacci que cree, y así sucesivamente D:, pero es muy tardado .

¿alguna idea?, no precisamente en código pero ideas...
Saludos : ).

[Instru]

Bueno. No fue tan complicado :).

Para poder lograr construir un algoritmo mas eficiente hay que saber un poco de analisis de algoritmos. Aunque sea lo mas basico.

En este caso tu algoritmo es bonito.
Pero el cuello de botella es que tienes ciclos anidados.
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.

Despues de de analizar un poco el programa logre obtener una solucion donde solo se utiliza un ciclo.

Código:

#include <cstdlib>
#include <iostream>

using namespace std;



int vector[300000];
int main()
{
	int numero,j,i,N;
	numero=0;
	i=0;
	j=2;
	
	
	cin>>N;
	vector[0]=1;
	vector[1]=2;
	for(i=3; i<N; i++)
	{
		if(i==vector[j-2]+vector[j-1])
		{
			vector[j]=i;
			j++;
		}
		else
			cout<<i<<" ";
	}
	return 0;
}

Si vez el codigo es mas sencillo aun.

El chiste es ir imprimiendo tooodos los numeros menos los de la serie de fibonacci.
Entonces solo necesitamos revisar que el numero que vamos a imprimir no sea de la serie, y si lo es, pues lo almacenamos para asi tener el siguiente valor de la serie y estarlo probando.
Pruebalo, seguramente correra en un factor lineal en vez de cuadratico, lo cual acelera muuucho a la hora de probar casos de incluso mas de 30000.

Podria pensar en otro tipo de algoritmos para intentar acelerarlo mas, pero ya seria un incremento insignificante en velocidad y gran incremento en complejidad, por lo que no valdria la pena.

Espero te sea de ayuda.

SAludos

[sam90]

Igualmente si analisas el otro codigo no es cuadratico por mas que tenga dos while anidados. Fijate que la variable numero aumenta en uno por uno al igual que lo esta haciendo en el tuyo. Y no vuelve a empezar a contar cuando sale del while interno.

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.

Si te fijas bien con cualqioera de los dos codigos si escribimos en un archivo redirigiendo el stdout el algoritmo corre en menos de unsegudno.
Ejecutucando de esta forma:
miprog.exe > salida.txt

o en linux
./miprog > salida.txt

Saludos

Es mas se podria tener ya precargado la serie de fibonacci.

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 << " ";
 

[Instru]

Tienes razón. El segundo while no implica un factor cuadrático.
De hecho despues de analizar un poco mas, he visto que el mismo compilador(en linux gcc), al hacer las optimizaciones necesarias queda casi de la misma manera.
Es poca la diferencia.

Sin embargo podria defender un poco el codigo que puse ya que al hacer un menor numero de comparaciones (if's.) y la simplicidad del codigo en si ayudan en poca medida a la eficiencia.

Ahora, si lo que tarda mas es imprimir en pantalla( en mi maquina es instantaneo hasta con el número 100,000). Seria bueno ver si lo mas pesado es el mismo cout, o el conjunto de llamadas al sistema para imprimir en pantalla.
Seria bueno saberlo.
Aun asi. Buen experimento jajaja.

Saludos

[sam90]

YO lo probe con 300.000 y ahi tarde unos cuantos segundos. Desde que empece a programar siempre aprecia que en los ciclos esos cuanto menos informacion detallaba mas rapida iba la cuentios.

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.

Saludos

[dem4ply]

aqui les pongo mi solucion en la que creo que se hacen menos comparaciones y para ver bien el tiempo real sin las impreciones solo es cosa de omitirlas y asignar a una variable el contador i cuando hay una imprecion

Código C++:

#include <iostream>
 
using namespace std;
 
int main()
{
    int num1 = 1, num2 = 1, n;
    
    cout << "Ingrese N: ";
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        if (i < num2)
            for(;i < num2 && i < n; ++i)
                cout << "i: " << i << "  ";
        num2 += num1;
        num1 = num2 - num1;
    }
    system("pause");
    return 0;
}
 

[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,