Как предотвратить создание промежуточных объектов в каскадных операторах?

Question

Я использую пользовательский класс Matrix в своем приложении и часто добавляю несколько матриц:

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

Однако это создает промежуточную матрицу для каждой операции сложения. Поскольку это простое добавление, можно избежать промежуточных объектов и создать результат, добавляя элементы всех 4 матриц одновременно. Как мне это сделать?

ПРИМЕЧАНИЕ: я знаю, что могу определить несколько функций, таких как Add3Matrices(a, b, c), Add4Matrices(a, b, c, d) и т. Д., Но я хочу сохранить элегантность result = a + b + c + d.

Answer 1

Вы можете ограничиться одним небольшим промежуточным звеном, используя ленивую оценку. Что-то вроде

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

Нельзя избежать создания промежуточных объектов.

Тем не менее, вы можете использовать шаблоны выражений, как описано здесь , чтобы свести их к минимуму и выполнить ленивую оценку шаблонов.

На самом простом уровне шаблон выражения может быть объектом, который хранит ссылки на несколько матриц и вызывает соответствующую функцию, такую ​​как Add3Matrices (), при назначении. На самом продвинутом уровне шаблоны выражений будут выполнять такие вещи, как ленивый подсчет минимального объема информации по запросу.

Answer 3

То, что, по крайней мере, позволит избежать боли

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

будет

Matrix AddMatrices(Matrix[] matrices)

Answer 4

В C ++ можно использовать Метапрограммы шаблонов , а также здесь , используя шаблоны для этого. Тем не менее, шаблон программирования нетривиален. Я не знаю, доступна ли подобная техника в C #, возможно, нет.

Эта техника в C ++ делает именно то, что вы хотите. Недостатком является то, что если что-то не так, то сообщения об ошибках компилятора, как правило, занимают несколько страниц и их практически невозможно расшифровать.

Без таких методов, я подозреваю, вы ограничены такими функциями, как Add3Matrices.

Но для C # эта ссылка может быть именно тем, что вам нужно: Эффективное матричное программирование в C # , хотя, похоже, она работает немного иначе, чем выражения шаблонов C ++.

Answer 5

Могу ли я предложить MatrixAdder, который ведет себя так же, как StringBuilder. Вы добавляете матрицы в MatrixAdder, а затем вызываете метод ToMatrix (), который сделает для вас дополнения в отложенной реализации. Это даст вам желаемый результат, может быть расширено до любого вида LazyEvaluation, но также не представит каких-либо умных реализаций, которые могут запутать других сопровождающих кода.

Answer 6

Я подумал, что вы можете просто указать желаемое поведение надстройки на месте:

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

Но, как указал Дуг в комментариях к этому сообщению, этот код обрабатывается компилятором так, как если бы я написал:

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

так что временные работы все еще создаются.

Я бы просто удалил этот ответ, но, похоже, другие могут иметь такое же заблуждение, поэтому рассмотрим это контрпример.

Answer 7

Это не самое чистое решение, но если вы знаете порядок оценки, вы можете сделать что-то вроде этого:

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

(или то же самое с разными именами). Затем MatrixCollector реализует + как + =, то есть начинается с 0-матрицы неопределенного размера, принимает размер после вычисления первого + и складывает все вместе (или копирует первую матрицу). Это уменьшает количество промежуточных объектов до 1 (или даже до 0, если вы правильно реализуете присваивание, потому что MatrixCollector может быть / содержать результат немедленно).
Я не совсем уверен, что это ужасно, черт возьми, или один из самых приятных хаков, которые можно сделать. Определенным преимуществом является то, что в некотором роде очевидно, что происходит.

Answer 8

Бьярне Страуструп имеет небольшую статью под названием Абстракция, библиотеки и эффективность в C ++ , где он упоминает методы, используемые для достижения того, что вы ищете. В частности, он упоминает библиотеку Blitz ++ , библиотеку для научных расчетов, которая также имеет эффективные операции с матрицами, а также некоторые другие интересные библиотеки. Также я рекомендую прочитать разговор с Бьярном Страуструпом на artima.com на эту тему.

Answer 9

Есть несколько способов реализовать ленивую оценку для достижения этой цели. Но важно помнить, что не всегда ваш компилятор сможет получить лучший код из всех.

Я уже сделал реализации, которые отлично работали в GCC и даже превзошли производительность традиционного кода «Не читаемый», потому что они заставили компилятор заметить, что между сегментами данных не было псевдонимов (что-то трудно понять с появлением массивов из ниоткуда ). Но некоторые из них были полным провалом в MSVC и наоборот в других реализациях. К сожалению, они слишком длинные, чтобы публиковать их здесь (не думайте, что здесь помещается несколько тысяч строк кода).

Очень сложной библиотекой с большими встроенными знаниями в этой области является библиотека Blitz ++ для научных вычислений.

Answer 10

Моим первым решением было бы что-то вроде этого (добавить в класс 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;
}

У меня было это в классе Matrix, потому что вы можете положиться на закрытые методы и свойства, которые могут быть полезны для вашей функции в случае реализации изменения матрицы (связанный список непустых узлов вместо большого двойного массива) например).

Конечно, вы бы потеряли элегантность result = a + b + c + d. Но у вас было бы что-то вроде result = Matrix.AddMatrices(new Matrix[] { a, b, c, d });.