2

の形式の 2 つの多項式を乗算するための私の方法を次に示しan*x^n + an-1*x^n-1 + ... + a1*x + a0ます。各Termオブジェクトには と の 2 つのフィールドがdouble coefficientありint powerます。Polynomialは項を に格納することにより多項式を表しArrayList<Term>ます。この乗算の現在の実装は O(n^2) です。高速化するためのアイデアやヒントはありますか?

public Polynomial multiply(Polynomial P2) {
    PolynomialImp result = new PolynomialImp();
    for (Term currentThisTerm : this.terms)
    {
        for (Term currentP2Term : ((PolynomialImp) P2).terms)
        {
            result.addTerm(new TermImp(currentThisTerm.getCoefficient()*currentP2Term.getCoefficient(), currentThisTerm.getExponent() + currentP2Term.getExponent()));
        }
    }
    //Sort polynomial in decreasing exponent order
    return result.sort();
}

以下は、必要に応じて addTerm メソッドです。

private void addTerm(Term nextTerm)
{
    for (int i = 0; i < this.terms.size(); i++)
    {
        if (this.terms.get(i).getExponent() == nextTerm.getExponent())
        {
            //Add the coefficients if the current term has the same exponent as a term that is already in the polynomial.
            //This preserves the sorting of the polynomial except during multiply.
            this.terms.set(i, new TermImp(this.terms.get(i).getCoefficient() + nextTerm.getCoefficient(), this.terms.get(i).getExponent()));
            return;
        }
    }
    //Avoid adding zeros to the polynomial.
    if (nextTerm.getCoefficient() != 0)
        this.terms.add(nextTerm);
}
4

3 に答える 3

5

これは、この機能を実装する方法です

public class Polynomial {
    private final double[] coeff;

    public Polynomial(double... coeff) {
        this.coeff = coeff;
    }

    @Override
    public String toString() {
        return Arrays.toString(coeff);
    }

    public Polynomial multiply(Polynomial polynomial) {
        int totalLength = coeff.length + polynomial.coeff.length - 1;
        double[] result = new double[totalLength];
        for (int i = 0; i < coeff.length; i++)
            for (int j = 0; j < polynomial.coeff.length; j++) {
                result[i + j] += coeff[i] * polynomial.coeff[j];
            }
        return new Polynomial(result);
    }

    public static void main(String... args) {
        Polynomial p1 = new Polynomial(1, 2, 3);
        System.out.println(p1 + "^2 =" + p1.multiply(p1));
        Polynomial p2 = new Polynomial(3, -1, -1);
        System.out.println(p1 + "*" + p2 + "=" + p1.multiply(p2));
    }
}

版画

[1.0, 2.0, 3.0]^2 =[1.0, 4.0, 10.0, 12.0, 9.0]
[1.0, 2.0, 3.0]*[3.0, -1.0, -1.0]=[3.0, 5.0, 6.0, -5.0, -3.0]
于 2012-10-04T16:39:16.817 に答える
1

おそらく、このアルゴリズムを遅くしているのは、n^2 個の TermImp オブジェクトを作成しているためです。C++ では、スタック上にオブジェクトを作成して値渡しするため、これは問題になりません。私の理解では、Java にはこのオプションがありません。オブジェクトを作成するオーバーヘッドを受け入れてから参照渡しする必要があります。

項を掛けるたびに新しいオブジェクトを作成するのは効率が悪いようです。それを排除することはできませんでしたか？

係数と指数を double/int 引数として受け入れるように addTerm メソッドを変更することを検討できます。

アルゴリズムは、n が大きい場合でも O(n^2) になりますが、それでも大幅に高速化されるはずです。

イテレータには新しいオブジェクトの作成も含まれるため、イテレータではなくforループを使用することを検討できます...ただし、O(n)はそれほど重要ではありません。

于 2012-10-04T16:48:29.447 に答える
0

重要な非効率性が 1 つあります。順序付けられていないリストのように見えるものに用語を保存します。terms.get(n) が x^n の用語を返すように、コードを変更する必要があります。これにより、addTerm メソッドで terms 変数を検索する必要がなくなります。

これを行うには、用語の順序を維持するために用語を変更するすべてのコードを更新する必要があります。

乗算メソッド自体は効率的に見えますが、これ以上最適化できるとは思いません。

于 2012-10-04T16:33:49.953 に答える