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 😀
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 😛 Si es difícil normalmente no hay tanta participación 🙂
Pero lo dicho… tomo nota 😀
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 😀
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 😀
Gracias y happy monday meetings!!
MMmm…
… pues nada, Jose felicidades!
Tanto pensar como optimizar el cálculo, cuando la clave era como mostrar los resultados (aunque en mi defensa he de decir que nunca pensé que se incluyese este tiempo en el total… :P).
De todos modos esto nos recuerda una lección básica sobre rendimiento: este no siempre se pierde donde más obvio parece…
Saludos!
«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 :)»
¿Se parece más a código C++ de producción (STL, BOOST, etc)? 😛
Me alegro mucho de haber ganado el reto.
Gracias Eduard. 🙂
@Rafa, no siempre las lambdas son lo mejor. Son alternativas interesantes a tener en cuenta, pero ni todo son lambdas ni todo tampoco lo son. Lo mismo ocurre con parallels… todo es digno de ser analizado sin despreciar nada.
Y ahora… a esperar para ver si David se anima y nos presenta un día de estos otro interesante reto.
Quedaremos a la espera de retos más complicados a ver… :-)))
#andrechi Si que me llegó, de todos modos tenías mi correo en el enunciado del problema 🙂 Tomo nota de los comentarios para la próxima, gracias!
#espinete
A ver si saco hoy un rato y pongo un comentario con algunas implementaciones
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 fib = null; fib = null; cache = new Dictionary ();
fib = n => n < = 1 ? 1 : fib(n-1) + fib(n-2); Algoritmo Recursivo con lambdas y cache Func
Dictionary
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 )
Enhorabuena Jorge.
Hay que j**erse cono lo de la salida en pantalla, pensé que la salida a consola era un requisito.
jajaja.
David, en las pruebas que hice, (pocas por falta de tiempo) phi era más rápido que la suma de tres. Lo que pasa es que phi es un poco tramposo, porque es un cálculo por aproximación de modo que tiene +/-E, como el problema esta acotado (del 1 al 44) pueden ajustarse para que el error sea 0.
En fin, divertido.
Una cosita al publicar resultados mejor que sean DateTime.Ticks (http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=357164)