Luna Flow
日本語

mutable/sparse API

Luna-Flow/luna-poly/mutable/sparse はミュータブルな SparsePolynomial[A] を提供します。immut/sparse と同様に ExponentVector から非零係数への順序付きマップであり、マップをその場で対数時間で更新するメソッドを備えます。

この型は mutable ファサードによって @mutable.SparsePolynomial として再エクスポートされており、例ではこちらを使います。「immut と同様」とは、immut/sparse API の意味、制約、コストを指します。変更のモデルは mutable/sparse の設計 で説明しています。

型

SparsePolynomial

指数ベクトルから非零係数へのミュータブルなマップで、単項式順序の昇順に反復されます。

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.Clearable for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] @core.Copyable 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]
pub impl[A : Eq + @luna-generic.AddMonoid] @core.MutablePolynomial for SparsePolynomial[A]

ここでは Copyable と MutablePolynomial は Eq + AddMonoid 係数を必要とします。copy が from_terms を通じてマップを再構築するためです。

構築と変換

SparsePolynomial::new, SparsePolynomial::zero, SparsePolynomial::one, SparsePolynomial::from_terms, SparsePolynomial::from_array

多項式を構築します (immut と同様)。

pub fn[A] SparsePolynomial::new() -> Self[A]
pub fn[A] SparsePolynomial::zero() -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] SparsePolynomial::one() -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_terms(Array[(@core.ExponentVector, A)]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_array(Array[(Array[UInt], A)]) -> Self[A]

SparsePolynomial::from_immut, SparsePolynomial::to_immut

イミュータブルな型との相互変換です。どちらも新しいマップを構築します。

pub fn[A] SparsePolynomial::from_immut(@Luna-Flow/luna-poly/immut/sparse.SparsePolynomial[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::to_immut(Self[A]) -> @Luna-Flow/luna-poly/immut/sparse.SparsePolynomial[A]

SparsePolynomial::copy

独立したコピーを返します (Copyable::copy でも可)。O(mlog⁡m)O(m \log m) です。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::copy(Self[A]) -> Self[A]

問い合わせ

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

immut と同様です。get は O(log⁡m)O(\log m) の検索で、存在しない (零の) 項には None を返します。to_terms は昇順の新しい配列を返します。

pub fn[A] SparsePolynomial::get(Self[A], @core.ExponentVector) -> A?
pub fn[A] SparsePolynomial::get_checked(Self[A], @core.ExponentVector) -> A?
pub fn[A] SparsePolynomial::to_terms(Self[A]) -> Array[(@core.ExponentVector, A)]
pub fn[A] SparsePolynomial::size(Self[A]) -> Int
pub fn[A] SparsePolynomial::term_count(Self[A]) -> Int
pub fn[A] SparsePolynomial::is_empty(Self[A]) -> Bool
pub fn[A] SparsePolynomial::is_zero(Self[A]) -> Bool
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

変更

SparsePolynomial::set_coefficient

xαx^\alpha の係数を設定します。零に設定するとそのキーは削除されます。O(log⁡m)O(\log m) です。

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

SparsePolynomial::add_term_inplace

c xαc\,x^\alpha を加えます。新しいキーを挿入するか、既存の係数に加算し、和が零になればキーを削除します。cc が零なら何もしません。O(log⁡m)O(\log m) です。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add_term_inplace(Self[A], @core.ExponentVector, A) -> Unit

SparsePolynomial::add_inplace

other のすべての項を add_term_inplace で加えます。O(nlog⁡(m+n))O(n \log(m + n)) です。p.add_inplace(p) は p を 2 倍にします。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add_inplace(Self[A], Self[A]) -> Unit

SparsePolynomial::mul_inplace

内容を self * other で置き換えます。積を先に計算するため、p.mul_inplace(p) は p を二乗します。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] SparsePolynomial::mul_inplace(Self[A], Self[A]) -> Unit

SparsePolynomial::scale_inplace

内容を c xγ⋅pc\,x^\gamma \cdot p で置き換えます。

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

SparsePolynomial::clear

すべての項を削除します (Clearable::clear でも可)。

pub fn[A] SparsePolynomial::clear(Self[A]) -> Unit
test "mutation" {
  let x = @mutable.ExponentVector::from_array([1U])
  let p : @mutable.SparsePolynomial[Int] = @mutable.SparsePolynomial::new()
  p.set_coefficient(x, 3)
  p.add_term_inplace(x, -1)
  debug_inspect(p.get(x), content="Some(2)")
  p.add_term_inplace(@mutable.ExponentVector::one(), 5)
  p.add_inplace(p)
  inspect(p, content="10 + 4 * x")
  p.set_coefficient(x, 0)
  inspect(p, content="10")
  p.clear()
  assert_true(p.is_empty())
}

非破壊的な演算

SparsePolynomial::add, SparsePolynomial::sub, SparsePolynomial::mul, SparsePolynomial::neg, SparsePolynomial::scale, SparsePolynomial::pow

新しい多項式を返す演算子と算術メソッドです (immut と同様)。+ はレシーバーをコピーして add_inplace を呼び出します。

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.AddMonoid + Mul] SparsePolynomial::mul(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Neg] SparsePolynomial::neg(Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Mul] SparsePolynomial::scale(Self[A], @core.ExponentVector, A) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::pow(Self[A], UInt) -> Self[A]

SparsePolynomial::eval, SparsePolynomial::eval_checked, SparsePolynomial::equal, SparsePolynomial::to_string, SparsePolynomial::ops

評価、等価性、表示、および MultivariateOps レコードです (immut と同様)。

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?
pub fn[A : Eq] SparsePolynomial::equal(Self[A], Self[A]) -> Bool
pub fn[A : Show + @luna-generic.Zero] SparsePolynomial::to_string(Self[A]) -> String
pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::ops() -> @core.MultivariateOps[Self[A], A]
test "non-mutating" {
  let p = @mutable.SparsePolynomial::from_array([([1U], 1), ([], 1)])
  let q = p * p
  inspect(q, content="1 + 2 * x + 1 * x^2")
  inspect(p, content="1 + 1 * x")
  inspect(q.eval([2]), content="9")
}

非推奨

ソース互換性のために残されている、隠されたメソッド形式:

非推奨代替
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)