Luna Flow
日本語

immut/sparse チュートリアル

このチュートリアルでは、多変数多項式の個々の係数を検索したい場合の SparsePolynomial の使い方を示します。構築、指数ベクトルによる係数の問い合わせ、項の追加、計算と評価です。

クイックスタート

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/immut",
}
test "sparse quick start" {
  let p = @immut.SparsePolynomial::from_array([([2U], 1), ([1U], 2), ([], 1)])
  inspect(p, content="1 + 2 * x + 1 * x^2")
  debug_inspect(p.get(@immut.ExponentVector::from_array([1U])), content="Some(2)")
}

p は x2+2x+1x^2 + 2x + 1 で、get は x1x^1 の係数を読みます。疎な多項式は昇順、つまり定数項から表示されます。

日常的なタスク

係数を検索する

get は現れない単項式に対して None を返します。これはその係数がゼロであることを意味します:

fn coefficient_or_zero(p : @immut.SparsePolynomial[Int], exponents : Array[UInt]) -> Int {
  p.get(@immut.ExponentVector::from_array(exponents)).unwrap_or(0)
}

test "lookup" {
  let p = @immut.SparsePolynomial::from_array([([1U, 1], 6), ([0U, 3], -1)])
  inspect(coefficient_or_zero(p, [1, 1]), content="6")
  inspect(coefficient_or_zero(p, [0, 3]), content="-1")
  inspect(coefficient_or_zero(p, [5]), content="0")
}

項を 1 つずつ追加する

add_term は新しい多項式を返します。打ち消し合った項は消えます:

test "add term" {
  let x2 = @immut.ExponentVector::from_array([2U])
  let p = @immut.SparsePolynomial::new().add_term(x2, 3).add_term(@immut.ExponentVector::one(), 1)
  inspect(p, content="1 + 3 * x^2")
  let q = p.add_term(x2, -3)
  inspect(q, content="1")
  inspect(p.size(), content="2")
}

add_term は呼び出すたびにマップを再構築します。単一の項による更新を多数行う場合は、項の配列を作って from_terms を 1 回呼び出すか、mutable/sparse を使ってください。

計算と評価

test "compute" {
  let x = @immut.SparsePolynomial::from_array([([1U], 1)])
  let y = @immut.SparsePolynomial::from_array([([0U, 1], 1)])
  let p = (x * y + x).pow(2)
  inspect(p, content="1 * x^2 + 2 * x^2x_1 + 1 * x^2x_1^2")
  inspect(p.eval([2, 3]), content="64")
  assert_true(p.eval_checked([2]) is None)
}

(2,3)(2, 3) における (xy+x)2(xy + x)^2 は (6+2)2=64(6 + 2)^2 = 64 です。p は 2 つの変数を使っているのに値が 1 つしか与えられていないため、eval_checked は None を返します。

先頭項を求める

マップは昇順なので、先頭項は最後のエントリです:

test "leading term" {
  let p = @immut.SparsePolynomial::from_array([([], 5), ([1U, 1], 2), ([3U], 1)])
  let terms = p.to_terms()
  let (lead, coeff) = terms[terms.length() - 1]
  inspect(lead, content="x^3")
  inspect(coeff, content="1")
}

さらに進む

アルゴリズムにおける係数の取り出し

よくあるパターンは、決まった単項式の集合、たとえば一次の部分の係数を読み取ることです:

fn linear_part(p : @immut.SparsePolynomial[Int], variables : Int) -> Array[Int] {
  Array::makei(variables, i => {
    let e = @immut.ExponentVector::one().with_exponent(i, 1)
    p.get(e).unwrap_or(0)
  })
}

test "linear part" {
  let p = @immut.SparsePolynomial::from_array([([1U], 3), ([0U, 0, 1], -2), ([1U, 1], 9), ([], 4)])
  debug_inspect(linear_part(p, 3), content="[3, 0, -2]")
}

項の格納との一致

同じ項から構築した疎な多項式と項多項式は同じ多項式です。異なるのは走査順序だけです:

test "agreement" {
  let terms = [([2U], 1), ([1U, 1], 3), ([], 4)]
  let s = @immut.SparsePolynomial::from_array(terms)
  let t = @immut.TermPolynomial::from_array(terms)
  assert_true(@immut.TermPolynomial::from_terms(s.to_terms()) == t)
  inspect(s.eval([1, 2]) == t.eval([1, 2]), content="true")
}

他の係数型上の多項式

luna-generic の能力を備えた係数型であれば何でも使えます。たとえば Double です:

test "double coefficients" {
  let p = @immut.SparsePolynomial::from_array([([2U], 0.5), ([], -1.0)])
  inspect(p.eval([2.0]), content="1")
}

よくある落とし穴

  • 昇順. to_terms() と表示は定数項から始まります。TermPolynomial は先頭項から始まります。
  • キーは正規形. [1, 0] と [1] は同じキーなので、どちらも x0x_0 の係数を検索します。
  • get_checked は get と同じ. 失敗の仕方が異なることはありません。係数を数値として読むには get(...).unwrap_or(0) を使ってください。
  • 再構築のコスト. イミュータブルな型では、add_term は呼び出しごとに O(mlog⁡m)O(m \log m) です。

次のステップ