¿Cuál es la forma más rápida de escribir la función de Fibonacci en Scala?

Revisé algunas implementaciones de la función Fibonacci en Scala, comenzando desde una muy simple hasta las más complicadas .

No estoy del todo seguro de cuál es el más rápido. Me estoy inclinando por la impresión de que los que usan la memorización son más rápidos, sin embargo, me pregunto por qué Scala no tiene una memoria original.

¿Alguien puede iluminarme hacia la mejor y más rápida (y más limpia) forma de escribir una función de Fibonacci?

para mí, lo más simple define una función de cola interior recursiva:

def fib: Stream[Long] = { def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h + n) tail(0, 1) } 

Esto no necesita construir ningún objeto Tuple para el zip y es fácil de entender sintácticamente.

Las versiones más rápidas son las que se desvían del esquema de sum habitual de alguna manera. Muy rápido es el cálculo de alguna manera similar a una exponenciación binaria rápida basada en estas fórmulas:

 F(2n-1) = F(n)² + F(n-1)² F(2n) = (2F(n-1) + F(n))*F(n) 

Aquí hay un código que lo usa:

 def fib(n:Int):BigInt = { def fibs(n:Int):(BigInt,BigInt) = if (n == 1) (1,0) else { val (a,b) = fibs(n/2) val p = (2*b+a)*a val q = a*a + b*b if(n % 2 == 0) (p,q) else (p+q,p) } fibs(n)._1 } 

Aunque esto no está muy optimizado (p. Ej., El ciclo interno no es recursivo de cola), superará las implementaciones aditivas habituales.

Scala tiene memoria en forma de Streams.

 val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2) scala> fib take 100 mkString " " res22: String = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ... 

Stream es un LinearSeq por lo que es posible que desee convertirlo a IndexedSeq si realiza muchas llamadas de tipo fib(42) .

Sin embargo, cuestionaría cuál es su caso de uso para una función de fibbonaci. Se desbordará Long en menos de 100 términos, por lo que los términos más grandes no son de gran utilidad para nada. Los términos más pequeños se pueden pegar en una tabla y buscarlos si la velocidad es primordial. Entonces los detalles del cálculo probablemente no importan mucho ya que para los términos más pequeños todos son rápidos.

Si realmente quiere saber los resultados para términos muy grandes, entonces depende de si solo quiere valores únicos (use la solución de Landei) o, si está haciendo una cantidad suficiente de llamadas, es posible que desee precomputar todo el lote. El problema aquí es que, por ejemplo, el elemento número 100.000 tiene más de 20,000 dígitos. Así que estamos hablando de gigabytes de valores BigInt que bloquearán su JVM si intenta mantenerlos en la memoria. Podrías sacrificar la precisión y hacer las cosas más manejables. Podrías tener una estrategia de memorización parcial (digamos, memorizar cada centésimo término) que haga una compensación de memoria / velocidad adecuada. No existe una respuesta clara sobre cuál es el más rápido: depende de su uso y recursos.

Esto podría funcionar toma O (1) espacio O (n) tiempo para calcular un número, pero no tiene almacenamiento en caché.

 object Fibonacci { def fibonacci(i : Int) : Int = { def h(last : Int, cur: Int, num : Int) : Int = { if ( num == 0) cur else h(cur, last + cur, num - 1) } if (i < 0) - 1 else if (i == 0 || i == 1) 1 else h(1,2,i - 2) } def main(args: Array[String]){ (0 to 10).foreach( (x : Int) => print(fibonacci(x) + " ")) } } 

Una cola más simple Solución recursiva que puede calcular Fibonacci para valores grandes de n. La versión Int es más rápida pero está limitada, cuando se produce un desbordamiento de n > 46 integer

 def tailRecursiveBig(n :Int) : BigInt = { @tailrec def aux(n : Int, next :BigInt, acc :BigInt) :BigInt ={ if(n == 0) acc else aux(n-1, acc + next,next) } aux(n,1,0) } 

Esto ya ha sido respondido, pero espero que mi experiencia sea útil. Tuve muchos problemas para ponerme a pensar en las streams infinitas de scala. Luego, vi la presentación de Paul Agron donde dio muy buenas sugerencias: (1) implemente primero su solución con Listas básicas; luego, si va a generar su solución con tipos parametrizados, cree una solución con tipos simples como el primero.

