Luna Flow
简体中文

mutable/term 教程

本教程展示如何在一个始终保持有序且规范的可变容器中逐项构建多元多项式，以及何时应改用整体多项式操作。

快速开始

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/mutable",
}
test "mutable term quick start" {
  let p : @mutable.TermPolynomial[Int] = @mutable.TermPolynomial::zero()
  p.add_term_inplace(@mutable.ExponentVector::from_array([1U, 1]), 3)
  p.add_term_inplace(@mutable.ExponentVector::from_array([2U]), 1)
  inspect(p, content="3 * xx_1 + 1 * x^2")
}

容器在每次插入后都会重新排序，因此打印时总是首项在前。

日常任务

在循环中收集项

指数向量相同的项会合并，相消的项会消失：

test "collect" {
  let p : @mutable.TermPolynomial[Int] = @mutable.TermPolynomial::zero()
  for i in 0..<4 {
    p.add_term_inplace(@mutable.ExponentVector::from_array([(i % 2).reinterpret_as_uint()]), 1)
  }
  inspect(p, content="2 * x + 2")
  p.add_term_inplace(@mutable.ExponentVector::one(), -2)
  inspect(p, content="2 * x")
}

原地相乘与缩放

test "multiply" {
  let p = @mutable.TermPolynomial::from_array([([1U], 1), ([0U, 1], 1)])
  p.mul_inplace(p)
  inspect(p, content="1 * x_1^2 + 2 * xx_1 + 1 * x^2")
  p.scale_inplace(@mutable.ExponentVector::from_array([0U, 0, 1]), -1)
  inspect(p.total_degree().unwrap(), content="3")
}

边构建边求值

由于容器始终是规范的，查询在任何时刻都可用：

test "evaluate" {
  let p = @mutable.TermPolynomial::from_array([([2U], 1)])
  inspect(p.eval([3]), content="9")
  p.add_term_inplace(@mutable.ExponentVector::from_array([0U, 1]), 10)
  assert_true(p.eval_checked([3]) is None)
  inspect(p.eval([3, 1]), content="19")
}

加入一个含 x1x_1 的项后，该多项式需要两个值。

深入了解

大规模求和

add_inplace 逐个插入项。对于大的操作数，请一次性构建和：

test "large sums" {
  let parts = Array::makei(50, i => @mutable.TermPolynomial::from_array([([i.reinterpret_as_uint()], 1)]))
  let all_terms : Array[(@mutable.ExponentVector, Int)] = []
  for part in parts {
    for t in part.to_terms() {
      all_terms.push(t)
    }
  }
  let sum = @mutable.TermPolynomial::from_terms(all_terms)
  inspect(sum.size(), content="50")
}

一次 from_terms 以 O(Nlog⁡N)O(N \log N) 规范化所有项。

交给不可变代码

test "freeze" {
  let p = @mutable.TermPolynomial::from_array([([1U], 2)])
  let frozen = p.to_immut()
  p.clear()
  inspect(frozen, content="2 * x")
  assert_true(p.is_zero())
}

常见陷阱

  • add_inplace 的代价。 对大的操作数大致是二次的；见上文。
  • 共享容器。 赋值会共享；如需独立容器，请使用 copy()。
  • 顺序。 与不可变类型相同，该序是分次的，平局在最高变量处决出。

后续步骤