Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 15:59
Оценка:
Итак, задача. Нужно развернуть массив (именно массив). Но:
1. Сделать это при помощи рекурсии
2. Таким образом, чтобы это можно было распараллелить
3. Не использовать никакие разделяемые переменные

Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл
Кто-нибудь видит?
Re: Опять кадровики "радуют"
От: B0FEE664  
Дата: 15.11.18 16:23
Оценка:
Здравствуйте, CodeMonkey, Вы писали:

CM>Итак, задача. Нужно развернуть массив (именно массив). Но:

CM>1. Сделать это при помощи рекурсии
легко
CM>2. Таким образом, чтобы это можно было распараллелить
можно
CM>3. Не использовать никакие разделяемые переменные
а сам массив?

CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл

если у вас очень много процессоров, то почему нет? N/2 одновременно запущенных корутин сделают своё дело. Точно! Шаблонная Variadic функция запускающая каждый swap в отдельном процессе.

CM>Кто-нибудь видит?

Ну это типа поиска максимума в массиве на GPU процессоре: запустить сравнение двух соседних элементов для всего массива сразу, а потом сравнить соседние результаты и повторять, пока не останется один элемент.
И каждый день — без права на ошибку...
Re: Опять кадровики "радуют"
От: ononim  
Дата: 15.11.18 16:33
Оценка: :)))
CM>Кто-нибудь видит?
unsigned char array[32] = {...};
for (int i = 0; i < sizeof(array); ++i) {
    if (fork() == 0) {
        sleep(sizeof(array) - i);
        print("%02x ", array[i]);
    }
}


  Скрытый текст
классика же
Как много веселых ребят, и все делают велосипед...
Отредактировано 15.11.2018 16:34 ononim . Предыдущая версия .
Re[2]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 16:43
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>а сам массив?


Переменные нельзя. Исходный массив — можно, если он не меняется.

BFE>N/2 одновременно запущенных корутин сделают своё дело. Точно! Шаблонная Variadic функция запускающая каждый swap в отдельном процессе.


Самый большой вопрос — как на выходе получить массив Конверсия в массив из всего этого добра сожрет больше ресурсов, чем просто разворот в цикле (и делать это надо в один поток, поскольку см пункт 3)
Отредактировано 15.11.2018 16:44 CodeMonkey . Предыдущая версия .
Re[3]: Опять кадровики "радуют"
От: B0FEE664  
Дата: 15.11.18 17:03
Оценка: :)
Здравствуйте, 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]);
...
И каждый день — без права на ошибку...
Отредактировано 15.11.2018 17:04 B0FEE664 . Предыдущая версия .
Re[4]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 17:09
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>
BFE>template <class T>
BFE>void Swap(T& l, T& r)
BFE>{
BFE>  T t = std::move(l);
BFE>  l = std::move(r);
BFE>  r = std::move(t);
BFE>}

BFE>std::array<int, 4> arr{{1,2,3,4}};

BFE>std::thread t1(Swap<int, int>, arr[0], arr[3]);
BFE>std::thread t2(Swap<int, int>, arr[1], arr[2]);
BFE>...
BFE>


Не соблюдается пункт 3 — никаких разделяемых переменных. У тебя массив изменяется и разделяется.
Re[5]: Опять кадровики "радуют"
От: B0FEE664  
Дата: 15.11.18 17:18
Оценка:
Здравствуйте, CodeMonkey, Вы писали:

CM>Не соблюдается пункт 3 — никаких разделяемых переменных. У тебя массив изменяется и разделяется.

Насколько я понимаю, пункт 3 выполнен.
И каждый день — без права на ошибку...
Re[6]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 17:22
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>Насколько я понимаю, пункт 3 выполнен.


Озвучь ход мысли.
Re: Опять кадровики "радуют"
От: Voivoid Россия  
Дата: 15.11.18 17:32
Оценка: 9 (1) +2 :)
Здравствуйте, 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);
}


live пример
Re[2]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 17:36
Оценка:
Здравствуйте, Voivoid, Вы писали:

V>Да вроде особо без проблем:


Снова не соблюдается пункт 3
Re[3]: Опять кадровики "радуют"
От: Voivoid Россия  
Дата: 15.11.18 17:47
Оценка: +2
Здравствуйте, CodeMonkey, Вы писали:

CM>Здравствуйте, Voivoid, Вы писали:


V>>Да вроде особо без проблем:


CM>Снова не соблюдается пункт 3

Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком. Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.

Ну или пиши что тогда по твоему означают разделяемые переменные
Re[4]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 17:54
Оценка: :))
Здравствуйте, Voivoid, Вы писали:

