скалярное произведение вектора ‹ вектора ‹ int › › по первому измерению

У меня есть

vector < vector < int > > data_mat ( 3, vector < int > (4) );
vector          < int >   data_vec ( 3                     ); 

где data_mat можно рассматривать как матрицу, а data_vec как вектор-столбец, и я ищу способ вычислить внутренний продукт каждого столбца data_mat с data_vec и сохранить его в другом vector < int > data_out (4).

Пример http://liveworkspace.org/code/2bW3X5%241 с использованием for_each и transform может использоваться для вычисления суммы столбцов матрицы:

sum=vector<int> (data_mat[0].size());
for_each(data_mat.begin(), data_mat.end(),
         [&](const std::vector<int>& c) {
            std::transform(c.begin(), c.end(), sum.begin(), sum.begin(),
                           [](int d1, double d2) 
                             { return d1 + d2; }
                          );
            }
        );

Возможно ли аналогичным образом (или немного другим способом, использующим функции STL) вычислять точечные произведения столбцов матрицы с вектором?

Проблема в том, что трюк 'd2 = d1 + d2' не работает здесь в случае внутреннего продукта столбца - если есть способ включить d3, который решит эту проблему ( d3 = d3 + d1 * d2 ), но тернарные функции, похоже, не существуют в transform.


person alle_meije    schedule 04.03.2013    source источник
comment
inner_product?   -  person Peter Wood    schedule 05.03.2013
comment
Npte, если вы хотите заняться серьезной математикой, то, вероятно, пришло время отказаться от stl и использовать библиотеку C, например ГСЛ. Меня удивляет, что stl даже может заниматься такими вещами, разница в скорости, вероятно, составляет 2 полных порядка...   -  person Matt Phillips    schedule 05.03.2013
comment
Я не уверен, что понимаю, чего вы пытаетесь достичь. Вы говорите о скалярных произведениях, но я не вижу здесь умножения.   -  person Andy Prowl    schedule 05.03.2013
comment
У меня нет кода для скалярного произведения, как объясняется в тексте ниже примера кода для суммы столбцов (см. умножение в тексте). Насколько я знаю, нет способа сделать { d3 + d1 * d2; } в преобразовании.   -  person alle_meije    schedule 05.03.2013
comment
Что ж, не нужно обращаться ни к какой библиотеке C, нет проблем с STL, но Matt по крайней мере прав в том, что если вы хотите заняться серьезной математикой, то, по крайней мере, отбросьте этот ужасно неуместный вектор векторов. и использовать правильную матричную структуру данных (в которой внутренние данные хранятся непрерывно). Кто бы ни сказал вам, что динамические массивы динамических массивов являются хорошим способом представления двумерных массивов, явно ошибается. Тем не менее, все еще интересный вопрос.   -  person Christian Rau    schedule 05.03.2013
comment
Пункт принят и понят @ChristianRau! Честно говоря, это часть доказательства концепции для других об использовании STL и того факта, что вы можете, если вы абсолютно настаиваете, использовать эти итераторы практически для чего угодно. Я застрял с этим, но мне интересно, можно ли это сделать. Самый простой способ сделать матрицы, я думаю, это stackoverflow.com/questions/12657811, который я буду использовать исключительно после демонстрации безнадежного неэффективный / неподходящий / инертный / и т. д. способ.   -  person alle_meije    schedule 06.03.2013
comment
@alle_meije На самом деле вы можете использовать алгоритмы стандартной библиотеки с любой структурой данных, которая вам нравится, не обязательно только со стандартными контейнерами, или позволить матричной структуре данных, оптимизированной для хранения/разметки, предоставить свои собственные итераторы для использования со стандартными алгоритмами. Это просто vector<vector> вздор, а не общий подход transform или <algorithm>. И, как уже было сказано, идея решения таких задач, как та, что в вопросе, только с помощью алгоритмов STL, действительно хороша, даже если в данном конкретном случае имеет только теоретическое значение.   -  person Christian Rau    schedule 06.03.2013
comment
@alle_meije О твоей награде: я показываю только ту, что сейчас здесь. Вы можете наградить его в ближайшее время, если хотите. На этот вопрос нет предварительной награды. Спасибо!   -  person Andrew Barber    schedule 24.04.2013


Ответы (1)


На самом деле вы можете использовать существующий подход к сумме столбцов почти один к одному. Вам не нужен троичный std::transform в качестве внутреннего цикла, потому что коэффициент, с которым вы масштабируете строки матрицы перед их суммированием, является постоянным для каждой строки, поскольку это значение строки из вектора-столбца, которое повторяется вместе со строками матрицы и, таким образом, внешний std::for_each.

