（効果的に）多項式を動的に格納する

Question

私が達成しようとしているのは、配列を使って多項式の未知のサイズを格納することです。 私はインターネット上で見たことは、各セルにcoeffecientが含まれており、次数がセル番号であるという配列を使用していますが、それは効果的ではありません。なぜなら、6x^14 + x + 5のような多項式があるからです。これは、1から13までのすべてのセルに0を持たせることを意味します。すでにベクトルとリンクされたリストを持ついくつかのソリューションを見ていますが、この問題に効果的に取り組む他の方法はありません（std :: vectorsまたはstd ：：リスト）？

Answer 1

ゼロの要素が存在しないキーによって表されるマップでスパース多項式を表すことができます。このようなクラスの例を次に示します。

#include <map> 

//example of sparse integer polynomial 
class SparsePolynomial{ 
    std::map<int,int> coeff; 
    int& operator[](const int& degree); 
    int get(int degree); 
    void update(int degree, int val); 
}; 

要素の係数を取得または更新しようとするたびに、マップの存在が評価されます。要素の係数が更新されるたびに、値がゼロかどうかがチェックされます。したがって、マップのサイズは常に最小限に抑えることができます。

これら2つの方法をoperator[]に置き換えることができます。しかし、この場合、更新操作中にゼロをチェックすることができないため、アクセスと更新のために2つの別々のメソッドを使用するのと同じくらい効率的ではありません。

int SparsePolynomial::get(int degree){ 
    if (coeff.find(degree) == coeff.end()){ 
     return 0; 
    }else{ 
     return coeff[degree]; 
    } 
} 

void SparsePolynomial::update(int degree, int val){ 
    if (val == 0){ 
     std::map<int,int>::iterator it = coeff.find(degree); 
     if (it!=coeff.end()){ 
      coeff.erase(it); 
     } 
    }else{ 
     coeff[degree]=val; 
    } 
} 

この方法では、より効率的な記憶域が得られますが、アクセスと更新にはベクターよりも時間がかかります。しかし、疎な多項式の場合、その差は小さくてもよい。サイズNのstd::mapが与えられた場合、要素の平均検索複雑度はO(log N)となります。度がd、非ゼロ係数の数がNのスパース多項式があるとします。 Nがdよりもはるかに小さい場合、アクセスと更新の時間は十分に小さく通知されません。

Answer 2

別の方法で実行する必要がある魅力的な理由がない限り（これはCスタイルの配列を使用する必要があるプログラミング割り当てです）、標準ライブラリのstd::vectorを使用してください。図書館には、あなたの人生を楽にする理由があります。オーバーヘッドはおそらくあなたのプログラムの文脈では重要ではありません。

[-1, 1, 0, 0, 0, 4]などのインデックスを持つstd::vectorに多項式（4 * x^5 + x - 1など）を格納するのは非効率的です。これは当てはまりますが、1000を超える次数の多項式を格納しない限り、この無駄はほとんどありません。高度は低いが係数は少ない「疎」多項式の場合、各ペアの最初の値には電力が格納され、2番目の値には係数が格納されたペアのベクトルを使用することを検討できます。