Итак, задача. Нужно развернуть массив (именно массив). Но:
1. Сделать это при помощи рекурсии
2. Таким образом, чтобы это можно было распараллелить
3. Не использовать никакие разделяемые переменные
Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл
Кто-нибудь видит?
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии
легко CM>2. Таким образом, чтобы это можно было распараллелить
можно CM>3. Не использовать никакие разделяемые переменные
а сам массив?
CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл
если у вас очень много процессоров, то почему нет? N/2 одновременно запущенных корутин сделают своё дело. Точно! Шаблонная Variadic функция запускающая каждый swap в отдельном процессе.
CM>Кто-нибудь видит?
Ну это типа поиска максимума в массиве на GPU процессоре: запустить сравнение двух соседних элементов для всего массива сразу, а потом сравнить соседние результаты и повторять, пока не останется один элемент.
Здравствуйте, B0FEE664, Вы писали:
BFE>а сам массив?
Переменные нельзя. Исходный массив — можно, если он не меняется.
BFE>N/2 одновременно запущенных корутин сделают своё дело. Точно! Шаблонная Variadic функция запускающая каждый swap в отдельном процессе.
Самый большой вопрос — как на выходе получить массив Конверсия в массив из всего этого добра сожрет больше ресурсов, чем просто разворот в цикле (и делать это надо в один поток, поскольку см пункт 3)
Здравствуйте, CodeMonkey, Вы писали:
BFE>>N/2 одновременно запущенных корутин сделают своё дело. Точно! Шаблонная Variadic функция запускающая каждый swap в отдельном процессе.
CM>Самый большой вопрос — как на выходе получить массив Конверсия в массив из всего этого добра сожрет больше ресурсов, чем просто разворот в цикле (и делать это надо в один поток, поскольку см пункт 3)
а зачем его получать?:
template <class T>
void Swap(T& l, T& r)
{
T t = std::move(l);
l = std::move(r);
r = std::move(t);
}
std::array<int, 4> arr{{1,2,3,4}};
std::thread t1(Swap<int, int>, arr[0], arr[3]);
std::thread t2(Swap<int, int>, arr[1], arr[2]);
...
Здравствуйте, CodeMonkey, Вы писали:
CM>Не соблюдается пункт 3 — никаких разделяемых переменных. У тебя массив изменяется и разделяется.
Насколько я понимаю, пункт 3 выполнен.
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии CM>2. Таким образом, чтобы это можно было распараллелить CM>3. Не использовать никакие разделяемые переменные
Да вроде особо без проблем:
template <typename Iter>
void rev(Iter from, Iter mid, Iter to)
{
const auto len = mid - from;
if (len == 0)
{
return;
}
else if (len == 1)
{
std::iter_swap(from, to - 1);
return;
}
auto left = from + ( len / 2 );
auto right = to - ( len / 2 );
auto t1 = std::thread{ [=]() { rev(from, left, to); } };
auto t2 = std::thread{ [=]() { rev(left, mid, right); } };
t1.join();
t2.join();
}
template <typename Iter>
void rev(Iter begin, Iter end)
{
const auto len = end - begin;
rev(begin, begin + (len / 2), end);
}
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Да вроде особо без проблем:
CM>Снова не соблюдается пункт 3
Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком. Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
Ну или пиши что тогда по твоему означают разделяемые переменные
Здравствуйте, Voivoid, Вы писали:
V>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.
Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой
И даже на x86, если у тебя просто массив int32 без пропусков для выравнивания, то будет полный ёк.
V>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.
CM>Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой
Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
V>>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
CM>Не мне, а кадровикам.
Здравствуйте, Voivoid, Вы писали:
V>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.
Что касатеся std::string, ЕМНИП там есть основной объект (который в массиве) и плюс к нему отдельная память в хипе.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
CM> CM>Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.
В моем примере нет конкурентного доступа к данным. Вообще. Кстати в этом и был смысл задачи. К чему ты тут вообще завел речь об атомарности и локах — я не знаю. И, кроме того, если мы говорим про C++, то начиная с 11-го стандарта у языка появилась наконец-то своя модель памяти и если уж очень хочется, то вести обсуждение надо в её контексте.
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии CM>2. Таким образом, чтобы это можно было распараллелить CM>3. Не использовать никакие разделяемые переменные
CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл CM>Кто-нибудь видит?
Может массив распределенный и лежит на нескольких машинах?
Тогда
1. Не знаю зачем
2. Очевидно: можно данные на различных нодах обрабатывать параллельно
3. Очевидно: разделяемые переменные в распределенной среде это сразу будет еще одна отдельная задача, без которой тут можно обойтись
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии CM>2. Таким образом, чтобы это можно было распараллелить CM>3. Не использовать никакие разделяемые переменные
CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл CM>Кто-нибудь видит?
def rev(a):
L = len(a)
if L == 1:
return a
else:
left = rev(a[L//2:])
right = rev(a[:L//2])
return left + right
data = [1,2,3,4,5]
print(rev(data))
1. Рекурсия есть
2. left и right можно вычислять параллельно
3. Разделяемых переменных нет
Скорее всего дико неэффективно, но эффективности никто вроде и не требовал
Здравствуйте, Voivoid, Вы писали:
V> В моем примере нет конкурентного доступа к данным.
Каким образом нет, если он есть?
V>И, кроме того, если мы говорим про C++, то начиная с 11-го стандарта у языка появилась наконец-то своя модель памяти и если уж очень хочется, то вести обсуждение надо в её контексте.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>> В моем примере нет конкурентного доступа к данным.
CM>Каким образом нет, если он есть?