C/C++

Как стандартно распараллелить ассоциативное умножение в C++? Перемножаем, например, 1000 элементов.

От расстановки скобок произведение не зависит, а от порядка множителей зависит.

Вот лично я перемножаю vector<Qt>, Qt - мой собственный класс для кватернионов, оператор умножения для них есть, разумеется.

Всякие методы типа std::reduce принимают initial value, что намекает, что хрен его знает, как он множители при разных ExecutionPolicy переставит.
Сергей Зайцев
Сергей Зайцев
34 449
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;
long long product(const vector<long long>& box) {
if (box.empty()) return 0;
if (box.size() == 1) return box[0];
int n = static_cast<int>(box.size());
auto len = n >> 1;
if (n & 1) ++len;
vector<long long> acc(len);
for (auto i = 1, j = 0; i < n; i += 2, ++j) {
acc[j] = box[i] * box[i - 1];
}
if (n & 1) acc.back() = box.back();
if (len == 2) return acc[0] * acc[1];
else return product(acc);
}
int main() {
vector<long long> box(15);
iota(box.begin(), box.end(), 1);
for (auto x : box) cout << x << ' ';
puts("");
auto p = product(box);
cout << p << '\n';
}

P.S. Так что ли?
СГ
Серёга Грищенко
84 611
Лучший ответ
Сергей Зайцев Ммм... я попроще хотел, в одну строчку и испольованием стандарта - так, чтоб она рапараллелить вычисления мог.
Серёга Грищенко Допустим берём игральную кость, у которой сумма противоположных любых граней равна семи. Ставим её в некоторое изначальное положение. Например, Верх: 1, Фронт: 2. По условию у нас не допустимы преобразования, в результате которых куб возвращается в состояние, в котором он находился до начала вращения, за исключением стартового варианта. Итак вы имеете 24 состояния куба Верх - Фронт, в каждое из которых можно перейти путём вращения.
1 - 2
1 - 3
1 - 4
1 - 6
2 - 1
2 - 3
2 - 4
2 - 5
3 - 1
3 - 2
3 - 5
3 - 6
4 - 1
4 - 2
4 - 5
4 - 6
5 - 2
5 - 3
5 - 4
5 - 6
6 - 1
6 - 3
6 - 4
6 - 5
не очень понимаю, в чем именно проблема. я задачу понял не так, как Николай.
Вариант 1:
Создай 10 тредов, в каждом перемножь пачку из 100 кватернионов.
Дождись окончания тредов, перемножь их результаты.

Кол-во тредов лучше сделать параметром, т. к. на разном железе оптимальное кол-во тредов будет разным. Слишком много - плохо еще и потому, что тебе надо хранить промежуточные результаты, а это - память.

Вариант 2: больше подходит для случая, когда выполнение одного из тредов намного дольше, чем остальных. Тогда лучше пойти через ТредПул и очередь задач.
Добавляешь в очередь задачи на перемножение.
Тред Пул:
1) При добавлении задачи, если у него есть "свободный" тред - запускает задачу в нем, иначе - оставляет в очереди
2) При завершении треда - проверяет, что в очереди есть задачи. Если есть - отдает первую освободившемуся треду.
Соответственно, если один из тердов долго пыхтит - остальные в это время все остальные задачи выполнят.

У меня по этому варианту МТ-загрузка объектов из файла организована.
НС
Наталия Спирина
38 458
Сергей Зайцев Хочется стандартный one-liner из STL или, на худой конец, из boost.
Задача-то стандартная;.
Наталия Спирина Тот еж кватернион есть и в boost, но у тебя-то свой. Так почему бы и работу с потоками самостоятельно не сделать?
Ста ита такое сир?
Liss Liss
Liss Liss
444
Сергей Зайцев Сир, алгебра.
В математике фигова туча операций умножения, для которых сочетательное свойтсво умножения выполняется, а пермеестительное не выполняется.

Я хочу заставить его выполнять операцию типа
a*b*c*d*e*f
параллельно.
Но только так, чтоб он множители не переставлял. А скобки пусть сам расставляет, как ему удобно.
Например, a*b*c посчитает пусть в одном потоке, d*e*f - в другом, если уме так нравится. А потом переножит полученные значения (abc)(def)

Похожие вопросы