Qual è il modo più veloce per scrivere la funzione di Fibonacci in Scala?

Ho esaminato alcune implementazioni della funzione di Fibonacci in Scala partendo da una molto semplice , a quelle più complicate .

Non sono del tutto sicuro quale sia il più veloce. Mi sto orientando verso l’impressione che quelli che usano la memoizzazione siano più veloci, tuttavia mi chiedo perché Scala non abbia una memoizzazione nativa.

Qualcuno può illuminarmi verso il modo migliore e più veloce (e più pulito) di scrivere una funzione fibonacci?

per me il più semplice definisce una funzione ricorsiva della coda interna:

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

Questo non ha bisogno di build alcun object Tuple per lo zip ed è facile da capire sintatticamente.

Le versioni più veloci sono quelle che si discostano dal solito schema di addizione in qualche modo. Molto veloce è il calcolo in qualche modo simile a un esponenziale binario veloce basato su queste formule:

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

Ecco un codice che lo utilizza:

 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 } 

Anche se questo non è molto ottimizzato (ad esempio il ciclo interno non è ricorsivo della coda), batterà le consuete implementazioni additive.

Scala ha la memoizzazione sotto forma di flussi.

 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 è un LinearSeq quindi potresti convertirlo in IndexedSeq se stai facendo molte chiamate di tipo fib(42) .

Tuttavia vorrei mettere in discussione il tuo caso d’uso per una funzione fibbonaci. Traboccherà a lungo in meno di 100 termini, quindi termini più grandi non sono molto utili a nulla. I termini più piccoli si possono semplicemente inserire in un tavolo e cercarli se la velocità è fondamentale. Quindi i dettagli del calcolo probabilmente non contano molto poiché per i termini più piccoli sono tutti veloci.

Se vuoi veramente conoscere i risultati per termini molto grandi, allora dipende se vuoi solo valori unici (usa la soluzione di Landei) o, se stai facendo un numero sufficiente di chiamate, potresti voler eseguire un calcolo preliminare l’intero lotto Il problema qui è che, ad esempio, il 100.000esimo elemento è lungo oltre 20.000 cifre. Quindi stiamo parlando di gigabyte di valori BigInt che causeranno il crash della tua JVM se proverai a tenerli in memoria. Potresti sacrificare l’accuratezza e rendere le cose più gestibili. Si potrebbe avere una strategia di memoizzazione parziale (ad esempio, memoize ogni 100 ° trimestre) che consente un adeguato compromesso memoria / velocità. Non esiste un chiaro analista per ciò che è più veloce: dipende dal tuo utilizzo e dalle tue risorse.

Questo potrebbe funzionare. ci vuole O (1) spazio O (n) tempo per calcolare un numero, ma non ha cache.

 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 coda più semplice Soluzione ricorsiva in grado di calcolare Fibonacci per grandi valori di n. La versione Int è più veloce ma è limitata quando si verifica un overflow di n > 46 interi

 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) } 

Questo è già stato risposto, ma si spera che troverete la mia esperienza utile. Ho avuto un sacco di problemi a riflettere su scala infinita di flussi. Poi, ho visto la presentazione di Paul Agron in cui ha fornito ottimi suggerimenti: (1) implementare prima la soluzione con elenchi di base, quindi se si intende generare la soluzione con tipi parametrizzati, creare una soluzione con tipi semplici come prima di Int.

usando questo approccio ho trovato una soluzione semplice (e per me, facile da capire):

  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}") 

Per arrivare alla soluzione di cui sopra ho prima creato, come da consiglio di Paul, la versione di “for-dummy”, basata su liste semplici:

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

Notate che ho cortocircuitato la versione della lista, perché se non l’avessi sarebbe andata avanti per sempre .. Ma .. a chi importa? ; ^) poiché è solo un bit di codice esplorativo.

Le risposte che usano Stream (compresa la risposta accettata) sono molto brevi e idiomatiche, ma non sono le più veloci. Gli stream memoizzano i loro valori (che non è necessario nelle soluzioni iterative), e anche se non si mantiene il riferimento allo stream, è ansible allocare molta memoria e quindi immediatamente raccogliere i dati . Una buona alternativa è usare un Iterator : non causa allocazioni di memoria, è funzionale in stile, breve e leggibile.

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

Il codice sottostante è veloce e in grado di calcolare con indici di input elevati. Sul mio computer restituisce il 10 ^ 6: numero di Fibonacci in meno di due secondi. L’algoritmo è in uno stile funzionale ma non utilizza elenchi o flussi. Piuttosto, si basa sull’uguaglianza \ phi ^ n = F_ {n-1} + F_n * \ phi, per \ phi la sezione aurea. (Questa è una versione della “formula di Binet”.) Il problema con l’utilizzo di questa uguaglianza è che \ phi è irrazionale (che coinvolge la radice quadrata di cinque) quindi divergerà a causa dell’aritmetica a precisione finita se interpretato in modo ingenuo usando i numeri di Float. Tuttavia, poiché \ phi ^ 2 = 1 + \ phi è facile implementare calcoli esatti con numeri della forma a + b \ phi per interi aeb, e questo è l’algoritmo sottostante. (La funzione “power” ha un po ‘di ottimizzazione, ma in realtà è solo un’iterazione della “mult” -multiplication su tali numeri.)

  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 } 

EDIT: un’implementazione che è più efficiente e in un certo senso anche più idiomatica si basa sulla libreria Spire di Typelevel per calcoli numerici e algebra astratta. Si può quindi parafrasare il codice di cui sopra in un modo molto più vicino all’argomento matematico (non abbiamo bisogno dell’intera struttura ad anello, ma penso che sia “moralmente corretto” includerlo). Prova a eseguire il seguente codice:

 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) ) } }