mutable/term の設計

設計目標

ミュータブルな TermPolynomial[A] は、分配形式の多変数多項式のためのコンテナです。アルゴリズムはこれを段階的に更新でき (項を加える、因子を掛ける、単項式でスケールする)、その間も観測可能なすべての時点で immut/term の正規形のソート済み項配列が保たれます。

数学的背景

コンテナはある $f \in R[x_0, x_1, \dots]$ の正規形の項リストを保持します。すなわち、単項式順序 で $\alpha_1 \succ \alpha_2 \succ \cdots$ を満たし、すべての $c_k \neq 0$ である項 $(\alpha_k, c_k)$ です。インプレース演算は代入です。

$$\begin{aligned} \texttt{add\_term\_inplace}(\alpha, c) &: f \leftarrow f + c\,x^\alpha, \\ \texttt{add\_inplace}(g) &: f \leftarrow f + g, \\ \texttt{mul\_inplace}(g) &: f \leftarrow f g, \\ \texttt{scale\_inplace}(\gamma, c) &: f \leftarrow c\,x^\gamma f . \end{aligned}$$

設計上の判断

配列は置き換え、部分的には編集しない

すべての変更メソッドは完全な正規形の配列を計算してから、それをプライベートフィールドに代入します。読み手が半分だけソートされた状態やマージされていない状態を観測することはなく、エイリアシングも無害です。p.add_inplace(p) では、フィールドが再代入される間もループは古い配列を反復するので $2p$ が得られ、p.mul_inplace(p) は代入の前に $p^2$ を計算します。

単一項の挿入は共有の正規化を再利用する

add_term_inplace は配列のコピーに新しい項を追加し、イミュータブルなコンストラクタで正規化し直します。$O(m \log m)$ です。二分探索の後に挿入またはマージを行えば $O(m)$ (配列のシフトが支配的) で済みますが、正規化のロジックが重複してしまいます。両方のレイヤーで 1 つの正規化ルーチンを使うことを優先しました。

add_inplace(g) は $g$ の項を 1 つずつ挿入するので、$g$ の項数を $n$ とするとコストは $O(n\,(m + n)\log(m + n))$ であり、+ (コピーして add_inplace を呼ぶ) もそのコストを引き継ぎます。これが immut/term との主な性能差で、あちらの + は $O((m+n)\log(m+n))$ で一度だけ正規化します。大きな和の場合は、to_immut で変換してそちらで加算してから戻すか、項リストを組み立てて from_terms を一度だけ呼んでください。

スケーリングは順序を保つ

scale_inplace は $(\alpha, a) \mapsto (\alpha + \gamma, ac)$ と写し、消える積を除去しますが、ソートはしません。イミュータブルな型と同じ論法によります。単項式順序において $\alpha \mapsto \alpha + \gamma$ は狭義単調増加なので、狭義降順の配列は狭義降順のままです (導出)。

積とべきは委譲する

*、mul_inplace、pow は両方のオペランドをイミュータブルな型に変換し、そこで乗算してから戻します。変換のコストはそれぞれ $O(m \log m)$ で、$O(mn \log(mn))$ の積に比べれば小さく、イミュータブルなレイヤーと同じ結果を保証します。

正しさ / 不変条件

• すべての公開呼び出しの後で 正規形 (狭義降順、マージ済み、零なし) です。導出された == は多項式の等価性です。
• immut との一致: すべての演算について from_immut(a).op(...).to_immut() == a.op(...) であり、インプレース演算はレシーバーを対応する演算子の結果と等しい状態にします。
• 分離: copy、to_terms、coefficients、from_immut、to_immut は決してレシーバーと配列を共有しません。
• 計算量: add_term_inplace は $O(m \log m)$、add_inplace と + は $O(n(m+n)\log(m+n))$、mul_inplace と * は $O(mn\log(mn))$、scale_inplace は $O(m)$ です。

採用しなかった代替案

• 遅延正規化 (今は追加だけして、読み出し時にソート): 挿入は安価ですが、すべての問い合わせで正規形を検査または復元しなければならず、== が隠れた状態に依存してしまいます。
• 項のための 連結構造や木構造: それは mutable/sparse が提供するものです。項コンテナは高速な順序付き走査のためにフラットな配列のままにします。

境界

• 指数による係数の検索はありません。mutable/sparse を使ってください。
• add_inplace は大きなオペランド向けには最適化されていません (上記参照)。
• 変数は位置ベースです。名前を使うには mutable/context を使います。
• immut/term が対象外とするものは、ここでもすべて対象外です。