Оптимизация алгоритма умножения матриц
Я реализовал свою собственную версию алгоритма для умножения двух матриц вместе, и мне нужен кто-то, кто знает, что они делают, чтобы увидеть, есть ли что-нибудь, что можно сделать более оптимальным способом. Я также очень хочу понять, как я могу сделать его надежным, чтобы он не падал, когда в качестве аргумента передаются непрямоугольные матрицы, то есть матрица, которая имеет нечетное количество элементов в разных Vds, которые она содержит.
Меня особенно интересует функция matrixDotв приведенном ниже коде, все остальное - только для того, чтобы показать, как я использую ее в своем проекте).
#include "iostream"
#include <vector>
#define LOG(m) std::cout << m << std::endl
struct Vd
{
std::vector<double> v;
};
struct Md
{
std::vector<Vd> m;
//fill matrix with num
void fill(unsigned const int rows, unsigned const int cols, const double num)
{
m.clear();
for (unsigned int i = 0; i < rows; i++)
{
Vd tempVec;
for (unsigned int j = 0; j < cols; j++)
{
tempVec.v.push_back(num);
}
m.push_back(tempVec);
}
}
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[" << std::endl << std::endl;
for (unsigned int i = 0; i < mat.m.size(); i++)
{
out << "[";
for (unsigned int j = 0; j < mat.m[i].v.size(); j++)
{
if (j % mat.m[i].v.size() == mat.m[i].v.size() - 1)
out << mat.m[i].v[j] << "]" << std::endl << std::endl;
else
out << mat.m[i].v[j] << ", ";
}
}
out << "]" << std::endl;
return out;
}
};
inline void matrixDot(const Md& m1, const Md& m2, Md& outm)
{
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
unsigned int m1x = 0; unsigned int m1y = 0; unsigned int m2y = 0; //m2x = m1y
while (outm.m.size() < m1.m.size())
{
Vd tempv;
while (tempv.v.size() < m2.m[0].v.size())
{
double total = 0.0;
while (m1x < m1.m[0].v.size())
{
total += m1.m[m1y].v[m1x] * m2.m[m1x].v[m2y];
m1x++;
}
tempv.v.push_back(total);
m1x = 0;
m2y < m2.m[0].v.size() - 1 ? m2y++ : m2y = 0;
}
m1y < m1.m.size() - 1 ? m1y++ : m1y = 0;
outm.m.push_back(tempv);
}
}
int main()
{
Md mat1;
mat1.fill(5, 2, 1.0);
Md mat2;
mat2.fill(2, 6, 2.0);
Md mat3;
matrixDot(mat1, mat2, mat3);
std::cout << mat3;
}
Ответы
Я вижу некоторые вещи, которые вы можете использовать для улучшения своего кода.
Используйте usingпри необходимости
Код в настоящее время содержит это:
struct Vd
{
std::vector<double> v;
};
Это, вероятно, лучше выразить так:
using Vd = std::vector<double>;
Итак, вместо того, чтобы писать это:
out << mat.m[i].v[j] << ", ";
Мы можем использовать этот более чистый синтаксис:
out << mat.m[i][j] << ", ";
Понимать заголовки включают пути
Существует тонкое различие между #include "iostream"и #include <iostream>. Хотя эта реализация определена, в большинстве реализаций компилятора форма с кавычками сначала выполняет поиск локально (например, в текущем каталоге), а затем выполняет поиск в системных каталогах, если это не удается. Форма угловой скобки обычно ищет в системных каталогах include. См. Этот вопрос для получения дополнительной информации. По этой причине этот код, вероятно, следует использовать #include <iostream>.
Не используйте, std::endlесли он вам действительно не нужен
Разница между std::endlи '\n'заключается в том, что '\n'просто выдает символ новой строки, а на std::endlсамом деле сбрасывает поток. Это может занять много времени в программе с большим количеством операций ввода-вывода и на самом деле редко требуется. Лучше всего использовать толькоstd::endl тогда, когда у вас есть веская причина для очистки потока, и это не очень часто требуется для простых программ, таких как эта. Избегание привычки использовать std::endlwhen '\n'will do принесет дивиденды в будущем, поскольку вы будете писать более сложные программы с большим количеством операций ввода-вывода и где производительность должна быть максимальной.
При необходимости используйте стандартные функции
Вместо написания , ostream& operator<<как вы едите, аккуратная альтернатива была бы использование std::copyи std::experimental::ostream_joinerтак:
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[\n";
for (const auto& row : mat.m) {
out << "\t[";
std::copy(row.begin(), row.end(), std::experimental::make_ostream_joiner(out, ", "));
out << "]\n";
}
return out << "]\n";
}
Предпочитать возвращаемые значения выходным параметрам
Кажется гораздо более логичным matrixDotвернуть новую матрицу, чем использовать третий параметр в качестве выходного параметра. См. F.20 для более подробной информации.
Рассмотрим альтернативное представление
Этот код несколько хрупок в том смысле, что оба Mdи Vdреализованы как struct, со всеми членами общедоступными. Хуже того, у нас может быть зубчатый массив, в котором каждая строка не имеет одинакового количества элементов. Это, наверное, ни к чему хорошему не приведет. По обеим этим причинам я бы предложил использовать classи один vectorдля хранения всех элементов. См. Этот вопрос для получения некоторых идей и советов о том, как это сделать. Вы также можете рассматривать std::valarrayкак базовый тип.
Обеспечьте реализацию полного класса
В дополнение к конструктору, принимающему std::initializer_listаргументы, я бы также предложил некоторые другие операторы, например, operator==для этого класса.
Должен признаться, я немного сбит с толку, вы сделали сложные части, а есть вопросы по легким? Возможно, я неправильно понял ваш вопрос.
Я также очень хочу понять, как я могу сделать его надежным, чтобы он не падал, когда непрямоугольные матрицы передаются в качестве аргумента, т.е. матрица, которая имеет нечетное количество элементов в разных Vds, которые она содержит.
Вы можете проверить, что у вас есть хорошо сформированная матрица,
inline bool isValid(const Md& mat)
{
if (mat.m.size())
{
int size = mat.m[0].v.size();
for (int i = 1; i < mat.m.size(); i++) {
if (size != mat.m[i].v.size())
{
return false;
}
}
}
return true;
}
и включив его в matrixDotфункцию проверки, аналогичную проверке формы, которая у вас есть прямо сейчас.
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
if (!isValid(m1))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m1;
throw std::exception();
}
if (!isValid(m2))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m2;
throw std::exception();
}
Любые оптимизации, которые я могу придумать, связаны с использованием std::arrayвместо того, std::vectorчтобы знать длину строк и столбцов во время создания.
Лично я бы расширил структуру (класс) Md, чтобы она полностью инкапсулировала матрицу. В нем будут:
-> Переменные-члены для:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Конструктор, позволяющий создать матрицу нужного размера (строки, столбцы).
This would allow you to use vector resize and reserve which will give you
a more performant implementation, especially if the matrices are re-used.
So avoid using push_back and instead set values directly.
-> Получить функции для получения количества строк / столбцов
-> Получить / установить функции для получения / установки значений данных матрицы.
Get/Set functions implement bounds checking.
Затем я бы создал класс mathMatrix, который бы добавил функцию умножения матриц. Это потребует замены большей части прямого доступа к функциям размера / элементам данных и т. Д. На вызовы из приведенного выше, что упростило бы чтение и, следовательно, обслуживание.
Затем, как было предложено ранее, добавление функций isValid или canMultiply поможет сделать решение более надежным.