Comment empêcher la création d'objets intermédiaires dans des opérateurs en cascade?

Question

J'utilise une classe Matrix personnalisée dans mon application et j'ajoute fréquemment plusieurs matrices:

Matrix result = a + b + c + d; // a, b, c and d are also Matrices

Cependant, cela crée une matrice intermédiaire pour chaque opération d’addition. Comme il s’agit d’une addition simple, il est possible d’éviter les objets intermédiaires et de créer le résultat en ajoutant les éléments des 4 matrices à la fois. Comment puis-je accomplir cela?

REMARQUE: je sais que je peux définir plusieurs fonctions telles que Add3Matrices (a, b, c) , Add4Matrices (a, b, c, d) , etc., mais Je veux conserver l'élégance de resultat = a + b + c + d .

Answer 1

Vous pouvez vous limiter à un seul petit intermédiaire en utilisant une évaluation paresseuse. Quelque chose comme

public class LazyMatrix
{
    public static implicit operator Matrix(LazyMatrix l)
    {
        Matrix m = new Matrix();
        foreach (Matrix x in l.Pending)
        {
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    m.Contents[i, j] += x.Contents[i, j];
        }

        return m;
    }

    public List<Matrix> Pending = new List<Matrix>();
}

public class Matrix
{
    public int[,] Contents = { { 0, 0 }, { 0, 0 } };

    public static LazyMatrix operator+(Matrix a, Matrix b)
    {
        LazyMatrix l = new LazyMatrix();
        l.Pending.Add(a);
        l.Pending.Add(b);
        return l;
    }

    public static LazyMatrix operator+(Matrix a, LazyMatrix b)
    {
        b.Pending.Add(a);
        return b;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Matrix a = new Matrix();
        Matrix b = new Matrix();
        Matrix c = new Matrix();
        Matrix d = new Matrix();

        a.Contents[0, 0] = 1;
        b.Contents[1, 0] = 4;
        c.Contents[0, 1] = 9;
        d.Contents[1, 1] = 16;

        Matrix m = a + b + c + d;

        for (int i = 0; i < 2; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                System.Console.Write(m.Contents[i, j]);
                System.Console.Write("  ");
            }
            System.Console.WriteLine();
        }

        System.Console.ReadLine();
    }
}

Answer 2

Quelque chose qui éviterait au moins la douleur de

Matrix Add3Matrices(a,b,c) //and so on 

serait

Matrix AddMatrices(Matrix[] matrices)

Answer 3

En C ++, il est possible d'utiliser les Métaprogrammes de modèles ainsi que ici , en utilisant des modèles pour faire exactement cela. Cependant, la programmation des modèles n’est pas triviale. Je ne sais pas si une technique similaire est disponible en C #, très probablement pas.

Cette technique, en c ++, fait exactement ce que vous voulez. L'inconvénient est que si quelque chose ne va pas, les messages d'erreur du compilateur ont tendance à s'étendre sur plusieurs pages et sont presque impossibles à déchiffrer.

Sans ces techniques, je suppose que vous êtes limité à des fonctions telles que Add3Matrices.

Mais pour C #, ce lien peut être exactement ce dont vous avez besoin: Programmation matricielle efficace en C # bien que cela semble fonctionner légèrement différemment des expressions de modèles C ++.

Answer 4

Vous ne pouvez pas éviter de créer des objets intermédiaires.

Cependant, vous pouvez utiliser les modèles d’expression tels que décrits ici pour les minimiser et faire une évaluation paresseuse des modèles.

Au niveau le plus simple, le modèle d’expression peut être un objet qui stocke les références à plusieurs matrices et appelle une fonction appropriée telle que Add3Matrices () lors de l’affectation. Au niveau le plus avancé, les modèles d’expression permettent, entre autres, de calculer la quantité minimale d’informations de manière informelle, à la demande.

Answer 5

Ce n'est pas la solution la plus propre, mais si vous connaissez l'ordre d'évaluation, vous pourriez faire quelque chose comme ceci:

result = MatrixAdditionCollector() << a + b + c + d

