Luna Flow
日本語

mutable/term チュートリアル

このチュートリアルでは、常にソート済みかつ正規形に保たれるミュータブルなコンテナの中で多変数多項式を項ごとに構築する方法と、代わりに多項式全体の演算を使うべき場面を示します。

クイックスタート

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/mutable",
}
test "mutable term quick start" {
  let p : @mutable.TermPolynomial[Int] = @mutable.TermPolynomial::zero()
  p.add_term_inplace(@mutable.ExponentVector::from_array([1U, 1]), 3)
  p.add_term_inplace(@mutable.ExponentVector::from_array([2U]), 1)
  inspect(p, content="3 * xx_1 + 1 * x^2")
}

コンテナは挿入のたびにソートし直すので、常に先頭項から表示されます。

日常的なタスク

ループで項を集める

同じ指数ベクトルを持つ項はマージされ、打ち消し合う項は消えます。

test "collect" {
  let p : @mutable.TermPolynomial[Int] = @mutable.TermPolynomial::zero()
  for i in 0..<4 {
    p.add_term_inplace(@mutable.ExponentVector::from_array([(i % 2).reinterpret_as_uint()]), 1)
  }
  inspect(p, content="2 * x + 2")
  p.add_term_inplace(@mutable.ExponentVector::one(), -2)
  inspect(p, content="2 * x")
}

インプレースで乗算・スケーリングする

test "multiply" {
  let p = @mutable.TermPolynomial::from_array([([1U], 1), ([0U, 1], 1)])
  p.mul_inplace(p)
  inspect(p, content="1 * x_1^2 + 2 * xx_1 + 1 * x^2")
  p.scale_inplace(@mutable.ExponentVector::from_array([0U, 0, 1]), -1)
  inspect(p.total_degree().unwrap(), content="3")
}

構築しながら評価する

コンテナは常に正規形なので、問い合わせはいつでも行えます。

test "evaluate" {
  let p = @mutable.TermPolynomial::from_array([([2U], 1)])
  inspect(p.eval([3]), content="9")
  p.add_term_inplace(@mutable.ExponentVector::from_array([0U, 1]), 10)
  assert_true(p.eval_checked([3]) is None)
  inspect(p.eval([3, 1]), content="19")
}

x1x_1 を含む項を加えた後は、多項式の評価に 2 つの値が必要になります。

さらに進む

大きな和

add_inplace は項を 1 つずつ挿入します。オペランドが大きい場合は、和を一度に構築してください。

test "large sums" {
  let parts = Array::makei(50, i => @mutable.TermPolynomial::from_array([([i.reinterpret_as_uint()], 1)]))
  let all_terms : Array[(@mutable.ExponentVector, Int)] = []
  for part in parts {
    for t in part.to_terms() {
      all_terms.push(t)
    }
  }
  let sum = @mutable.TermPolynomial::from_terms(all_terms)
  inspect(sum.size(), content="50")
}

1 回の from_terms ですべての項を O(Nlog⁡N)O(N \log N) で正規化します。

イミュータブルなコードに引き渡す

test "freeze" {
  let p = @mutable.TermPolynomial::from_array([([1U], 2)])
  let frozen = p.to_immut()
  p.clear()
  inspect(frozen, content="2 * x")
  assert_true(p.is_zero())
}

よくある落とし穴

  • add_inplace のコスト。 オペランドが大きいとほぼ二次になります。上を参照してください。
  • 共有されるコンテナ。 代入は共有します。独立したコンテナには copy() を使ってください。
  • 順序。 イミュータブルな型と同様に、順序は次数付きで、同次数の場合は最も高い変数で比較します。

次のステップ