Bibliothèque polynomiale utilisant des modèles d'expression

Question

Dans un projet de jouet récent, j'ai fait un usage intensif de calculs impliquant des polynômes dans Z [x]. À titre expérimental, j'ai décidé d'essayer d'implémenter des modèles d'expression - et cela a semblé fournir des accélérations drastiques dans mon cas d'utilisation principal, avec des modifications minimes du code consommateur. (Au cas où il pourrait être utile de voir le contexte dans lequel j'utilise cette bibliothèque, voir:https://github.com/dschepler/groebner-zx .)

Ici, ma principale préoccupation concerne la partie implémentation du modèle d'expression de la bibliothèque. Certaines de mes réflexions actuelles (bien que si ces questions particulières sont trop ouvertes pour fournir de bonnes réponses, c'est juste; d'un autre côté, s'il y a des réponses standard, en particulier pour la question de référence vs. suis toutes les oreilles):

• J'ai choisi ici de capturer des références à des sous-expressions partout; ainsi, par exemple, auto myexpr = 2 * p + q;entraînerait immédiatement des références pendantes à la 2 * psous - expression. Il pourrait également être possible de déplacer-capturer des sous-expressions intermédiaires; bien que cela augmente la complexité de l'implémentation (en particulier, je voudrais toujours éviter de faire des copies d' polynomialexpressions de feuille qui sont des références à des variables existantes).
• Une possibilité à laquelle j'ai pensé serait: fournir une classe spéciale pour les sous-expressions où il est facile de déterminer au moment de la compilation que le résultat de la sous-expression est un monôme; puis cela permettrait de prévoir des implémentations optimisées de multiplication par un monôme. Cela rendrait le code consommateur un peu plus lisible: par exemple, au lieu de p -= 2 * times_x_to(q, 3);le lire p -= 2 * x_to(3) * q;. Mais encore une fois, au prix d'une complexité de mise en œuvre accrue.

Les choses dont je suis conscient, mais qui ne sont pas autant préoccupantes aux fins de cet examen, comprennent:

• Une possibilité de modéliser le type polynomial afin qu'il puisse également être utilisé pour des polynômes sur Q, sur double, sur des réels de précision arbitraire mpfr, etc.
• Choix de représentation interne - en particulier, s'il serait préférable de stocker les coefficients par ordre croissant de degré.

polynomial.h:

#pragma once

#include <gmpxx.h>
#include <initializer_list>
#include <iostream>
#include <string>
#include <vector>

using Z = mpz_class;
inline Z operator""_Z(const char* s)
{
    return operator""_mpz(s);
}

// This is a library for manipulating polynomials with integer
// coefficients.  Note that because the library uses expression
// templates behind the scenes, the following general restrictions
// apply:
//
// * Use of "auto" keyword to initialize a variable with the result
//   of a calculation will generally not work as expected.  Instead,
//   explicitly set the result type to "polynomial".  e.g. instead of
//     auto p = 2 * q + r;
//   write
//     polynomial p = 2 * q + r;
//
// * Assignment expressions aliasing the destination variable will not
//   work as expected.  To work around this, use a polynomial constructor
//   to materialize the intermediate result before assignment.  e.g.
//   instead of
//     p += 2 * times_x_to(p + q, 3);
//   write
//     p += polynomial{2 * times_x_to(p + q, 3)};



// polynomial expression templates: each type should declare a member type
// is_polynomial_expr, and implement methods compatible with:
//    int degree_bound() const;
//      upper bound on degree of the result (does not need to be exact in
//      cases such as sum or difference of two polynomials)
//    Z coefficient(int d) const;
//      return the coefficient of x^d - where d can still be greater than
//      degree_bound()

template <typename CoeffCallable>
class polynomial_expr {
public:
    using is_polynomial_expr = std::true_type;

    polynomial_expr(int degree_bound, CoeffCallable&& coeff_callable)
        : m_degree_bound(degree_bound)
        , m_coeff_callable(std::forward<CoeffCallable>(coeff_callable))
    {
    }
    int degree_bound() const { return m_degree_bound; }
    Z coefficient(int d) const
    {
        return m_coeff_callable(d);
    }

private:
    int m_degree_bound;
    typename std::decay_t<CoeffCallable> m_coeff_callable;
};

template <typename PolyExpr1, typename PolyExpr2,
    typename = typename std::decay_t<PolyExpr1>::is_polynomial_expr,
    typename = typename std::decay_t<PolyExpr2>::is_polynomial_expr>
auto operator+(PolyExpr1&& p, PolyExpr2&& q)
{
    return polynomial_expr {
        std::max(p.degree_bound(), q.degree_bound()),
        [&p, &q](int d) -> Z { return p.coefficient(d) + q.coefficient(d); }
    };
}

template <typename PolyExpr1, typename PolyExpr2,
    typename = typename std::decay_t<PolyExpr1>::is_polynomial_expr,
    typename = typename std::decay_t<PolyExpr2>::is_polynomial_expr>
auto operator-(PolyExpr1&& p, PolyExpr2&& q)
{
    return polynomial_expr {
        std::max(p.degree_bound(), q.degree_bound()),
        [&p, &q](int d) -> Z { return p.coefficient(d) - q.coefficient(d); }
    };
}

template <typename PolyExpr,
    typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
auto operator-(PolyExpr&& p)
{
    return polynomial_expr {
        p.degree_bound(),
        [&p](int d) -> Z { return -(p.coefficient(d)); }
    };
}

template <typename PolyExpr,
    typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
auto operator*(const Z& n, PolyExpr&& p)
{
    return polynomial_expr {
        n == 0 ? -1 : p.degree_bound(),
        [&n, &p](int d) -> Z { return n * p.coefficient(d); }
    };
}

template <typename PolyExpr,
    typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
auto operator*(PolyExpr&& p, const Z& n)
{
    return polynomial_expr {
        n == 0 ? -1 : p.degree_bound(),
        [&n, &p](int d) -> Z { return p.coefficient(d) * n; }
    };
}

class polynomial;
polynomial operator*(const polynomial& p, const polynomial& q);

template <typename PolyExpr,
    typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
auto times_x_to(PolyExpr&& p, int d)
{
    return polynomial_expr {
        p.degree_bound() < 0 ? -1 : p.degree_bound() + d,
        [&p, d](int e) -> Z { return e >= d ? p.coefficient(e - d) : 0; }
    };
}

template <typename PolyExpr1, typename PolyExpr2,
    typename = typename std::decay_t<PolyExpr1>::is_polynomial_expr,
    typename = typename std::decay_t<PolyExpr2>::is_polynomial_expr>
bool operator==(PolyExpr1&& p, PolyExpr2&& q)
{
    auto d = std::max(p.degree_bound(), q.degree_bound());
    for (int i = 0; i <= d; ++i)
        if (p.coefficient(i) != q.coefficient(i))
            return false;
    return true;
}

template <typename PolyExpr1, typename PolyExpr2,
    typename = typename std::decay_t<PolyExpr1>::is_polynomial_expr,
    typename = typename std::decay_t<PolyExpr2>::is_polynomial_expr>
bool operator!=(PolyExpr1&& p, PolyExpr2&& q)
{
    auto d = std::max(p.degree_bound(), q.degree_bound());
    for (int i = 0; i <= d; ++i)
        if (p.coefficient(i) != q.coefficient(i))
            return true;
    return false;
}

class polynomial {
public:
    using is_polynomial_expr = std::true_type;

    polynomial() = default;
    polynomial(std::initializer_list<Z> coeffs);
    explicit polynomial(std::vector<Z> coeffs);

    polynomial(const polynomial&) = default;
    polynomial(polynomial&&) = default;
    template <typename PolyExpr,
        typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
    polynomial(PolyExpr&& p)
    {
        int d = p.degree_bound();
        if (d >= 0) {
            m_coeffs.reserve(d + 1);
            for (; d >= 0; --d)
                m_coeffs.push_back(p.coefficient(d));
            normalize();
        }
    }

    polynomial& operator=(const polynomial&) = default;
    polynomial& operator=(polynomial&&) = default;
    template <typename PolyExpr,
        typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
    polynomial& operator=(PolyExpr&& p)
    {
        auto deg = p.degree_bound();
        m_coeffs.resize(deg + 1);
        for (int d = 0; d <= deg; ++d)
            m_coeffs[deg - d] = p.coefficient(d);
        normalize();
        return *this;
    }

    int degree() const { return m_coeffs.size() - 1; }
    int degree_bound() const { return degree(); }
    const Z& coefficient(int d) const
    {
        static Z static_zero = 0;
        return d > degree() ? static_zero : m_coeffs[degree() - d];
    }

    // leading_coefficient has as a precondition that the polynomial must not be 0
    const Z& leading_coefficient() const
    {
        return m_coeffs.front();
    }

    void negate();

    template <typename PolyExpr,
        typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
    polynomial& operator+=(PolyExpr&& p)
    {
        if (p.degree_bound() > degree())
            m_coeffs.insert(m_coeffs.begin(), p.degree_bound() - degree(), 0);
        for (int d = p.degree_bound(); d >= 0; --d)
            m_coeffs[m_coeffs.size() - d - 1] += p.coefficient(d);
        normalize();
        return *this;
    }
    template <typename PolyExpr,
        typename = typename std::decay_t<PolyExpr>::is_polynomial_expr>
    polynomial& operator-=(PolyExpr&& p)
    {
        if (p.degree_bound() > degree())
            m_coeffs.insert(m_coeffs.begin(), p.degree_bound() - degree(), 0);
        for (int d = p.degree_bound(); d >= 0; --d)
            m_coeffs[m_coeffs.size() - d - 1] -= p.coefficient(d);
        normalize();
        return *this;
    }
    polynomial& operator*=(Z n);
    polynomial& operator*=(const polynomial& p)
    {
        return *this = (*this * p);
    }

    std::string to_string() const;

    friend std::ostream& operator<<(std::ostream& os, const polynomial& p)
    {
        return os << p.to_string();
    }

private:
    std::vector<Z> m_coeffs;

    void normalize();
    static std::string monomial_to_string(const Z& coeff, int d);
};

polynomial.cpp:

#include "polynomial.h"
#include <algorithm>

polynomial::polynomial(std::initializer_list<Z> coeffs)
    : m_coeffs(coeffs)
{
    normalize();
}

polynomial::polynomial(std::vector<Z> coeffs)
    : m_coeffs(std::move(coeffs))
{
    normalize();
}

void polynomial::normalize()
{
    auto first_nonzero = find_if(m_coeffs.begin(), m_coeffs.end(),
        [](const Z& coeff) { return coeff != 0; });
    m_coeffs.erase(m_coeffs.begin(), first_nonzero);
}

void polynomial::negate()
{
    for (auto& coeff : m_coeffs)
        coeff = -coeff;
}

polynomial& polynomial::operator*=(Z n)
{
    if (n == 0)
        m_coeffs.clear();
    else {
        for (Z& coeff : m_coeffs)
            coeff *= n;
    }
    return *this;
}

namespace polynomial_mult_details {

auto evenpart(const polynomial& p)
{
    return polynomial_expr {
        p.degree() / 2,
        [&p](int d) -> const Z& { return p.coefficient(d * 2); }
    };
}

auto oddpart(const polynomial& p)
{
    return polynomial_expr {
        (p.degree() - 1) / 2,
        [&p](int d) -> const Z& { return p.coefficient(d * 2 + 1); }
    };
}

template <typename PolyExpr1, typename PolyExpr2,
    typename = typename PolyExpr1::is_polynomial_expr,
    typename = typename PolyExpr2::is_polynomial_expr>
auto interleave(PolyExpr1&& p, PolyExpr2&& q)
{
    return polynomial_expr {
        std::max(2 * p.degree_bound(), 2 * q.degree_bound() + 1),
        [&p, &q](int d) -> Z {
            if (d % 2 == 0)
                return p.coefficient(d / 2);
            else
                return q.coefficient(d / 2);
        }
    };
}

} // namespace polynomial_mult_details

polynomial operator*(const polynomial& p, const polynomial& q)
{
    // Following the classic recursive algorithm with O(d^lg(3)) multiplications of Z values

    if (p == polynomial {} || q == polynomial {})
        return polynomial {};
    if (p.degree() == 0)
        return p.coefficient(0) * q;
    if (q.degree() == 0)
        return p * q.coefficient(0);

    // In the following, we'll be using each coefficient of p and q
    // multiple times, which is why we have designed the interface to let
    // the caller materialize p and q for us.

    auto pe = polynomial_mult_details::evenpart(p);
    auto po = polynomial_mult_details::oddpart(p);
    auto qe = polynomial_mult_details::evenpart(q);
    auto qo = polynomial_mult_details::oddpart(q);

    polynomial pe_qe = pe * qe;
    polynomial po_qo = po * qo;
    polynomial pepo_qeqo = (pe + po) * (qe + qo);

    return polynomial_mult_details::interleave(
        pe_qe + times_x_to(po_qo, 1),
        pepo_qeqo - pe_qe - po_qo);
}

std::string polynomial::monomial_to_string(const Z& coeff, int d)
{
    std::string result;
    if (coeff == 1 && d > 0)
        result = "";
    else if (coeff == -1 && d > 0)
        result = "-";
    else {
        result = coeff.get_str();
        if (d > 0)
            result += " ";
    }
    if (d == 1)
        result += "x";
    else if (d > 1) {
        result += "x^";
        result += std::to_string(d);
    }
    return result;
}

std::string polynomial::to_string() const
{
    if (m_coeffs.empty())
        return "0";
    std::string result = monomial_to_string(m_coeffs.front(), degree());
    for (int d = degree() - 1; d >= 0; --d) {
        auto coeff = coefficient(d);
        if (coeff > 0) {
            result += " + ";
            result += monomial_to_string(coeff, d);
        } else if (coeff < 0) {
            result += " - ";
            result += monomial_to_string(-coeff, d);
        }
    }

    return result;
}

Et, au cas où il pourrait être utile de voir ma batterie de test actuelle (bien que je sache qu'il manque actuellement des tests pour operator+=,-=,*=): polynomial_test.cpp:

#include "polynomial.h"
#include <gtest/gtest.h>

TEST(Polynomial, Equality)
{
    EXPECT_EQ((polynomial {}), (polynomial {}));
    EXPECT_EQ((polynomial { 0, 0 }), (polynomial {}));
    EXPECT_EQ((polynomial {}), (polynomial { 0, 0 }));
    EXPECT_EQ((polynomial { 1, 2 }), (polynomial { 1, 2 }));
    EXPECT_EQ((polynomial { 0, 1, 2 }), (polynomial { 1, 2 }));
    EXPECT_EQ((polynomial { 1, 2 }), (polynomial { 0, 1, 2 }));
    EXPECT_NE((polynomial { 1, 2 }), (polynomial { 1, 2, 0 }));
}

TEST(Polynomial, Degree)
{
    EXPECT_EQ((polynomial {}.degree()), -1);
    EXPECT_EQ((polynomial { 5 }.degree()), 0);
    EXPECT_EQ((polynomial { 1, 2, 3 }.degree()), 2);
}

TEST(Polynomial, Coefficient)
{
    EXPECT_EQ((polynomial {}.coefficient(0)), 0);
    EXPECT_EQ((polynomial {}.coefficient(1)), 0);
    EXPECT_EQ((polynomial { 5 }.coefficient(0)), 5);
    EXPECT_EQ((polynomial { 5 }.coefficient(1)), 0);
    EXPECT_EQ((polynomial { 5 }.coefficient(2)), 0);
    EXPECT_EQ((polynomial { 1, 2, 3 }.coefficient(0)), 3);
    EXPECT_EQ((polynomial { 1, 2, 3 }.coefficient(1)), 2);
    EXPECT_EQ((polynomial { 1, 2, 3 }.coefficient(2)), 1);
    EXPECT_EQ((polynomial { 1, 2, 3 }.coefficient(3)), 0);
    EXPECT_EQ((polynomial { 1, 2, 3 }.coefficient(4)), 0);
}

TEST(Polynomial, Negate)
{
    EXPECT_EQ((-polynomial {}), (polynomial {}));
    EXPECT_EQ((-polynomial { 1, 2 }), (polynomial { -1, -2 }));
    EXPECT_EQ((-polynomial { 1, -3, -2 }), (polynomial { -1, 3, 2 }));
}

TEST(Polynomial, TimesXTo)
{
    EXPECT_EQ(times_x_to(polynomial {}, 5), (polynomial {}));
    EXPECT_EQ(times_x_to(polynomial { 1, 2, 3 }, 0), (polynomial { 1, 2, 3 }));
    EXPECT_EQ(times_x_to(polynomial { 1, 2, 3 }, 3),
        (polynomial { 1, 2, 3, 0, 0, 0 }));
}

TEST(Polynomial, ScalarMult)
{
    EXPECT_EQ((2 * polynomial {}), (polynomial {}));
    EXPECT_EQ((0 * polynomial { 1, 2, 3 }), (polynomial {}));
    EXPECT_EQ((3 * polynomial { 1, -2, 3 }), (polynomial { 3, -6, 9 }));
    EXPECT_EQ((-3 * polynomial { 1, -2, 3 }), (polynomial { -3, 6, -9 }));
}

TEST(Polynomial, Add)
{
    EXPECT_EQ((polynomial {} + polynomial {}), (polynomial {}));
    EXPECT_EQ((polynomial { 1, 2, 3 } + polynomial {}), (polynomial { 1, 2, 3 }));
    EXPECT_EQ((polynomial {} + polynomial { 1, 2, 3 }), (polynomial { 1, 2, 3 }));
    EXPECT_EQ((polynomial { 1, 2, 3 } + polynomial { 1, 2, 3 }), (polynomial { 2, 4, 6 }));
    EXPECT_EQ((polynomial { 1, 2, 3 } + polynomial { -1, -2, -3 }), (polynomial {}));
    EXPECT_EQ((polynomial { 1, 2, 3, 4 } + polynomial { -1, -2, 5, 6 }),
        (polynomial { 8, 10 }));
    EXPECT_EQ((polynomial { 1, 2, 3, 4 } + polynomial { 5, 6 }),
        (polynomial { 1, 2, 8, 10 }));
    EXPECT_EQ((polynomial { 5, 6 } + polynomial { 1, 2, 3, 4 }),
        (polynomial { 1, 2, 8, 10 }));
}

TEST(Polynomial, Subtract)
{
    EXPECT_EQ((polynomial {} - polynomial {}), (polynomial {}));
    EXPECT_EQ((polynomial { 1, 2, 3 } - polynomial {}), (polynomial { 1, 2, 3 }));
    EXPECT_EQ((polynomial {} - polynomial { 1, 2, 3 }), (polynomial { -1, -2, -3 }));
    EXPECT_EQ((polynomial { 1, 2, 3 } - polynomial { 1, 2, 3 }), (polynomial {}));
    EXPECT_EQ((polynomial { 1, 2, 3, 4 } - polynomial { 1, 2, 5, 6 }),
        (polynomial { -2, -2 }));
    EXPECT_EQ((polynomial { 1, 2, 3, 4 } - polynomial { 5, 6 }),
        (polynomial { 1, 2, -2, -2 }));
    EXPECT_EQ((polynomial { 5, 6 } - polynomial { 1, 2, 3, 4 }),
        (polynomial { -1, -2, 2, 2 }));
}

TEST(Polynomial, Multiply)
{
    EXPECT_EQ((polynomial {} * polynomial {}), (polynomial {}));
    EXPECT_EQ((polynomial {} * polynomial { 1, 2, 3 }), (polynomial {}));
    EXPECT_EQ((polynomial { 1, 2, 3 } * polynomial {}), (polynomial {}));
    EXPECT_EQ((polynomial { 2 } * polynomial { 1, 2, 3 }), (polynomial { 2, 4, 6 }));
    EXPECT_EQ((polynomial { 1, 2, 3 } * polynomial { 2 }), (polynomial { 2, 4, 6 }));
    EXPECT_EQ((polynomial { 1, 5 } * polynomial { 1, 6 }), (polynomial { 1, 11, 30 }));
    EXPECT_EQ((polynomial { 1, 2 } * polynomial { 1, -2 }), (polynomial { 1, 0, -4 }));
    EXPECT_EQ((polynomial { 1, 1, 1, 1, 1 } * polynomial { 1, 1, 1 }), (polynomial { 1, 2, 3, 3, 3, 2, 1 }));
}

TEST(Polynomial, ExprTemplates)
{
    polynomial p { 2, 3, 4 };
    polynomial q { 5, 6 };
    EXPECT_EQ(p * q - p, p * (q - polynomial { 1 }));
    EXPECT_EQ(p + q + p, 2 * p + q);
    EXPECT_EQ(3 * p + 4 * times_x_to(q, 2), (polynomial { 20, 30, 9, 12 }));
    EXPECT_EQ(5 * p - 2 * times_x_to(q, 1), (polynomial { 3, 20 }));
}

TEST(Polynomial, ToString)
{
    EXPECT_EQ((polynomial {}.to_string()), "0");
    EXPECT_EQ((polynomial { 13 }.to_string()), "13");
    EXPECT_EQ((polynomial { -3 }.to_string()), "-3");
    EXPECT_EQ((polynomial { 1, 0 }.to_string()), "x");
    EXPECT_EQ((polynomial { 1, 4 }.to_string()), "x + 4");
    EXPECT_EQ((polynomial { 1, -4 }.to_string()), "x - 4");
    EXPECT_EQ((polynomial { 2, 3 }.to_string()), "2 x + 3");
    EXPECT_EQ((polynomial { -2, -3 }.to_string()), "-2 x - 3");
    EXPECT_EQ((polynomial { -1, 5 }.to_string()), "-x + 5");
    EXPECT_EQ((polynomial { 1, 3, 2 }.to_string()), "x^2 + 3 x + 2");
    EXPECT_EQ((polynomial { 1, 0, -3, 0, 0, 1, 5 }.to_string()), "x^6 - 3 x^4 + x + 5");
    EXPECT_EQ((polynomial { -1, 0, 0, 0 }.to_string()), "-x^3");
    EXPECT_EQ((polynomial { 1, 0, 1 }.to_string()), "x^2 + 1");
    EXPECT_EQ((polynomial { 1, 0, -1 }.to_string()), "x^2 - 1");
    EXPECT_EQ((polynomial { -1 }.to_string()), "-1");
}

Answer 1

Considérez le principe du moindre étonnement

À moins que vous ne connaissiez les détails d'implémentation de vos classes, il est difficile de comprendre pourquoi ce qui suit fonctionne:

std::cout << polynomial{1} << "\n";

Mais cela ne:

std::cout << polynomial{1} + polynomial{2} << "\n";

Vous avez déjà expliqué pourquoi, mais devoir se souvenir de cela et envelopper l'expression dans une autre expression polynomial{}est frustrant et fastidieux. Certains utilisateurs, lorsqu'ils sont confrontés à quelque chose comme ça, ajouteront polynomial{}autour de tout, même s'ils n'en ont pas besoin, et tout avantage en termes de performances sera perdu.

Vous devez faire en sorte que l'interface publique suive le principe du moindre étonnement et qu'elle fonctionne exactement comme vous vous attendez à ce que les expressions régulières fonctionnent, dans la mesure du possible. La performance devrait être une préoccupation secondaire ici. Cependant, cela ne signifie pas que vous ne devriez pas avoir polynomial_exprdu tout. Cela signifie cependant que vous devriez essayer de:

• Se polynomialrendre plus efficace, ou
• Faire polynomial_exprs implicitement cast polynomiallà où c'est nécessaire, ou
• Fournissez des surcharges pour polynomial_exprque cela se comporte comme polynomial.

Par exemple, je peux faire la deuxième déclaration que j'ai écrite ci-dessus compiler et exécuter en ajoutant:

template <typename CoeffCallable>
class polynomial_expr {
    ...
    friend std::ostream &operator<<(const std::ostream &out, const polynomial_expr &expr);
};

... // after definition of class polynomial:

template <typename CoeffCallable>
std::ostream &operator<<(std::ostream &out, const polynomial_expr<CoeffCallable> &expr)
{
    return out << polynomial{expr};
}

Pourquoi polynomial_exprs sont-ils plus rapides que polynomials?

Je pense que la raison pour laquelle le retour de polynomial_exprs est plus rapide est que vous évitez de construire un nouveau polynomialavec le résultat, ce qui implique de construire un std::vectoravec les coefficients. Étant donné que cela nécessite une allocation de mémoire, ce qui a des effets secondaires et peut changer le comportement si, par exemple, le global operator newest surchargé, les compilateurs pourraient ne pas être en mesure de l'optimiser, même s'ils peuvent voir que le résultat polynomiallui-même n'est qu'un temporaire.

Mais les utilisateurs C ++ sont habitués à ce type de problème de performances; c'est pourquoi nous modifions souvent les conteneurs sur place par exemple. Donc au lieu d'écrire:

polynomial p1, p2, p3 = ...;
polynomial result = p1 + p2 * p3;

Si vous savez que vous n'avez plus besoin de conserver les valeurs d'origine, vous pouvez écrire:

polynomial p1, p2, p3 = ...;
p1 += p2 *= p3;

Bien que cela ne remporte aucun concours de beauté non plus, c'est au moins moins surprenant, et c'est une façon pour un utilisateur soucieux de la performance d'obtenir du code haute performance avec seulement votre polynomialclasse.

Faire polynomialaller plus vite

Comme je l'ai mentionné précédemment, le fait que cela polynomialutilise un std::vectormoyen dont il a besoin pour faire des allocations de mémoire de tas. Envisagez d'utiliser un autre conteneur pour stocker les coefficients qui implémentent une petite optimisation vectorielle .

De plus, vous avez déjà mentionné faire des monômes un cas particulier. Je pense que c'est une bonne idée, mais vous pouvez peut-être généraliser cette optimisation et faire en sorte que vous ne stockiez que les coefficients entre le coefficient non nul le plus élevé et le plus bas. Par exemple, faites en sorte que le polynôme \$x^{102} + x^{101} + x^{100}\$ne stocke que trois coefficients. L'implémentation peut être aussi simple que d'ajouter une variable membre à class polynomialqui stocke le décalage au coefficient différent de zéro le plus bas. Bien sûr, cela peut signifier un peu plus de travail ici et là, mais certaines opérations en bénéficieront grandement. Par exemple, multiplier ou diviser par un monôme unitaire sera trivial.

Rendre encore plus simple d'utilisation

Vous avez déjà mentionné que ce x_to()serait un moyen court et agréable d'écrire un monôme. Encore plus court serait X(), mais comme il s'agit d'un nom très court, vous voudrez probablement le mettre dans un espace de noms, pour éviter de polluer l'espace de noms global, et pour que les utilisateurs puissent y adhérer:

namespace polynomial_utilities {
polynomial_expr X(int d = 1) {
    return {d, [&p, d](int e) -> Z { return int(e == d); }};
}
}

...

using polynomial_utilies::X;
auto expr = 3 * X(2) - 5 * X() + 4;

Vous pouvez également créer dun paramètre de modèle pour utiliser des chevrons.

Ajouter un moyen d'évaluer un polynomialà un point donné

C'est très bien que vous puissiez construire des polynômes et les imprimer, mais généralement vous voudrez évaluer le polynôme à un point donné. J'ajouterais donc un operator()()pour faire ceci:

class polynomial {
    ...
    template<typename T>
    T operator()(T x) {
        T result{0};
        T multiplier{1};

        for (auto &coeff: m_coeffs) {
            result += coeff * multiplier;
            multiplier *= x;
        }

        return result;
    }
}

Vous pouvez donc écrire:

polynomial func{3, -5, 4};
std::cout << func(1.5) << "\n"; // should print: 3.25