Поговорим об отложенных(ленивых) вычислениях
Suslik | Модератор | www | 26 окт. 2017 | 17:54 | #0 |
---|
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 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 отложенными вычислениями. Например, код из предыдущего примера записывается так:
Этот код развернётся на этапе компиляции в точно такой же код, как и в случае с ручными циклами. Обратите внимание, что в моём решении явно разделены понятия матрицы и её Proxy. Матрица содержит в себе, собственно, данные и создаётся только вручную. Операции над матрицами напрямую производить нельзя. Ни при каких обстоятельствах в промежуточных вычислениях не может случайно выделиться несколько сотен мегов памяти на здоровенную матрицу. А вот под Proxy я понимаю как раз промежуточные компайлтайм объекты, которые при присвоении резолвятся, преобразуются в единственный цикл по всем элементам и уже в нём записывают результат куда надо за один проход. Моей любимой фишкой этого подхода является то, что можно брать Proxy не на всю матрицу, а на её отдельные подматрицы. Например, такой код:res.GetRow(0).GetTransposed() = (m3 * m1).GetColumn(3);
Было бы очень интересно взглянуть, если кто-то ещё из местных писал подобный велосипед. Ещё было бы очень интересно, как подобное можно реализовать на других языках программирования, потому что, как мне кажется, именно подобные задачи, связанные со сложным overhead-free синтаксическим сахаром наиболее удачно ложатся на C++.
Правка: 26 окт. 2017 18:27
MrShoor | Участник | www | 26 окт. 2017 | 18:55 | #1 |
---|
> именно подобные задачи, связанные со сложным overhead-free синтаксическим
> сахаром наиболее удачно ложатся на C++.
Да, С++ в этом месте рулит. Можно круто решить все в одну строку. А бонусом идет то, что сторонний человек глядя в этот код будет думать: "Что за говно здесь творится?".
И вот он например код, где по auto мне приехала какая то неведомая фигня, а потом хрясь хрясь, и с ней происходит снова неведомая фигня:
res.GetRow(0).GetTransposed() = (m3 * m1).GetColumn(3);
Собственно из-за этого недостатка данная проблема практически никак не решается в других ЯП.
Alexander K | Постоялец | www | 26 окт. 2017 | 19:04 | #2 |
---|
> Ещё было бы очень интересно, как подобное можно реализовать на других языках
> программирования
Быстрым гуглением готовую либу с таким функционалом на rust не нашёл, но кажется, что его можно реализовать без проблем. Например там в стандартной либе есть итераторы с ленивыми преобразованиями, которые разворачиваются в без-оверхедный код.
cast.reinterpret | Постоялец | www | 26 окт. 2017 | 21:22 | #3 |
---|
Правка: 26 окт. 2017 21:23
kipar | Постоялец | www | 26 окт. 2017 | 21:35 | #4 |
---|
Но если все-таки надо умножать большие матрицы целиком, то их же быстрее не в лоб а тем хитрым рекурсивным алгоритмом из blas?
Ghost2 | Постоялец | www | 26 окт. 2017 | 21:38 | #5 |
---|
Когда то, лет семь назад, делал такое. Кода конечно не осталось. Как оно называется и реализуется наверное пол часа вспоминал - никак.
В итоге пришлось лезть в гугл. Называется expression templates. Вот накидал пример:
http://rextester.com/BKFR72853
Основная идея - CRTP и типы на каждую операцию.
PS. Если какие косяки относительно возможностей новых стандартов, то извините, я из шаблонного "мейнстрима" выбыл еще до появления C++11.
Правка: 26 окт. 2017 21:41
eagle | Постоялец | www | 26 окт. 2017 | 21:50 | #6 |
---|
MrShoor | Участник | www | 26 окт. 2017 | 21:54 | #7 |
---|
> то их же быстрее не в лоб а тем хитрым рекурсивным алгоритмом из 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]; });
Опять же непонятно как оно будет инлайнится в случае с лямбдой, и нужно тестировать производительность.
Ну и справедливости ради библиотека суслика может быть полезна в некоторых случаях, например когда с матрицами надо работать очень много.
return [](){}; | Участник | www | 26 окт. 2017 | 22:44 | #8 |
---|
*Lain* | Пользователь | www | 26 окт. 2017 | 23:04 | #9 |
---|
Правка: 26 окт. 2017 23:06
MrShoor | Участник | www | 26 окт. 2017 | 23:06 | #10 |
---|
> Не матрицы и не lazy, но пусть будет
Ухты. Круто компилятор соптимизировал. Жаль только что assert который в default он не проверяет в компайлтайме. А то сейчас можно написать auto v2 = v1.wzya; и скомпилировать, а упадет оно только в рантайме.
MrShoor | Участник | www | 26 окт. 2017 | 23:14 | #11 |
---|
> Вариант с лямбдами называют комбинаторным и он не торт, ибо не читабилен
Только сейчас понял, что у меня кстати вариант с лямбдами неправильный. Ибо там перемножение матриц, строка на столбец, все дела. И такое лямбдами выйдет монстроуозно. Так что признаю, библиотека вполне годная.
Тоже ссылку на гитхаб хочу. :)
kipar | Постоялец | www | 26 окт. 2017 | 23:22 | #12 |
---|
> Ибо там перемножение матриц, строка на столбец, все дела.
Ну вот мне и непонятно. Для одной строки ок. Но для больших матриц рекурсивный алгоритм со сложностью O(n^2.8) будет сильно быстрее влобного умножения за O(n^3), а на view этот алгоритм по-моему не ложится никак (или ложится?).
А если перемножение убрать, то остается только суммирование и умножение на скаляр, возможно транспонирование - по-моему там можно исхитриться и придумать что-то без этих expression templatов, для частного случая этих трех операций. Ну, я исключительно с позиции завистника сужу.
MrShoor | Участник | www | 26 окт. 2017 | 23:43 | #13 |
---|
> а на view этот алгоритм по-моему не ложится никак (или ложится?).
вот поэтому код интересно посмотреть
return [](){}; | Участник | www | 26 окт. 2017 | 23:44 | #14 |
---|
http://rextester.com/DPGKD71973
/ Форум / Программирование игр / Общее