Ускорение вычислений при перегрузке бинарных операторов

Автор: Ugin

При перегрузке бинарных операторов, создаётся временный объект, что для случаев с матрицей или строкой, может быть достаточно дорого.

Предположим, мы вычисляем сумму матриц:

Matrix a(...);
Matrix b(...);
Matrix c = a + b;

При вычислении этого выражения сначала будет создана временная матрица с суммой a и b, матрице c будет присвоено значение этой временной матрицы, а затем временная матрица будет уничтожена.

Для избежания этого, можно воспользоваться следующим приёмом.

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

class SumMatrix
{
    friend class Matrix;
    const Matrix *a,*b;
    SumMatrix(const Matrix &A, const Matrix &B) : a(&A), b(&B) {}
};

В самом классе матрицы переопределяем следующие операторы:

SumMatrix Matrix::operator+(const Matrix &A, const Matrix &B)
{
    //тут создаётся временный объект и в него копируются указатели
    return SumMatrix(A,B);
}

const Matrix &Matrix::operator = (const SumMatrix &sm)
{
    //здесь надо сложить все члены матриц, используя указатели sm.a и sm.b
    ....
    return *this;
}

Что же теперь произойдёт при вычислении?

Matrix c = a + b;

А вот что: будет создан временный объект типа SumMatrix, и он запомнит указатели на матрицы a и b, матрице c будет присвоено значение этого временного объекта, и менно тут произойдёт сложение исходных матриц, временный объект будет уничтожен.

Только теперь временный объект у нас — не толстая матрица, а легковесный хранитель двух указателей.

При желании можно определять промежуточные классы не для одного бинарного оператора, а для целой серии операторов. Например можно создать промежуточный класс для вычисления выражения A=B+C*D.

Для этого надо создать промежуточный класс, аналогичный классу SumMatrix, для хранения указателей на члены произведения (напр. MultMatrix), и промежуточный класс SumMultMatrix:

class SumMultMatrix
{
    friend class Matrix;
    const Matrix *a;
    const MultMatrix *m;
    SumMultMatrix(const Matrix &A, const MultMatrix &M) : a(&A), m(&M) {}
    SumMultMatrix(const MultMatrix &M, const Matrix &A) : a(&A), m(&M) {}
};

соответственно в классе Matrix надо перегрузить operator=(const SumMultMatrix &sm).

К сожалению, число промежуточных классов растёт очень быстро. Но в случае со строками, можно добиться существенного прироста в скорости относительно небольшими усилиями.

11 июня 2009

Комментарии [79]