(ou la même chose avec des noms différents). MatrixCollector implémente ensuite + as + =, c'est-à-dire commence par une matrice 0 de taille indéfinie, prend une taille une fois que le premier + est évalué et ajoute le tout (ou copie la première matrice). Cela réduit le nombre d'objets intermédiaires à 1 (voire à 0 si vous implémentez correctement l'affectation, car MatrixCollector pourrait être / contenir le résultat immédiatement.)

Je ne suis pas tout à fait sûr que ce soit aussi laid que l'enfer ou l'un des plus beaux bidouilles qu'on pourrait faire. Un avantage certain est que ce qui se passe est assez évident.

Answer 6

Puis-je suggérer un MatrixAdder qui se comporte beaucoup comme un StringBuilder. Vous ajoutez des matrices à MatrixAdder, puis appelez une méthode ToMatrix () qui effectuerait les ajouts pour vous dans une implémentation paresseuse. Cela vous donnerait le résultat souhaité, pourrait être étendu à n’importe quel type d’évaluation LazyEvaluation, mais n’introduirait pas non plus d’implémentations intelligentes susceptibles de dérouter les autres responsables du code.

Answer 7

Je pensais que vous pouviez simplement expliciter le comportement de complément souhaité:

Matrix result = a;
result += b;
result += c;
result += d;

Mais comme l'a souligné Doug dans les Commentaires de ce message, ce code est traité par le compilateur comme si j'avais écrit:

Matrix result = a;
result = result + b;
result = result + c;
result = result + d;

ainsi, les temporaires sont toujours créés.

Je voudrais juste supprimer cette réponse, mais il semble que d'autres pourraient avoir la même idée fausse, alors considérez ceci comme un contre-exemple.

Answer 8

Bjarne Stroustrup a rédigé un court article intitulé Abstraction, bibliothèques et efficacité en C ++ où il mentionne les techniques utilisées pour réaliser ce que vous recherchez. Plus précisément, il mentionne la bibliothèque Blitz ++ , une bibliothèque de calculs scientifiques qui permet également des opérations efficaces sur les matrices, avec quelques autres bibliothèques intéressantes. Je vous recommande également de lire une conversation avec Bjarne Stroustrup sur artima.com à ce sujet.

Answer 9

Il n'est pas possible d'utiliser des opérateurs.

Answer 10

Ma première solution serait de suivre cette ligne (à ajouter si possible à la classe Matrix):

static Matrix AddMatrices(Matrix[] lMatrices) // or List<Matrix> lMatrices
{
    // Check consistency of matrices

    Matrix m = new Matrix(n, p);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            foreach (Maxtrix mat in lMatrices)
                m[i, j] += mat[i, j];

    return m;
}

Je l'avais dans la classe Matrix parce que vous pouvez compter sur les méthodes et propriétés privées qui pourraient être utiles pour votre fonction en cas de changement de matrice (liste chaînée de noeuds non vides au lieu d'un grand tableau double) par exemple).

Bien sûr, vous perdriez l'élégance de result = a + b + c + d . Mais vous auriez quelque chose du genre result = Matrix.AddMatrices (nouvelle Matrix [] {a, b, c, d}); .

Answer 11

Il existe plusieurs façons de mettre en œuvre une évaluation paresseuse pour y parvenir. Mais il est important de se rappeler que votre compilateur ne pourra pas toujours obtenir le meilleur code.

J'ai déjà réalisé des implémentations qui fonctionnaient très bien dans GCC et surpassaient même les performances du code traditionnel illisible, car elles amènent le compilateur à remarquer qu'il n'y avait pas d'alias entre les segments de données (quelque chose de difficile à saisir avec des tableaux venant de nulle part). ). Mais certains de ceux-ci ont été un échec complet à MSVC et vice versa sur d'autres implémentations. Malheureusement, ceux-ci sont trop longs à publier ici (ne pensez pas que plusieurs milliers de lignes de code conviennent ici).

Une bibliothèque très complexe avec de grandes connaissances intégrées est la bibliothèque Blitz ++ pour le calcul scientifique.