Итак, что нам нужно сделать, это перебрать строки матрицы и умножить каждую полную строку на соответствующее значение в векторе-столбце и добавить эту масштабированную строку к вектору суммы. Но, к сожалению, для этого нам понадобится функция std::for_each, которая одновременно перебирает два диапазона, строки матрицы и строки вектора-столбца. Для этого мы могли бы использовать обычный унарный std::for_each и просто выполнить итерацию по вектору-столбцу вручную, используя дополнительный итератор:

std::vector<int> sum(data_mat[0].size());
auto vec_iter = data_vec.begin();
std::for_each(data_mat.begin(), data_mat.end(), 
              [&](const std::vector<int>& row) {
                 int vec_value = *vec_iter++;    //manually advance vector row
                 std::transform(row.begin(), row.end(), sum.begin(), sum.begin(),
                                [=](int a, int b) { return a*vec_value + b; });
              });

Дополнительная ручная итерация внутри std::for_each на самом деле не является идиоматическим использованием алгоритмов стандартной библиотеки, но, к сожалению, нет бинарного std::for_each, который мы могли бы использовать.


Другим вариантом было бы использовать std::transform в качестве внешнего цикла (который может выполнять итерацию по двум диапазонам), но на самом деле мы не вычисляем одно значение в каждой внешней итерации для возврата, поэтому нам нужно будет просто вернуть какое-то фиктивное значение из внешней лямбды. и выбросьте его, используя какой-нибудь фиктивный итератор вывода. Это тоже было бы не самым чистым решением:

//output iterator that just discards any output
struct discard_iterator : std::iterator<std::output_iterator_tag,
                                        void, void, void, void>
{
    discard_iterator& operator*() { return *this; }
    discard_iterator& operator++() { return *this; }
    discard_iterator& operator++(int) { return *this; }
    template<typename T> discard_iterator& operator=(T&&) { return *this; }
};

//iterate over rows of matrix and vector, misusing transform as binary for_each
std::vector<int> sum(data_mat[0].size());
std::transform(data_mat.begin(), data_mat.end(), 
               data_vec.begin(), discard_iterator(), 
               [&](const std::vector<int>& row, int vec_value) {
                   return std::transform(row.begin(), row.end(), 
                                         sum.begin(), sum.begin(),
                                         [=](int a, int b) { 
                                             return a*vec_value + b;
                                         });
               });

EDIT: Хотя это уже обсуждалось в комментариях, и я понимаю (и ценю) теоретическую природу вопроса, я все же включу предположение, что на практике динамический массив динамических массивов — это ужасный способ для представления такого структурно четко определенного двумерного массива, как матрица. Правильная матричная структура данных (которая хранит свое содержимое непрерывно) с соответствующими операторами почти всегда является лучшим выбором. Но, тем не менее, из-за их универсальности вы все равно можете использовать стандартные алгоритмы библиотеки для работы с такой пользовательской структурой данных (возможно, даже позволив матричному типу предоставлять свои собственные итераторы).

person Christian Rau    schedule 06.03.2013
comment
Спасибо! Я не думал о создании дополнительного вектора и доступе к нему «изнутри». В приложении, которое я хочу продемонстрировать, строки — это пронумерованные изображения, а столбцы — индексы пикселей — в этом случае все не так уж плохо, потому что большие блоки все еще являются смежными. Даже в этом случае верно то, что если вы знаете о своих данных достаточно, чтобы определить внутренние продукты, структуры данных, которые извлекают выгоду из таких знаний, всегда более эффективны. - person alle_meije; 06.03.2013
comment
@alle_meije Да, это не имеет смысла. Но подождите, я его переделаю, в конце концов нам нужен даже не временный вектор, а бинарник for_each. - person Christian Rau; 23.04.2013
comment
@alle_meije Хорошо, обновил ответ. Тот факт, что std::for_each не может перебирать два диапазона одновременно, не позволяет получить полностью чистое и оптимизированное решение STL, но освобождает нас от необходимости в дополнительном временном векторе, который использовался в моем первом (неправильном) решении. - person Christian Rau; 23.04.2013
comment
Это гениально! Спасибо, Кристиан, мне втайне нравится вид ручного вмешательства в «официальный» итератор :). - person alle_meije; 25.04.2013
comment
это программа, в которой я использую код: github.com /amwink/bias/blob/master/cpp/fastecm/fastecm.cpp - person alle_meije; 18.11.2014