Luna Flow
简体中文

immut/sparse API

Luna-Flow/luna-poly/immut/sparse 提供 SparsePolynomial[A]，即存储为从 ExponentVector 到非零系数的有序映射的不可变多变量多项式。它描述的多项式与 TermPolynomial 相同，但支持以对数时间查找单个系数。

该类型由 immut 门面包以 @immut.SparsePolynomial 重新导出，示例即使用该形式。变量按下标寻址。设计说明见 immut/sparse 设计。

类型

SparsePolynomial

SparsePolynomial[A] 把每个满足 cα≠0c_\alpha \neq 0 的指数向量 α\alpha 映射到 cαc_\alpha。键按单项式序排序，映射按升序迭代。

type SparsePolynomial[A] derive(@debug.Debug)
pub impl[A : Eq] Eq for SparsePolynomial[A]
pub impl[A] @luna-generic.Zero for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + @luna-generic.One] @luna-generic.One for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] Add for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Neg] Sub for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul] Mul for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + Neg] Neg for SparsePolynomial[A]
pub impl[A : Show + @luna-generic.Zero] Show for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] @arithmetic.PowNatChecked for SparsePolynomial[A]
pub impl[A] @core.HasArity for SparsePolynomial[A]
pub impl[A] @core.HasShape for SparsePolynomial[A]
pub impl[A] @core.HasTermCount for SparsePolynomial[A]
pub impl[A] @core.HasTotalDegree for SparsePolynomial[A]
pub impl[A] @core.IsZero for SparsePolynomial[A]
pub impl[A] @core.MultivariatePolynomial for SparsePolynomial[A]

构造

SparsePolynomial::new, SparsePolynomial::zero

两者都返回空映射，即零多项式；zero 也是 Zero::zero()。

pub fn[A] SparsePolynomial::new() -> Self[A]
pub fn[A] SparsePolynomial::zero() -> Self[A]

SparsePolynomial::one

返回常数 11；若在 A 中 1=01 = 0，则返回零多项式；也是 One::one()。

pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] SparsePolynomial::one() -> Self[A]

SparsePolynomial::from_terms

由项列表构造多项式，将指数向量相等的项的系数相加，并丢弃和为零的项。输入会被复制。开销为 O(mlog⁡m)O(m \log m) 次比较。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_terms(Array[(@core.ExponentVector, A)]) -> Self[A]

SparsePolynomial::from_array

与 from_terms 相同，但每个指数向量以 Array[UInt] 给出。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_array(Array[(Array[UInt], A)]) -> Self[A]

SparsePolynomial::add_term

返回加上 c xαc\,x^\alpha 后的新多项式；系数变为零时删除该键。接收者保持不变。整个映射会被重建，因此开销为 O(mlog⁡m)O(m \log m)。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add_term(Self[A], @core.ExponentVector, A) -> Self[A]
test "construction" {
  let p = @immut.SparsePolynomial::from_array([([2U], 1), ([1U], 2), ([], 1), ([1U, 0], -2)])
  inspect(p, content="1 + 1 * x^2")
  let q = p.add_term(@immut.ExponentVector::from_array([2U]), -1)
  inspect(q, content="1")
  inspect(p, content="1 + 1 * x^2")
}

查询

SparsePolynomial::get

返回 xαx^\alpha 的系数；若该项不存在（其系数为零），则返回 None。开销为 O(log⁡m)O(\log m) 次比较。

pub fn[A] SparsePolynomial::get(Self[A], @core.ExponentVector) -> A?

SparsePolynomial::get_checked

与 get 相同。每个指数向量都是合法的键，因此没有额外的失败情形；这个名字只是为了与其他带检查的 API 保持对称。

pub fn[A] SparsePolynomial::get_checked(Self[A], @core.ExponentVector) -> A?

SparsePolynomial::to_terms

以单项式序升序返回各项组成的新数组，常数项（如有）在前。这与 TermPolynomial::to_terms 的顺序相反。

pub fn[A] SparsePolynomial::to_terms(Self[A]) -> Array[(@core.ExponentVector, A)]

SparsePolynomial::size, SparsePolynomial::term_count

两者都返回存储的（非零）项数。

pub fn[A] SparsePolynomial::size(Self[A]) -> Int
pub fn[A] SparsePolynomial::term_count(Self[A]) -> Int

SparsePolynomial::is_empty, SparsePolynomial::is_zero

两者对零多项式都返回 true。

pub fn[A] SparsePolynomial::is_empty(Self[A]) -> Bool
pub fn[A] SparsePolynomial::is_zero(Self[A]) -> Bool

SparsePolynomial::arity, SparsePolynomial::total_degree, SparsePolynomial::shape

