Здравствуйте, RussianFellow, Вы писали:
RF>Что такое распараллеливание?
Это когда на собеседовании драться нужно одновременно с несколькими противниками.
RF>Что такое разделяемые переменные?
Это когда во время драки на собеседовании вы хватаетесь за стул, но за этот же стул одновременно хватается и ваш противник. В этом случае стул и будет той самой разделяемой переменной, своевременный захват которой обеспечит вам победу.
Здравствуйте, 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>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл CM>Кто-нибудь видит?
Кстати, конкретно эта задача на собеседовании имеет смысл. Основная идея — просто понимание что ты знаешь о таком приеме, как разделяй и властвуй.
Соответственно для тривиального случая возвращаешь исходный массив. Для вырожденного из двух элементов делаешь перестановку. Для основного случая дробишь на части, запускаешь над каждой частью в параллель рекурсивно обращение массива. Далее джоинишь результаты, итерируясь в обратном порядке. Это кстати можно сделать аналогично через рекурсию и на месте, правда будет выглядеть грязно.
Никакие разделяемые переменные ты тут не создаешь. Параллелизация есть. Рекурсия есть. Все условия выполняются. Правда алгоритмическая сложность кабздец какая стала, но чтоб не тормозило условий не было . Чтоб не тормозило, кстати, на практике там можно взять вырожденный случай не из двух элементов, а из миллиона. И вырожденный случай обрабатывать традиционным способом. И все, мы при этом даже ускорение легко сделали на количество ядер.
Мне задача понравилась тем, что она отсеет Артемку, не умеющего программировать, но зазубрившего типичные задачи и мнящего себя богом. И не оторвана от реальности, так как в реальности зачастую нужно весьма сложный алгоритм как то легко распараллелить, с минимальной модификацией исходного кода. Ибо исходный код может быть весьма сложен и запутанен. В результате на практике мы на некоторых алгоритмах получим ускорение, при этом хаос в коде становится не сильно ужаснее. И сделаем требуемое от нас быстро.
Здравствуйте, Voivoid, Вы писали:
V>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.
Что касатеся std::string, ЕМНИП там есть основной объект (который в массиве) и плюс к нему отдельная память в хипе.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Да вроде особо без проблем:
CM>Снова не соблюдается пункт 3
Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком. Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
Ну или пиши что тогда по твоему означают разделяемые переменные
Здравствуйте, Voivoid, Вы писали:
V>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.
Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой
И даже на x86, если у тебя просто массив int32 без пропусков для выравнивания, то будет полный ёк.
V>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
CM> CM>Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.
В моем примере нет конкурентного доступа к данным. Вообще. Кстати в этом и был смысл задачи. К чему ты тут вообще завел речь об атомарности и локах — я не знаю. И, кроме того, если мы говорим про C++, то начиная с 11-го стандарта у языка появилась наконец-то своя модель памяти и если уж очень хочется, то вести обсуждение надо в её контексте.
Здравствуйте, elmal, Вы писали:
E>Кстати, конкретно эта задача на собеседовании имеет смысл. Основная идея — просто понимание что ты знаешь о таком приеме, как разделяй и властвуй. E> ...
Тут было всё верно.
E>Мне задача понравилась тем, что она отсеет Артемку, не умеющего программировать, но зазубрившего типичные задачи и мнящего себя богом. E> ...
А вот тут ты сильно не прав... я просто с ним работал пару лет. Очень приличный уровень как у разработчика, побольше б таких
Здравствуйте, CodeMonkey, Вы писали:
CM>Здравствуйте, Voivoid, Вы писали:
V>>Ну тогда наверное не затруднит его указать?
CM>Уже указал. http://rsdn.org/forum/job/7298592?tree=tree
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии CM>2. Таким образом, чтобы это можно было распараллелить
Что такое распараллеливание?
CM>3. Не использовать никакие разделяемые переменные
Здравствуйте, RussianFellow, Вы писали:
CM>>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>>1. Сделать это при помощи рекурсии CM>>2. Таким образом, чтобы это можно было распараллелить
RF>Что такое распараллеливание?
Сейчас, подожди. Я дискету отформатирую и покажу.
-- Пользователи не приняли программу. Всех пришлось уничтожить. --
Здравствуйте, Muxa, Вы писали:
RF>>>Что такое распараллеливание? КД>>Сейчас, подожди. Я дискету отформатирую и покажу. M>Эту шутку он не поймёт.
Если меня склероз не подводит, то по возрасту RF должен был застать fido. Эта шутка там ходила.
И что-то мне подсказывает, что он вас троллит самым откровенным образом
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, 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>Здравствуйте, Voivoid, Вы писали:
V>>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.
CM>Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой
Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.
V>>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.
CM>Не мне, а кадровикам.
Здравствуйте, CodeMonkey, Вы писали:
CM>Итак, задача. Нужно развернуть массив (именно массив). Но: CM>1. Сделать это при помощи рекурсии CM>2. Таким образом, чтобы это можно было распараллелить CM>3. Не использовать никакие разделяемые переменные
CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл CM>Кто-нибудь видит?
Может массив распределенный и лежит на нескольких машинах?
Тогда
1. Не знаю зачем
2. Очевидно: можно данные на различных нодах обрабатывать параллельно
3. Очевидно: разделяемые переменные в распределенной среде это сразу будет еще одна отдельная задача, без которой тут можно обойтись
CM>Я написал совершенно конкретно, в каких условиях возможно писать без блокировки и почему у тебя это невозможно.
А это нарушение какого из трех пунктов?
Итак, задача. Нужно развернуть массив (именно массив). Но:
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, Вы писали:
CM>Не соблюдается пункт 3 — никаких разделяемых переменных. У тебя массив изменяется и разделяется.
Насколько я понимаю, пункт 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>Каким образом нет, если он есть?
Здравствуйте, CodeMonkey, Вы писали:
CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл CM>Кто-нибудь видит?
У меня возникла ассоциация с массивом который лежит в хдфс и цепочкой мап-редьюс задач для его обработки. На какую позицию спрашивают, чем заниматься предполагается?
Здравствуйте, sr_dev, Вы писали:
_>У меня возникла ассоциация с массивом который лежит в хдфс и цепочкой мап-редьюс задач для его обработки. На какую позицию спрашивают, чем заниматься предполагается?
