Luna Flow
日本語

mutable/sparse チュートリアル

このチュートリアルでは、ミュータブルな SparsePolynomial を累積器として使う方法を示します。指数ベクトルによる係数の設定と加算を対数時間で行い、積を項ごとに展開し、結果を凍結します。

クイックスタート

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/mutable",
}
test "mutable sparse quick start" {
  let x = @mutable.ExponentVector::from_array([1U])
  let p : @mutable.SparsePolynomial[Int] = @mutable.SparsePolynomial::new()
  p.set_coefficient(x, 3)
  p.add_term_inplace(x, -1)
  debug_inspect(p.get(x), content="Some(2)")
}

日常的なタスク

単項式を数える

多項式を単項式の多重集合として使います。単項式が現れるたびに、その係数に 1 を加えます。

test "counting" {
  let words = [[1U], [0U, 1], [1U], [1U, 0], [0U, 2]]
  let counts : @mutable.SparsePolynomial[Int] = @mutable.SparsePolynomial::new()
  for w in words {
    counts.add_term_inplace(@mutable.ExponentVector::from_array(w), 1)
  }
  inspect(counts, content="3 * x + 1 * x_1 + 1 * x_1^2")
}

[1] と [1, 0] は同じ単項式なので、xx は 3 回数えられます。

積を項ごとに展開する

test "expansion" {
  let a = @mutable.SparsePolynomial::from_array([([1U], 1), ([0U, 1], 1)])
  let b = @mutable.SparsePolynomial::from_array([([1U], 1), ([0U, 1], -1)])
  let out : @mutable.SparsePolynomial[Int] = @mutable.SparsePolynomial::new()
  for ta in a.to_terms() {
    for tb in b.to_terms() {
      out.add_term_inplace(ta.0 * tb.0, ta.1 * tb.1)
    }
  }
  inspect(out, content="1 * x^2 + -1 * x_1^2")
  assert_true(out == a * b)
}

交差項 xy−xyxy - xy は累積の途中で打ち消し合い、マップに残ることはありません。

項を削除・置換する

test "set and remove" {
  let p = @mutable.SparsePolynomial::from_array([([2U], 4), ([], 1)])
  p.set_coefficient(@mutable.ExponentVector::from_array([2U]), 0)
  inspect(p, content="1")
  p.set_coefficient(@mutable.ExponentVector::from_array([0U, 3]), 7)
  inspect(p, content="1 + 7 * x_1^3")
}

さらに進む

共有のために凍結する

test "freeze" {
  let p = @mutable.SparsePolynomial::from_array([([1U], 2)])
  let frozen = p.to_immut()
  p.add_term_inplace(@mutable.ExponentVector::one(), 9)
  inspect(frozen, content="2 * x")
  inspect(p, content="9 + 2 * x")
}

ジェネリックな累積

MutablePolynomial のコードは、任意のミュータブルなコンテナをリセット・コピーできます:

fn[P : @mutable.MutablePolynomial] reset_copy(p : P) -> P {
  let snapshot = @mutable.Copyable::copy(p)
  @mutable.Clearable::clear(p)
  snapshot
}

test "generic" {
  let p = @mutable.SparsePolynomial::from_array([([1U], 5)])
  let before = reset_copy(p)
  inspect(before, content="5 * x")
  assert_true(p.is_zero())
}

よくある落とし穴

  • copy のコスト. コピーは木を再構築するため、O(mlog⁡m)O(m \log m) です。
  • copy の境界. Eq + AddMonoid な係数が必要です。したがって MutablePolynomial だけを境界とするジェネリックなコードが疎な多項式に対して使えるのは、そのような係数の場合に限られます。
  • 昇順. 表示と to_terms は定数項から始まります。

次のステップ