immut/sparse API

Luna-Flow/luna-poly/immut/sparse は、ExponentVector から非ゼロ係数への順序付きマップとして格納されるイミュータブルな多変数多項式 SparsePolynomial[A] を提供します。TermPolynomial と同じ多項式を表しますが、単一の係数を対数時間で検索できます。

この型は immut ファサードから @immut.SparsePolynomial として再エクスポートされており、例ではそれを使います。変数はインデックスで指定します。設計は immut/sparse の設計で説明しています。

型

`SparsePolynomial`

SparsePolynomial[A] は $c_\alpha \neq 0$ である各指数ベクトル $\alpha$ を $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`

定数 $1$ を返します。A において $1 = 0$ の場合はゼロ多項式を返します。One::one() でもあります。

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

`SparsePolynomial::from_terms`

項のリストから多項式を構築します。等しい指数ベクトルの係数は加算され、和がゼロになったものは取り除かれます。入力はコピーされます。コストは $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^\alpha$ を加えた新しい多項式を返します。係数がゼロになった場合はそのキーが削除されます。レシーバは変更されません。マップ全体が再構築されるため、コストは $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^\alpha$ の係数を返します。項が存在しない(係数がゼロである)場合は None を返します。コストは $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 \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`

$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^\gamma \cdot p$ を返します。ゼロになる積は取り除かれます。

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

`SparsePolynomial::pow`

二分累乗法で $p^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] は変数 $i$ の値で、少なくとも 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)`

immut/sparse API

型

SparsePolynomial

構築

SparsePolynomial::new, SparsePolynomial::zero

SparsePolynomial::one

SparsePolynomial::from_terms

SparsePolynomial::from_array

SparsePolynomial::add_term

問い合わせ

SparsePolynomial::get

SparsePolynomial::get_checked

SparsePolynomial::to_terms

SparsePolynomial::size, SparsePolynomial::term_count

SparsePolynomial::is_empty, SparsePolynomial::is_zero

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