immut/sparse 设计

设计目标

SparsePolynomial[A] 将多元多项式存储为从单项式到系数的有序映射。当算法询问“ $x^\alpha$ 的系数是多少？”的频率高于遍历整个多项式时，应使用这种表示；它能在对数时间内给出答案，同时保持为不可变值。

数学背景

多项式是一个有限支撑函数 $f : \mathbb{N}^{(\infty)} \to R$ ， $\alpha \mapsto f_\alpha$ （见 core 设计）。其支撑集 $\operatorname{supp} f = \{ \alpha \mid f_\alpha \neq 0 \}$ 是有限的，且 $f$ 由其在支撑集上的限制唯一确定。稀疏多项式恰好存储这个限制，即有限部分映射

\operatorname{supp} f \to R \setminus \{0\}, \qquad \alpha \mapsto f_\alpha ,

因此系数查找就是对该部分映射求值，不存在的键表示 $0$ 。两个多项式相等，当且仅当这两个部分映射相等。

设计决策

以单项式序为键的平衡搜索树

问题。 按指数向量查找需要索引。哈希映射能给出期望 $O(1)$ 的查找，但没有顺序；有序数组能给出 $O(\log m)$ 的查找，但插入为 $O(m)$ 。

选择。 各项存放在 @sorted_map.SortedMap[ExponentVector, A] 中，这是一棵按 ExponentVector::compare 排序的 AVL 树。AVL 树的高度保持在 $1.44 \log_2(m + 2)$ 以下，因此 get 执行 $O(\log m)$ 次键比较，每次比较对向量长度为 $O(\ell)$ 。¹1 Adelson-Velsky 和 Landis，1962。高度上界由高度为 $h$ 的 AVL 树最少节点数所满足的类 Fibonacci 递推式得出。该映射与 TermPolynomial 使用相同的单项式序，因此迭代得到的就是规范项列表，只是这里按升序：常数项在前，首项在后。

这棵树也符合其他操作的代价特征：从 $m$ 个有序项构建它需要 $O(m \log m)$ ，与排序相同。

规范内容：没有零值

不变量。 每个存储的值都非零。构造过程复用项表示的规范化（排序、合并相同的键、丢弃和为零的项），并插入剩余项；neg 和 scale 会跳过与零比较相等的结果，这在存在零因子时可能出现。由于键是规范指数向量且值非零，存储的映射就是 $\operatorname{supp} f$ 上的部分映射 $\alpha \mapsto f_\alpha$ ，并且

\texttt{p == q} \iff \texttt{p.to\_terms() == q.to\_terms()} \iff p = q .

因此 get(α) 返回 None 恰好意味着 $f_\alpha = 0$ 。

通过封装实现不可变性

SortedMap 是可变结构，但持有它的字段是私有的，并且本包中没有任何函数会在多项式返回后修改其映射。每个操作，包括 add_term，都会构建新的映射。这样无需持久化树即可获得值语义，代价是添加单个项要以 $O(m \log m)$ 重建映射。逐项添加的工作负载应使用 mutable/sparse，其 add_term_inplace 以 $O(\log m)$ 更新树。

与项表示共享的算术

加法和乘法收集项列表（对 * 而言是全部 $mn$ 个乘积），并通过共享的规范化重建映射，与 TermPolynomial 完全一样。因此两种表示计算出相同的规范结果，代价也相同，只差树插入的常数因子。eval 是同一个逐项求值同态，具有相同的元数前置条件。

两种多元表示

这两个类型描述相同的多项式，只在访问路径上不同：

操作	`TermPolynomial`	`SparsePolynomial`
$x^\alpha$ 的系数	对 `to_terms()` 做 $O(m)$ 扫描	$O(\log m)$ `get`
首项	第一个元素	最后一个元素
迭代顺序	降序	升序
由 $m$ 个项构建	$O(m \log m)$	$O(m \log m)$
添加一个项（不可变）	通过 `+`， $O(m \log m)$	$O(m \log m)$ `add_term`
`+`, `*`	$O((m+n)\log(m+n))$ , $O(mn\log(mn))$	相同
内存	扁平数组	每项一个树节点

转换通过 to_terms() 进行，这使各实现包相互独立；两者在门面包和 ContextPolynomial 中汇合。

正确性 / 不变量

键是规范的 ExponentVector 值；值非零。
相等比较升序项列表，并与多项式相等一致。
查找。 get(α) == Some(c) 当且仅当 $f_\alpha = c \neq 0$ ；None 当且仅当 $f_\alpha = 0$ 。get_checked 是同一个函数。
一致性。 对相同的输入项，SparsePolynomial 与 TermPolynomial 持有相同的项集，并且 +、-、*、pow、scale 和 eval 的结果一致。
值语义。 没有公开函数会修改已有的 SparsePolynomial。

被否决的替代方案

哈希映射存储。 查找期望为 $O(1)$ ，但迭代顺序是任意的，因此相等、打印和首项都需要排序。
持久化（路径复制）树。 核心库的 @immut/sorted_map 可以使 add_term 无需任何修改即达到 $O(\log m)$ 。本包则把可变的 SortedMap 放在私有字段后面，并把增量构建交给 mutable/sparse。
一个带存储标志的多元类型。 这正是 ContextPolynomial 在内部所做的；在按下标寻址的层次上，两个显式类型能让各自的代价模型在签名中清晰可见。

边界

没有 Compare 或 Hash 实例；稀疏多项式不能用作映射的键。
add_term 不是增量的；它会重建映射。
变量按位置寻址；具名变量和代换属于 ContextPolynomial。
没有除法或 Gröbner 基算法。
指数类型为 UInt，溢出时回绕；系数遵循 A 的语义。

Adelson-Velsky 和 Landis，1962。高度上界由高度为 $h$ 的 AVL 树最少节点数所满足的类 Fibonacci 递推式得出。 ↩