使用中的变量个数、最大的项次数（零多项式为 None），以及 PolynomialShape::Multivariate(arity~, term_count~)。

pub fn[A] SparsePolynomial::arity(Self[A]) -> Int
pub fn[A] SparsePolynomial::total_degree(Self[A]) -> UInt?
pub fn[A] SparsePolynomial::shape(Self[A]) -> @core.PolynomialShape
test "queries" {
  let p = @immut.SparsePolynomial::from_array([([1U, 1], 3), ([2U], 1), ([], 4)])
  debug_inspect(p.get(@immut.ExponentVector::from_array([1U, 1])), content="Some(3)")
  debug_inspect(p.get(@immut.ExponentVector::from_array([0U, 2])), content="None")
  inspect(p.to_terms().map(t => t.0.to_string()).join(", "), content="1, x^2, xx_1")
  inspect(p.arity(), content="2")
  debug_inspect(p.total_degree(), content="Some(2)")
}

算术

SparsePolynomial::add, SparsePolynomial::sub, SparsePolynomial::neg

运算符 +、- 和一元 -。加法收集两个项列表并重建映射，开销为 O((m+n)log⁡(m+n))O((m+n)\log(m+n))；取负为 O(mlog⁡m)O(m \log m) 次映射插入。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Neg] SparsePolynomial::sub(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Neg] SparsePolynomial::neg(Self[A]) -> Self[A]

SparsePolynomial::mul

构造全部 mnmn 个项的乘积并重建映射，即运算符 *。开销为 O(mnlog⁡(mn))O(mn \log(mn))。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] SparsePolynomial::mul(Self[A], Self[A]) -> Self[A]

SparsePolynomial::scale

返回 c xγ⋅pc\,x^\gamma \cdot p，丢弃为零的乘积。

pub fn[A : Eq + @luna-generic.Zero + Mul] SparsePolynomial::scale(Self[A], @core.ExponentVector, A) -> Self[A]

SparsePolynomial::pow

通过二进制幂算法返回 pep^e；pow(0) 为 one()。也可通过 @arithmetic.PowNatChecked 使用。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::pow(Self[A], UInt) -> Self[A]
test "arithmetic" {
  let p = @immut.SparsePolynomial::from_array([([1U], 1), ([0U, 1], -1)])
  inspect(p.pow(2), content="1 * x^2 + -2 * xx_1 + 1 * x_1^2")
  inspect(p - p, content="0")
  inspect(p.scale(@immut.ExponentVector::from_array([1U]), 2), content="2 * x^2 + -2 * xx_1")
}

求值

SparsePolynomial::eval, SparsePolynomial::eval_checked

在 values 处求值，其中 values[i] 是变量 ii 的取值；至少需要 arity() 个值。数组过短时，eval 中止（abort），eval_checked 返回 None。

pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::eval(Self[A], Array[A]) -> A
pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::eval_checked(Self[A], Array[A]) -> A?
test "evaluation" {
  let p = @immut.SparsePolynomial::from_array([([2U], 1), ([1U], 2), ([], 1)])
  inspect(p.eval([2]), content="9")
  assert_true(@immut.SparsePolynomial::from_array([([0U, 1], 1)]).eval_checked([1]) is None)
}

比较与打印

SparsePolynomial::equal

比较项列表，即多项式相等。它就是 ==。

pub fn[A : Eq] SparsePolynomial::equal(Self[A], Self[A]) -> Bool

SparsePolynomial::to_string

按升序把各项渲染为 c * monomial（常数项只写 c），以 + 连接；零多项式打印为系数零。

pub fn[A : Show + @luna-generic.Zero] SparsePolynomial::to_string(Self[A]) -> String

泛型访问

SparsePolynomial::ops

返回该类型的 MultivariateOps 记录；eval_indexed 即 eval。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::ops() -> @core.MultivariateOps[Self[A], A]
test "ops" {
  let ops = @immut.SparsePolynomial::ops()
  let p = ops.add(ops.one(), ops.from_terms([(@immut.ExponentVector::from_array([0U, 1]), 3)]))
  inspect(ops.eval_indexed(p, [0, 2]), content="7")
}

转换为项存储

经由项列表转换：TermPolynomial::from_terms(sparse.to_terms())。转换会重新排序为降序。

已弃用

为源码兼容而保留的隐藏方法形式：

已弃用替代方案
p.not_equal(q)p != q
p.output(logger)to_string 或字符串插值
p.to_repr()Repr(p) 或 debug_inspect
p.pow_nat_checked(e, ctx)@arithmetic.PowNatChecked::pow_nat_checked(p, e, ctx) 或 p.pow(e)