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

逐个添加项

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，或使用 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)
}

(xy+x)2(xy + x)^2 在 (2,3)(2, 3) 处的值为 (6+2)2=64(6 + 2)^2 = 64。eval_checked 返回 None，因为 p 使用了两个变量，而只给出了一个值。

查找首项

映射是升序的，因此首项是最后一个条目：

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)。

后续步骤