По долгу службы пришлось реализовывать много больших алгоритмов на матрицах. С незапамятных времён написал свой класс вроде
template<typename T> struct Matrix { T &Get(size_t row, size_t column) { return data[column + row * width]; } private: std::vector<T> data; size_t width, height; }
Matrix m = m1 + m2 * 2.0f + m3; //выделять память для всех трёх промежуточных результатов? ну уж нет.
Matrix m1, m2, m3; //заполняем матрицы (( m2 *= 2.0f) += m1) += m3;
for(int i = ...) for( int j = ...) m2.Get( i, j) = m2.Get( i, j) * 2.0f + m1.Get( i, j) + m3.Get( i, j);
Для рабочих проектов я использую eigen и понимаю, что в нём все эти проблемы в принципе решены, но во-первых, он просто гигантский. Во-вторых, мне не нравится их философия, где слишком много решается за программиста под капотом где-то внутри перегруженных операторов. Иногда он может посчитать, что надо создавать промежуточные матрицы, иногда — нет. Конечно, это всё в принципе настраивается и контролируется, но вся эта логика раздувает библиотеку до умопомрачительных размеров. Для домашних проэктов я хотел что-то предельно простое, лишённое всех вышеописанных недостатков и обмазанное всевозможным синтаксическим сахаром, чтоб пользоваться было приятно.
Так родилась моя либа со 100% overhead-free отложенными вычислениями. Например, код из предыдущего примера записывается так:
Matrix matrix1, matrix2, matrix3; //заполняем //берём proxy-объекты, каждый из которых не содержит данных кроме ссылки на свою матрицу и служит для хранения структуры математических выражений auto m1 = matrix1.GetProxy(); auto m2 = matrix2.GetProxy( ); auto m3 = matrix3.GetProxy( ); //в таком подходе код будет часто совпадать с псевдокодом m2 = m1 + m2 * 2.0f + m3;
res.GetRow(0).GetTransposed( ) = ( m3 * m1).GetColumn( 3);
Было бы очень интересно взглянуть, если кто-то ещё из местных писал подобный велосипед. Ещё было бы очень интересно, как подобное можно реализовать на других языках программирования, потому что, как мне кажется, именно подобные задачи, связанные со сложным overhead-free синтаксическим сахаром наиболее удачно ложатся на C++.
Suslik
> именно подобные задачи, связанные со сложным overhead-free синтаксическим
> сахаром наиболее удачно ложатся на C++.
Да, С++ в этом месте рулит. Можно круто решить все в одну строку. А бонусом идет то, что сторонний человек глядя в этот код будет думать: "Что за говно здесь творится?".
И вот он например код, где по auto мне приехала какая то неведомая фигня, а потом хрясь хрясь, и с ней происходит снова неведомая фигня:
res.GetRow(0).GetTransposed( ) = ( m3 * m1).GetColumn( 3);
Suslik
> Ещё было бы очень интересно, как подобное можно реализовать на других языках
> программирования
Быстрым гуглением готовую либу с таким функционалом на rust не нашёл, но кажется, что его можно реализовать без проблем. Например там в стандартной либе есть итераторы с ленивыми преобразованиями, которые разворачиваются в без-оверхедный код.
Move конструкторы чем не подходят?
Фишка с получением третьем строки произведения впечатляет.
Но если все-таки надо умножать большие матрицы целиком, то их же быстрее не в лоб а тем хитрым рекурсивным алгоритмом из blas?
Suslik
Когда то, лет семь назад, делал такое. Кода конечно не осталось. Как оно называется и реализуется наверное пол часа вспоминал - никак.
В итоге пришлось лезть в гугл. Называется expression templates. Вот накидал пример:
http://rextester.com/BKFR72853
Основная идея - CRTP и типы на каждую операцию.
PS. Если какие косяки относительно возможностей новых стандартов, то извините, я из шаблонного "мейнстрима" выбыл еще до появления C++11.
старая шаблонная трава https://github.com/highwatt/lazymatrix
kipar
> то их же быстрее не в лоб а тем хитрым рекурсивным алгоритмом из blas?
Я бы вообще лямбду потипа for_each зафигачил для матрицы, и никаких бы прокси не изобретал. Вот это: res.GetRow(0).GetTransposed() = (m3 * m1).GetColumn(3); как по мне - слишком сложно, и нужно знать дофига инфы по конкретно этой библиотеке. Как-то так имхо проще.
for_each_row(res, 0, [&m3, &m1]( int col) { res[0][col] = m3[col][3] * m1[col][3]; });
Не матрицы и не lazy, но пусть будет
http://rextester.com/OLX73513
https://godbolt.org/g/8JTAsD
Хотел предложить expression templates, но уже предложили. Ну а так подход Суслика с view норм. Это вью называется. Для строк даже в новый стандарт завезли. Вариант с лямбдами называют комбинаторным и он не торт, ибо не читабилен. С экспрессион темплейтс можно проводить предварительные оптимизации во время компиляции. Всякие преобразования или предвычисления констант, даже посчитать обратную матрицу от константы во время компиляции. Но хоть это и торт, но компиляться будет часами даже с отключенной оптимизацией, подобных вышеописанных. Ну и отлаживать не удобно. Про мув не слушай. Чувак тебя не понял. Мув даёт экономию по памяти, но не даёт леаниризации вычислений. В общем твой вариант с вью идеален. Читается на ура даже вариант с транспонированной колонкой. Потребление памяти и линеаризация - отличные. Короче никого здесь не слушай. Все правильно сделал. Мне понравилось Пости ссылку на суслиб на гикхабе.
return [](){};
> Не матрицы и не lazy, но пусть будет
Ухты. Круто компилятор соптимизировал. Жаль только что assert который в default он не проверяет в компайлтайме. А то сейчас можно написать auto v2 = v1.wzya; и скомпилировать, а упадет оно только в рантайме.
*Lain*
> Вариант с лямбдами называют комбинаторным и он не торт, ибо не читабилен
Только сейчас понял, что у меня кстати вариант с лямбдами неправильный. Ибо там перемножение матриц, строка на столбец, все дела. И такое лямбдами выйдет монстроуозно. Так что признаю, библиотека вполне годная.
Тоже ссылку на гитхаб хочу. :)
MrShoor
> Ибо там перемножение матриц, строка на столбец, все дела.
Ну вот мне и непонятно. Для одной строки ок. Но для больших матриц рекурсивный алгоритм со сложностью O(n^2.8) будет сильно быстрее влобного умножения за O(n^3), а на view этот алгоритм по-моему не ложится никак (или ложится?).
А если перемножение убрать, то остается только суммирование и умножение на скаляр, возможно транспонирование - по-моему там можно исхитриться и придумать что-то без этих expression templatов, для частного случая этих трех операций. Ну, я исключительно с позиции завистника сужу.
kipar
> а на view этот алгоритм по-моему не ложится никак (или ложится?).
вот поэтому код интересно посмотреть
MrShoor
http://rextester.com/DPGKD71973
Тема в архиве.