mutable/sparse の設計

設計目標

ミュータブルな SparsePolynomial[A] はライブラリのアキュムレータです。項を 1 つずつ対数時間で取り込む多変数多項式であり、項を逐次的に生成するアルゴリズム (積の展開、寄与の集計、データからの多項式の構築) に必要とされます。

数学的背景

コンテナは多項式 $f$ の部分写像 $\operatorname{supp} f \to R \setminus \{0\}$ 、 $\alpha \mapsto f_\alpha$ を保持します (immut/sparse の設計を参照)。項の追加はその写像の点ごとの更新です。

(f + c\,x^\alpha)_\beta = \begin{cases} f_\alpha + c & \beta = \alpha, \\ f_\beta & \beta \neq \alpha, \end{cases}

したがって変化するのはキー $\alpha$ だけで、それが台から外れるのはちょうど $f_\alpha + c = 0$ のときです。

設計上の判断

木の上での点ごとの更新

選択。 set_coefficient と add_term_inplace は上の式を AVL 木の上で直接実装します。1 回の検索の後に挿入、更新、削除のいずれかを行い、それぞれ $O(\log m)$ 回の比較です。「零値を持たない」という不変条件は局所的に維持されます。set_coefficient(α, 0) はキーを削除し、add_term_inplace は和が零になるとキーを削除し、零の増分は無視します。add_inplace(g) はそうした更新を $n$ 回行うもので $O(n \log(m + n))$ です。累積のために mutable/term よりこのコンテナを選ぶ理由はここにあります。

値をその場で更新するので、p.add_inplace(p) も矛盾なく定義されます。反復は各キーを一度だけ訪問し、訪問中のキーの値だけを書き換えるので、結果は $2p$ になります。

多項式全体の演算は委譲する

*、mul_inplace、pow、to_immut はイミュータブルな型を経由し、mul_inplace と scale_inplace は結果を完全に計算してから木をクリアして詰め直します。したがって結果は構成上 immut/sparse と一致し、p.mul_inplace(p) は p を二乗します。

コピーは再構築する

copy は項リストから from_terms を通じて新しい木を再構築し、 $O(m \log m)$ です。これには係数に Eq + AddMonoid が必要なので、この型では Copyable と MutablePolynomial バンドルがその制約を持ちます。copy が制約なしの配列コピーである密および項コンテナとは異なります。

他の多変数コンテナとのコスト比較

演算	`immut/sparse`	`mutable/term`	`mutable/sparse`
項を 1 つ追加	$O(m \log m)$	$O(m \log m)$	$O(\log m)$
$n$ 個の項を追加	$O((m+n)\log(m+n))$	$O(n(m+n)\log(m+n))$	$O(n \log(m+n))$
係数を設定	再構築	利用不可	$O(\log m)$
係数の検索	$O(\log m)$	$O(m)$	$O(\log m)$

正しさ / 不変条件

零値なし、正規形のキー。 すべての変更メソッドによって維持されます。== (昇順の項リストを比較) は多項式の等価性です。
immut との一致: from_immut(a).op(...).to_immut() == a.op(...) であり、インプレース演算はレシーバーを演算子の結果と等しい状態にします。
分離: copy、to_terms、from_immut、to_immut は新しいストレージを構築します。
エイリアシング: 自分自身に対する add_inplace(p) は $2p$ を、自分自身に対する mul_inplace(p) は $p^2$ を与えます。

採用しなかった代替案

ハッシュマップ。 期待 $O(1)$ で更新できますが順序がありません。等価性と表示にソートが必要になり、反復順序もイミュータブルな型と異なってしまいます。
零値を許し、読み出し時にフィルタする。 更新は単純になりますが、size、is_zero、== のすべてで零をスキップする必要が生じます。

境界

copy は $O(m \log m)$ であり、定数時間のスナップショットではありません。
to_terms() を実体化せずに、先頭項から下へ順序どおりに走査する方法はありません。
変数は位置ベースです。名前を使うには mutable/context を使います。
immut/sparse が対象外とするものは、ここでもすべて対象外です。