V>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.


Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой
И даже на x86, если у тебя просто массив int32 без пропусков для выравнивания, то будет полный ёк.

V>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.


Не мне, а кадровикам.
Отредактировано 15.11.2018 17:59 CodeMonkey . Предыдущая версия .
Re[5]: Опять кадровики "радуют"
От: Voivoid Россия  
Дата: 15.11.18 18:07
Оценка: :)
Здравствуйте, CodeMonkey, Вы писали:

CM>Здравствуйте, Voivoid, Вы писали:


V>>Все соблюдается. Ни одна переменная не доступна более чем из одного потока. Ни один элемент массива не будет модифицирован более чем одним потоком.


CM>Только если допустить, что архитектура — x86, данные — примитивные и правильно выравнены, а размер данных — не более 64 бит. Что не упоминается ни в условиях задачи, ни тобой


Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.

V>>Но если тебе прям очень хочется, то можешь сделать копию массива и реверсить уже её.


CM>Не мне, а кадровикам.


Телепат?
Re[6]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 18:13
Оценка: :)))
Здравствуйте, Voivoid, Вы писали:

V>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.



Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.
Что касатеся std::string, ЕМНИП там есть основной объект (который в массиве) и плюс к нему отдельная память в хипе.

В общем — читать учебник, бегом.
Отредактировано 15.11.2018 18:18 CodeMonkey . Предыдущая версия .
Re[7]: Опять кадровики "радуют"
От: Voivoid Россия  
Дата: 15.11.18 18:37
Оценка: +1 :)
Здравствуйте, CodeMonkey, Вы писали:

CM>Здравствуйте, Voivoid, Вы писали:


V>>Это ты про что вообще? У моего кода со всем вышеперечисленным нет никаких проблем. Реверсь хоть std::string'и, хоть 128 битные int'ы, хоть под x86, хоть под x64.


CM>

CM>Данные читаются и пишутся порциями по 64 бита, просто на уровне железа. А это значит, что читать и писать атомарно и без локов можно только данные порциями по 64 бита (т.е. сами данные не более 64 бит и выравнены по интервалу б4 бита). Во всех остальных случаях, операции записи будут цеплять соседние элементы.

В моем примере нет конкурентного доступа к данным. Вообще. Кстати в этом и был смысл задачи. К чему ты тут вообще завел речь об атомарности и локах — я не знаю. И, кроме того, если мы говорим про C++, то начиная с 11-го стандарта у языка появилась наконец-то своя модель памяти и если уж очень хочется, то вести обсуждение надо в её контексте.
Re: Опять кадровики "радуют"
От: StatujaLeha на правах ИМХО
Дата: 15.11.18 18:43
Оценка: +1
Здравствуйте, CodeMonkey, Вы писали:

CM>Итак, задача. Нужно развернуть массив (именно массив). Но:

CM>1. Сделать это при помощи рекурсии
CM>2. Таким образом, чтобы это можно было распараллелить
CM>3. Не использовать никакие разделяемые переменные

CM>Не вижу ни одного возможного решения, которое имело бы хоть какой-то смысл

CM>Кто-нибудь видит?

Может массив распределенный и лежит на нескольких машинах?
Тогда
1. Не знаю зачем
2. Очевидно: можно данные на различных нодах обрабатывать параллельно
3. Очевидно: разделяемые переменные в распределенной среде это сразу будет еще одна отдельная задача, без которой тут можно обойтись
Re: Опять кадровики "радуют"
От: bnk СССР http://unmanagedvisio.com/
Дата: 15.11.18 19:27
Оценка:
Здравствуйте, 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. Разделяемых переменных нет

Скорее всего дико неэффективно, но эффективности никто вроде и не требовал
Re[8]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 19:27
Оценка:
Здравствуйте, Voivoid, Вы писали:

V> В моем примере нет конкурентного доступа к данным.


Каким образом нет, если он есть?

V>И, кроме того, если мы говорим про C++, то начиная с 11-го стандарта у языка появилась наконец-то своя модель памяти и если уж очень хочется, то вести обсуждение надо в её контексте.


Ну расскажи.
Re[2]: Опять кадровики "радуют"
От: CodeMonkey  
Дата: 15.11.18 19:28
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Может массив распределенный и лежит на нескольких машинах?


Про это не говорилось, но так это имело бы хоть какой-то смысл.
Re[9]: Опять кадровики "радуют"
От: Voivoid Россия  
Дата: 15.11.18 19:57
Оценка:
Здравствуйте, CodeMonkey, Вы писали:

CM>Здравствуйте, Voivoid, Вы писали:


V>> В моем примере нет конкурентного доступа к данным.


CM>Каким образом нет, если он есть?


Ну тогда наверное не затруднит его указать?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.