0

私は自分のニーズに合わせて単純な多項式関連のライブラリを作成しています。今のところ、GF(2) 上の多項式ベースの多項式だけを扱っているので、単純に次のように表されます。

case class Polynomial(coeffs: BitSet)

だから私はちょうどのようなものを書くことができます

Polynomial(BitSet(0,1,2))

表現します

(x^2 + x + 1)

今、私は乗算関数について特に誇りに思っています。

def *(that: Polynomial): Polynomial = Polynomial {
    coeffs.foldLeft(BitSet.empty) { case (acc, i) => acc ^ that.coeffs.map(i +) }
}

しかし、今のところ、他の多項式モジュロによる簡約を表現するためのすべての努力は、同様の結果を示しませんでした。除算がやや複雑であることは確かに理解していますが、現在、非常に汚い再帰的なソリューションがあり、まったく好きではありません。私が現在持っているのは、次のようなものです (私たちが GF(2) にいることを忘れないでください)。（UPD：クラス外で実行できるようにするための簡略化されたコード）

  def foo(thisSet: BitSet, thatSet: BitSet): BitSet = {
    var ts = thisSet
    while (!ts.isEmpty && ts.max >= thatSet.max) {
      ts = ts ^ thatSet.map(_ - thatSet.max + ts.max)
    }
    ts
  }

それはうまく動作します (私はこれまでテストを書いていませんでしたが) が、私はきちんとしたものが欲しいです (せいぜい末尾再帰ですが、できれば折り畳み/マップ/縮小を使用するだけです.

4

1 に答える 1

0

単純なループをいつでも再帰的に書くことができます

あなたの foo 関数の例：

import scala.annotation.tailrec
def fooRec(thisSet : BitSet, thatSet : BitSet) : BitSet = {
    @tailrec def loop(acc : BitSet) : BitSet = {
        if (!acc.isEmpty && acc.max >= thatSet.max) loop(acc ^ thatSet.map(_ - thatSet.max + acc.max))
        else acc
    }
    loop(thisSet)
}                                         //> fooRec: (thisSet: scala.collection.BitSet, thatSet: scala.collection.BitSet)
                                          //| scala.collection.BitSet

foo(BitSet(1, 2, 0), BitSet(3, 0, 1))           //> res0: scala.collection.BitSet = BitSet(0, 1, 2)
fooRec(BitSet(1, 2, 0), BitSet(3, 0, 1))        //> res1: scala.collection.BitSet = BitSet(0, 1, 2)

var tsが内部再帰関数のパラメーターでloopあり、 whileがただの であることがわかりますif。

私の意見では、テール再帰関数と while ループは、パフォーマンスと可読性においてほとんど同じです。最適なスタイルを選択できます。

個人的には、このバージョンが while バージョンより汚いとは思いません。

于 2013-11-06T09:59:04.157 に答える