Usando ese enfoque, se me ocurrió una solución realmente simple (y para mí, fácil de entender):

  def fib(h: Int, n: Int) : Stream[Int] = { h #:: fib(n, h + n) } var x = fib(0,1) println (s"results: ${(x take 10).toList}") 

Para llegar a la solución anterior, primero creé, según el consejo de Pablo, la versión “para el maniquí”, basada en listas simples:

  def fib(h: Int, n: Int) : List[Int] = { if (h > 100) { Nil } else { h :: fib(n, h + n) } } 

Tenga en cuenta que cortocircuité la versión de la lista, porque si no lo hiciera funcionaría para siempre … Pero … ¿a quién le importa? ; ^) ya que es solo un fragmento exploratorio de código.

Las respuestas que usan Stream (incluida la respuesta aceptada) son muy cortas e idiomáticas, pero no son las más rápidas. Las secuencias memorizan sus valores (lo cual no es necesario en soluciones iterativas), e incluso si no conserva la referencia a la secuencia, se puede asignar mucha memoria y luego recolectarla de forma inmediata . Una buena alternativa es usar un Iterator : no causa asignaciones de memoria, es funcional en estilo, corto y legible.

 def fib(n: Int) = Iterator.iterate(BigInt(0), BigInt(1)) { case (a, b) => (b, a+b) }. map(_._1).drop(n).next 

El siguiente código es rápido y puede calcularse con índices de entrada altos. En mi computadora, devuelve el número 10 ^ 6: th Fibonacci en menos de dos segundos. El algoritmo tiene un estilo funcional pero no usa listas o flujos. Por el contrario, se basa en la igualdad \ phi ^ n = F_ {n-1} + F_n * \ phi, para \ phi la proporción áurea. (Esta es una versión de “la fórmula de Binet”.) El problema con el uso de esta igualdad es que \ phi es irracional (que involucra la raíz cuadrada de cinco) por lo que divergerá debido a la aritmética de precisión finita si se interpreta ingenuamente usando números flotantes. Sin embargo, dado que \ phi ^ 2 = 1 + \ phi es fácil implementar cálculos exactos con números de la forma a + b \ phi para enteros a y b, y esto es lo que hace el algoritmo siguiente. (La función “potencia” tiene un poco de optimización, pero en realidad es solo una iteración de la multiplicación “mult” en tales números).

  type Zphi = (BigInt, BigInt) val phi = (0, 1): Zphi val mult: (Zphi, Zphi) => Zphi = { (z, w) => (z._1*w._1 + z._2*w._2, z._1*w._2 + z._2*w._1 + z._2*w._2) } val power: (Zphi, Int) => Zphi = { case (base, ex) if (ex >= 0) => _power((1, 0), base, ex) case _ => sys.error("no negative power plz") } val _power: (Zphi, Zphi, Int) => Zphi = { case (t, b, e) if (e == 0) => t case (t, b, e) if ((e & 1) == 1) => _power(mult(t, b), mult(b, b), e >> 1) case (t, b, e) => _power(t, mult(b, b), e >> 1) } val fib: Int => BigInt = { case n if (n < 0) => 0 case n => power(phi, n)._2 } 

EDITAR: una implementación que es más eficiente y en cierto sentido también más idiomática se basa en la biblioteca de Spire de Typelevel para cálculos numéricos y álgebra abstracta. Uno puede parafrasear el código anterior de una manera mucho más cercana al argumento matemático (no necesitamos toda la estructura del anillo, pero creo que es “moralmente correcto” incluirla). Intenta ejecutar el siguiente código:

 import spire.implicits._ import spire.algebra._ case class S(fst: BigInt, snd: BigInt) { override def toString = s"$fst + $snd"++"φ" } object S { implicit object SRing extends Ring[S] { def zero = S(0, 0): S def one = S(1, 0): S def plus(z: S, w: S) = S(z.fst + w.fst, z.snd + w.snd): S def negate(z: S) = S(-z.fst, -z.snd): S def times(z: S, w: S) = S(z.fst * w.fst + z.snd * w.snd , z.fst * w.snd + z.snd * w.fst + z.snd * w.snd) } } object Fibo { val phi = S(0, 1) val fib: Int => BigInt = n => (phi pow n).snd def main(arg: Array[String]) { println( fib(1000000) ) } }