3

私の質問を例で明確にしましょう。これは、Scala で末尾再帰を使用して記述された標準的な累乗アルゴリズムです。

def power(x: Double, y: Int): Double = {
  def sqr(z: Double): Double = z * z
  def loop(xx: Double, yy: Int): Double = 
    if (yy == 0) xx
    else if (yy % 2 == 0) sqr(loop(xx, yy / 2))
    else loop(xx * x, yy - 1)

  loop(1.0, y)
}

ここでsqrは、 メソッドを使用して の結果の 2 乗を生成しloopます。このような単純な操作のために特別な関数を定義するのは、良い考えとは思えません。loop(..) * loop(..)しかし、計算が 2 倍になるので、代わりに書くことはできません。

val関数の有無にかかわらずそれを書くこともできsqrます：

def power(x: Double, y: Int): Double = {
  def loop(xx: Double, yy: Int): Double = 
    if (yy == 0) xx
    else if (yy % 2 == 0) { val s = loop(xx, yy / 2); s * s }
    else loop(xx * x, yy - 1)

  loop(1.0, y)
}

sqrを使用しているため、 を使用したバリアントよりも見栄えが良いとは言えませんstate variable。最初のケースはより機能的で、2 番目の方法はより Scala に適しています。

とにかく、私の質問は、関数の結果を後処理する必要がある場合の対処方法です。たぶん、Scalaにはそれを達成するための他の方法がありますか?

4

4 に答える 4

6

あなたはその法律を使用しています

x^(2n) = x^n * x^n

しかし、これは

x^n * x^n = (x*x)^n

したがって、再帰後の 2 乗を避けるために、y が偶数の場合の値は、コード リストの下に表示されるようにする必要があります。

このように、テールコールが可能になります。完全なコードは次のとおりです (Scala を知らないので、構文を類推して正しく理解できれば幸いです)。

def power(x: Double, y: Int): Double = {
    def loop(xx: Double, acc: Double, yy: Int): Double = 
      if (yy == 0) acc
      else if (yy % 2 == 0) loop(xx*xx, acc, yy / 2)
      else loop(xx, acc * xx, yy - 1)

    loop(x, 1.0, y)
}

これはHaskellのような言語です：

power2 x n = loop x 1 n 
    where 
        loop x a 0 = a 
        loop x a n = if odd n then loop x    (a*x) (n-1) 
                              else loop (x*x) a    (n `quot` 2)
于 2013-07-04T12:19:43.483 に答える
2

私のコメントで、あなたの実装は末尾呼び出しを最適化できないことを指摘しましたyy % 2 == 0。そのため、大きな入力の場合、スタックがオーバーフローする可能性があります。

これに対する一般的な解決策は、関数をトランポリンすることです。再帰呼び出しを、 などの「後処理」でマップできるデータに置き換えますsqr。次に、結果はインタープリターによって計算されます。インタープリターは戻り値をステップスルーし、それらをスタックではなくヒープに格納します。

Scalaz ライブラリは、データ型とインタープリターの実装を提供します。

import scalaz.Free.Trampoline, scalaz.Trampoline._

def sqr(z: Double): Double = z * z

def power(x: Double, y: Int): Double = {
  def loop(xx: Double, yy: Int): Trampoline[Double] =
    if (yy == 0)
      done(xx)
    else if (yy % 2 == 0)
      suspend(loop(xx, yy / 2)) map sqr
    else
      suspend(loop(xx * x, yy - 1))

  loop(1.0, y).run
}

ただし、これを行うにはかなりのパフォーマンス ヒットがあります。この特定のケースでは、Igno のソリューションを使用して、呼び出す必要がsqrまったくないようにします。ただし、上記の手法は、アルゴリズムに対してそのような最適化を行うことができない場合に役立ちます。

于 2013-07-04T11:49:22.387 に答える
0

この特定のケースでは

  • ユーティリティ関数は不要
  • 鈍いパイプ/暗黙の必要はありません

  • 最後に単一のスタンドアロン再帰呼び出しのみが必要 - 常に末尾再帰を提供する

    def power(x: Double, y: Int): Double = 
  if (y == 0) x
  else {
    val evenPower = y % 2 == 0
    power(if (evenPower) x * x else x, if (evenPower) y / 2 else y - 1)
  }
于 2013-11-21T23:56:55.197 に答える