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)")
}

日常任务

统计单项式

把多项式用作单项式的多重集：每出现一次，其系数加一。

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 被计数三次。

逐项展开乘积

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 都从常数项开始。

后续步骤