Как использовать std :: накапливать для аккуратного суммирования значений в векторе, обозначенном отдельно определенными индексами (заменяя циклы)
Мне было интересно, если есть более точный (или еще лучше, более эффективный) метод суммирования значений векторной / (асимметричной) матрицы (матрица, имеющая структуру, подобную симметрии), конечно, может быть использована в цикле, но не так ли у меня вопрос) указывается совокупностью показателей. По сути, этот код можно использовать, например, для расчета стоимости маршрута через 2D-матрицу. Я ищу способ использовать процессор, а не графический процессор.
Вот некоторый соответствующий код, тот, который меня больше интересует, это первый случай. Я думал, что можно использовать std::accumulate с лямбдой для захвата вектора индексов, но потом мне стало интересно, есть ли более аккуратный путь, возможно, с каким-то другим оператором. Не «настоящая проблема», поскольку циклы вполне понятны и для моих вкусов, но в поисках супер аккуратного или более эффективного встроенного …
template<typename out_type>
out_type sum(std::vector<float> const& matrix, std::vector<int> const& indices)
{
out_type cost = 0;
for(decltype(indices.size()) i = 0; i < indices.size() - 1; ++i)
{
const int index = indices.size() * indices[i] + indices[i + 1];
cost += matrix[index];
}
const int index = indices.size() * indices[indices.size() - 1] + indices[0];
cost += matrix[index];
return cost;
}
template<typename out_type>
out_type sum(std::vector<std::vector<float>> const& matrix, std::vector<int> const& indices)
{
out_type cost = 0;
for(decltype(indices.size()) i = 0; i < indices.size() - 1; i++)
{
cost += matrix[indices[i]][indices[i + 1]];
}
cost += matrix[indices[indices.size() - 1]][indices[0]];
return cost;
}
Ах, и PPL/TBB Честная игра тоже.
редактировать
Как запоздалая мысль и как прокомментировал Джон, будет ли место для работы станд :: common_type в расчете как могут различаться типы ввода и вывода? Это немного помахивание руками и больше похоже на методы обучения и библиотеки. Форма код ката, если вы будете.
Редактировать 2
Теперь есть один вариант, чтобы сделать циклы быстрее, объясняется в блоге Как обработать вектор STL с использованием кода SSE блогером theowl84. Код использует __m128 directly, но мне интересно, есть ли что-то в DirectXMath библиотека тоже.
Редактировать 3
Теперь, после написания конкретного кода, я нашел std::accumulate не получишь меня далеко Или, по крайней мере, я не мог найти способ сделать [indices[i + 1] участие в matrix[indices[i]][indices[i + 1]]; аккуратно, как std::accumulate Сам дает доступ только к текущему значению и сумме. В этом свете это выглядит как novelocrat-х подход будет наиболее плодотворным.
DeadMG предложил использовать parallel_reduce с оговорками ассоциативности, далее прокомментировал novelocrat. Я не пошел посмотреть, смогу ли я использовать parallel_reduce, интерфейс выглядел несколько громоздким для быстрой попытки. Кроме этого, даже если мой код выполняется последовательно, он будет страдать от тех же проблем, что и версия с параллельным сокращением. Хотя параллельная версия была бы / могла бы быть (намного) более непредсказуемой, чем серийная версия, я думаю.
Это идет в некотором роде, но это может быть интересным для некоторых здесь спотыкаться, и для тех, кто читал это далеко, могут быть (очень) заинтересованы в статье Блуждающая Точность в Блог NAG, в котором подробно описаны некоторые сложности даже при переупорядочении аппаратных инструкций! Тогда есть некоторые размышления об этой самой проблеме в распределенной установке в #AltDevBlogADay Синхронные двигатели RTS и повесть о рассинхронизации. Также, ACCU (кстати, общий список рассылки отличный, к нему можно бесплатно присоединиться), в нем есть несколько статей (например, этот) на точность с плавающей запятой. Касательное к тангенциальному, я нашел Фернандо Каччола Проблемы робастности в геометрических вычислениях быть хорошей статьей для чтения, изначально из списка рассылки ACCU.
А потом то std::common_type, Я не мог найти применение для этого. Если бы у меня было два разных типа в качестве параметров, то возвращаемое значение могло бы / должно быть решено std::common_type, Возможно, более уместным является std::is_convertible с static_assert чтобы убедиться, что желаемый тип результата можно преобразовать из типов аргументов (с чистым сообщением об ошибке). Кроме этого, я могу только проверить, что точность возвращаемого значения / промежуточного значения вычисления достаточна для представления результата суммирования без переполнений и тому подобного, но я не сталкивался со стандартным средством для этого.
Вот об этом, я думаю, дамы и господа. Мне понравилось, я надеюсь, что те, кто читает это, тоже что-то из этого получили.
Решение
Вы могли бы создать итератор, который принимает matrix а также indices и дает соответствующие значения.
class route_iterator
{
vector<vector<float>> const& matrix;
vector<int> const& indices;
int i;
public:
route_iterator(vector<vector<float>> const& matrix_, vector<int> const& indices_,
int begin = 0)
: matrix(matrix_), indices(indices_), i(begin)
{ }
float operator*() {
return matrix[indices[i]][indices[(i + 1) % indices.size()]];
}
route_iterator& operator++() {
++i;
return *this;
}
};
Тогда ваше накопление убегает от route_iterator(matrix, indices) в route_iterator(matrix, indices, indices.size()),
По общему признанию, однако, это упорядочивается без умного компилятора, превращающего его в нечто параллельное. Что вы действительно хотите, так это параллельное отображение и складывание (накопление) операций.
Другие решения
out_type cost = 0;
for(decltype(indices.size()) i = 0; i < indices.size() - 1; i++)
{
cost += matrix[indices[i]][indices[i + 1]];
}
Это в основном std::accumulate, PPL обеспечивает (и так же TBB, если я помню) parallel_reduce. Это требует ассоциативности, но не коммутативности, и + над реальным / float / integer является ассоциативным.