Tenemos Ganador al Juego de Fibonacci!!

Lo primero.. Gracias a esos 28 pedazo de participantes :) Me lo he pasado genial, de hecho no me creía que se animase tanta gente a participar. Ha sido una pena el problema con algunos antivirus que se han comido las soluciones. Ya lo sabemos, a partir de ahora texto plano con el algoritmo :D

Por cierto, tomo nota, ha habído un comentario general pidiendo retos más complicados. Este era sencillo y no pedía mucha potencia de calculo, ni tiempo de desarrollo, es para que pudiéséis seguir con vuestras vidas durante el reto :P  Si es difícil normalmente no hay tanta participación :)

Pero lo dicho... tomo nota :D

Soluciones propuestas

Ha sido muy variopinto, todos los participantes sabían que la solución recursiva tradicional no es más que un algoritmo "de laboratorio" y han planteado diversas soluciones. En C#, vb.net  y hasta en IL :)  Aquí os destaco los algoritmos más utilizados...

Algoritmo Recursivo con cache

El de toda la vida, pero guardando cada calculo en un Dictionary, por ejemplo, de modo que cada nueva llamada resultará en una suma de valores  precalculados en el Dictionary.

Sumas basadas en arrays

Se sustituye la llamada recursiva por una iteración donde se van sumando valores en un array.

Sumas con 3 variables

Igual que la anterior, pero se elimina el array, porque realmente solo hacen falta 3 valores. Actual, Anterior1 y Anterior2.

Calculos con el número phi

Estos me pillaron por sorpresa :) Pero cuesta más tiempo hacer el calculo y paralelizarlo que sumar los valores. Habría que verlo para calcular valores más grandes.

Por lo que he visto muchos tienen ya las lambdas de .net como ciudadanos de primer nivel... cada vez más el código .net me recuerda menos a código .net :)

Al grano, cómo han acelerado el algoritmo?

La mayoría del trabajo de los participantes ha pasado por encontrar el algoritmo más rápido para fibonacci. 

Hay personas que han utilizado la librería de parallels para intentar acelerar un poco el cálculo. ( desafortunadamente, fibonacci tradicional no es la mejor oportunidad para que parallels se luzca. El cálculo esta basado en valores anteriores, de modo que tiene tinte secuencial por naturaleza.

Pero, no solo del algoritmo vive la aplicación...se puede paralelizar:

a) Ir mostrando el resultado mientras se realiza el cálculo

b) El cálculo en sí, siempre y cuando no se utilice el método secuencial. Por ejemplo los que utilizan el cálculo con phi, si hacen un Parallel.For para calcular los valores por separado.

Posiblemente para valores más grandes Parallels hubiese marcado la diferencia. )

Pero el tiempo total no era sólo el tiempo del algoritmo, de hecho era lo mínimo en la mayoría de los casos...al ser un número tan bajo, la mayoría del tiempo se invierte en presentar los valores al usuario. De modo que ahí es donde se ha marcado la diferencia.

Las soluciones pasaban por presentar strings por consola en cada iteración, concatenar con stringbuilder antes de presentar por pantalla, sacar los valores a un archivo de texto... y la inesperada aproximación del ganador.

Utilizando el mismo algoritmo que muchos participantes, la diferencia ha sido abismal, mirad algunos de los tiempos ( al final del post podéis ver como he hecho las pruebas):

4  - 187141

3  - 179870

2 -   16186   ( diferencia de usar un archivo en lugar de la consola )

1 - 959

Venga... cuál es la diferencia ?

La diferencia, ha sido que nuestro Ganador del juego, Jorge Serrano ha utilizado una aplicación Windows Forms para presentar el resultado. Como muestran los timers, el tiempo en mostrar la información por consola requiere mucho mas trabajo que mostrarla en un control de WinForms.

Felicidades Jorge!! te tengo que mandar el detalle, esperamos foto en el blog eh :D

Las pruebas

He sufrido, lo reconozco. La próxima vez tengo que trabajar más en la descripción del reto O=)

Primero he estandarizado la forma en la que se tomaba el tiempo..de modo que he plantado Stopwatch por vuestro código.. Start justo al empezar el algoritmo y stop justo al acabar la visualización. He medido el valor de ElapsedTicks. A los que no tenían visualización les he añadido un for concatenando con stringbuilder.

A los que me habéis enviado varias opciones.. las he probado todas y solo he tenido en cuenta la más rápida.

Para tomar un valor por participante, he tomado la media de 5 ejecuciones en frío de cada algoritmo.

Para la próxima, posiblemente de yo el esqueleto de código e indique dónde hay que rellenar con el algoritmo :D

Gracias y happy monday meetings!!

Comments

• Anonymous
  November 23, 2008
  PingBack from http://blog.a-foton.ru/index.php/2008/11/24/tenemos-ganador-al-juego-de-fibonacci/

• Anonymous
  November 24, 2008
  :o felicitaciones al ganador!!

• Anonymous
  November 24, 2008
  Como comentaba en el post se han utilizado diferentes algoritmos en el juego de fibonacci, aquí tenéis una referencia rápida del código básico ( vamos, versión entendible y mejorable :) ) de las implementaciones más utilizadas. Algoritmo recursivo básico con lambdas Func<uint,uint> fib = null;   fib = n => n <= 1 ? 1 : fib(n-1) + fib(n-2); Algoritmo Recursivo con lambdas y cache Func<uint,uint> fib = null; Dictionary<uint,uint> cache = new Dictionary<uint,uint>();   fib = n => {     if ( n <= 1 ) return 1;                   if (cache.ContainsKey(n))                      return cache[n];                   uint res = fib(n-1) + fib(n-2);         cache.Add(n, res);   return res; } Sumas basadas en arrays uint []valores = new uint[44]; valores[0] = 1; valores[1] = 1; for ( int i=2;i<=43;i++ ) { valores[i] = valores[i-1] + valores[i-2]; } Sumas con 3 variables uint current; uint currentSub1 = 1; uint currentSub2 = 1; for ( int i=2;i<=43;i++ ) { current = currentSub1 + currentSub2; currentSub2 = currentSub1; currentSub1 = current; } Calculos con el número phi Os pongo la fórmula directamente :) f(n) = ( aureo^n - (-aureo)^-n ) / raiz( 5 )

• Anonymous
  March 08, 2009
  <1,2,3,5,8,15.................> numero de oro

• Anonymous
  September 21, 2009
  necesito que me ayuden com mi tarea de mate. cual es la formula para sacar fibonacci. me daran 1/2 de punto porfavor chavos

• Anonymous
  September 21, 2009
  compañeros  del humboldt que pex pasenme su correo el mio es kimliz48@hotmail.com