Wie mache ich eine Funktion mit futures tail-rekursiv?

In meiner Scala app, ich habe eine Funktion aufruft, die eine Funktion liefert ein Ergebnis vom Typ Future[T]. Ich übergeben zu müssen, das zugeordnete Ergebnis in meinem rekursiven Aufruf der Funktion. Ich will, dass das tail-rekursiv ist, aber die Karte (oder flatMap) bricht die Fähigkeit, das zu tun. Ich bekomme die Fehlermeldung "der Rekursive Aufruf nicht in den Schwanz-position."

Unten ist ein einfaches Beispiel für dieses Szenario. Wie können diese modifiziert werden, so dass der Aufruf tail-rekursiv (ohne das untergraben der Vorteile von Futures mit einer Erwarten.Ergebnis())?

import scala.annotation.tailrec
import scala.concurrent.{Await, Future}
import scala.concurrent.duration._

implicit val ec = scala.concurrent.ExecutionContext.global

object FactorialCalc {
  def factorial(n: Int): Future[Int] = {

    @tailrec
    def factorialAcc(acc: Int, n: Int): Future[Int] = {
      if (n <= 1) {
        Future.successful(acc)

      } else {
        val fNum = getFutureNumber(n)
        fNum.flatMap(num => factorialAcc(num * acc, num - 1))
      }
    }

    factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)
}

Await.result(FactorialCalc.factorial(4), 5.seconds)

InformationsquelleAutor Donuts | 2013-06-06

34

Ich könnte mich irren, aber Ihre Funktion nicht tail recursive in diesem Fall.

Tail recursion hilft uns nicht verbrauchen, die Stapel im Fall verwenden wir rekursive Funktionen. In Ihrem Fall, sind wir jedoch nicht tatsächlich verbrauchen die Stapel in der Art eines typischen rekursiven Funktion.

Dies ist, weil die "rekursiven" Aufruf asynchron erfolgen, auf einige Faden von der Ausführungskontext. So ist es sehr wahrscheinlich, dass dieser rekursive Aufruf nicht auch sich auf dem gleichen Stapel wie die erste Aufforderung.

Den factorialAcc Methode erstellt das künftige Objekt, die schließlich Auslöser der "rekursiven" Aufruf asynchron. Danach ist es sofort tauchte aus dem Stapel.

So, das ist eigentlich nicht stack Rekursion und der stack wächst nicht proportional zu n ist, bleibt es in etwa auf eine Konstante Größe.

Können Sie ganz einfach prüfen, indem Sie eine Ausnahme auslösen, die irgendwann in der factorialAcc Methode und Prüfung der stack-trace.

Schrieb ich Ihr Programm zu erhalten, eine besser lesbare stack-trace:
```
object Main extends App {
  import scala.concurrent.{Await, Future}
  import scala.concurrent.duration._

  implicit val ec = scala.concurrent.ExecutionContext.global

  def factorialAcc(acc: Int, n: Int): Future[Int] = {

    if (n == 97)
      throw new Exception("n is 97")

    if (n <= 1) {
      Future.successful(acc)

    } else {
      val fNum = getFutureNumber(n)
      fNum.flatMap(num => factorialAcc(num * acc, num - 1))
    }
  }


  def factorial(n: Int): Future[Int] = {
      factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)

  val r = Await.result(factorial(100), 5.seconds)
  println(r)

}
```
Und die Ausgabe ist:
```
Exception in thread "main" java.lang.Exception: n is 97
at test.Main$.factorialAcc(Main.scala:16)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:278)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:274)
at scala.concurrent.impl.CallbackRunnable.run(Promise.scala:29)
at scala.concurrent.impl.ExecutionContextImpl$$anon$3.exec(ExecutionContextImpl.scala:107)
at scala.concurrent.forkjoin.ForkJoinTask.doExec(ForkJoinTask.java:262)
at scala.concurrent.forkjoin.ForkJoinPool$WorkQueue.runTask(ForkJoinPool.java:975)
at scala.concurrent.forkjoin.ForkJoinPool.runWorker(ForkJoinPool.java:1478)
at scala.concurrent.forkjoin.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:104)
```
Damit Sie sehen können, dass der stack ist eigentlich kurz. Wenn dieser stack Rekursion sollte man gesehen haben über 97 Aufrufe der factorialAcc Methode. Stattdessen sehen Sie nur einen.

Ich denke diese Antwort wird auch für mich das, was ich brauche, jedoch gibt es noch einen leichten memory-leak, weil scala.gleichzeitige Futures nicht zusammengeführt.. Aber die twitter-Futures tun, durch eine Art von Zauberei. , Die being said, Sie haben in die TIEFE zu gehen, bevor dieses abstürzt. Weise, die tiefer als realistisch ist, so bin ich glücklich mit dieser.
Ich bin der Untersuchung etwas ähnliches wie here mit Spielen die WS-client-Bibliothek. Sie haben mehr Einblick in das memory-leak-Problem?
Wie würde die Stapel bleiben in etwa auf eine Konstante Größe? würde die Gesamtgröße schluckte als Stapel nicht nur eine Verteilung über verschiedene threads?
twitter.com/viktorklang/status/433957085621940225

InformationsquelleAutor Marius Danila
0

Wie über die Verwendung von foldLeft statt?
```
def factorial(n: Int): Future[Int] = future {
  (1 to n).foldLeft(1) { _ * _ }
}
```
Dieser findet den Punkt, der die Frage.. während das Beispiel funktioniert für eine tail-rekursive Lösung zu diesem problem.. das eigentliche problem ist, dass die Funktion sich selbst aufrufen MUSS, ist eine andere Funktion, gibt eine Zukunft. also das funktioniert hier nicht.

InformationsquelleAutor warpedjavaguy

Hier ein foldLeft Lösung, ruft eine andere Funktion zurückgibt, die eine Zukunft haben.

def factorial(n: Int): Future[Int] =
  (1 to n).foldLeft(Future.successful(1)) {
    (f, n) => f.flatMap(a => getFutureNumber(n).map(b => a * b))
  }

def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)

InformationsquelleAutor warpedjavaguy

-1

Machen factorialAcc Int zurückgeben und nur wickeln Sie es in eine Zukunft, in der factorial Funktion.

def factorial(n: Int): Future[Int] = {

    @tailrec
    def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) {
        acc
      } else {
        factorialAcc(n*acc,n-1)
      }
    }

    future {
      factorialAcc(1, n)
    }
}

dürfte.

die Funktion selbst MUSS eine andere Funktion aufrufen, gibt eine Zukunft. also das funktioniert hier nicht. Marius' Antwort ist korrekt obwohl.

InformationsquelleAutor Cubic

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.