Russian Qt Forum
Ноябрь 23, 2024, 06:23 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: "Разпоточить" рекурсию  (Прочитано 7225 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Май 02, 2014, 07:36 »

Добрый день

Навеяно этим http://www.prog.org.ru/topic_26946_0.html, но там мои попытки завязать содержательный разговор не имели успеха Улыбающийся  Типа "ну вот есть средства (Concurrent, QThread) - вот ими и пользуйся". Наверное подразумевается что если уж выучил средства по букварю, то все самой получится. Но вот чего-то у меня не выходит Улыбающийся Псевдокод задачи
Код
C++ (Qt)
void Merge(int *A, int first, int last)
{
 // что-то делаем с массивом
}
 
void MergeSort(int *A, int first, int last)
{
 MergeSort(A, first, (first+last)/2); //сортировка левой части
 MergeSort(A, (first+last)/2+1, last); //сортировка правой части
 Merge(A, first, last); //слияние двух частей
}
 
void main()
{
 ...
 MergeSort(A, 1, n);
 ...
}
 
Как же будем "разпоточивать"? Да, и давайте по-взрослому: число созданных потоков не должно превышать число ядер

Спасибо
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #1 : Май 02, 2014, 08:02 »

В простом случае, нет нужды распоточивать рекурсию.
Например, можно запустить две нитки, каждой дать по половине массива. Дождаться их завершения и объединить их в запускающей нитке. Или запустить четыре и дать каждой по четверти массива.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Май 02, 2014, 08:43 »

В простом случае, нет нужды распоточивать рекурсию.
Например, можно запустить две нитки, каждой дать по половине массива. Дождаться их завершения и объединить их в запускающей нитке. Или запустить четыре и дать каждой по четверти массива.
Ну четыре надо сначала получить. А две - это всего 2 ядра, а сейчас 8 - пройденный этап, да и 16 никого не удивить. Да и даже 2 - как запускать-то? (в смысле куда встроить код запуска).

По поводу смысла: начиная так метров со 100 данных - он появляется очень быстро 
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #3 : Май 02, 2014, 08:52 »

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

Раскидать это можно и на 8 ядер. Например, в запускаемый создаём две нитки, внутри себя они создают ещё две рабочих.
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #4 : Май 02, 2014, 09:52 »

Добрался до компьютера:
Код
C++ (Qt)
int main()
{
   ...
 
   std::thread th1( std::bind( &MergeSort, A, first, (first+last)/2 ) );
   std::thread th2( std::bind( &MergeSort, A, (first+last)/2+1, last ) );
   th1.join();
   th2.join();
   Merge( A, first, last );
}
 
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Май 02, 2014, 10:11 »

Да, красиво с bind. Но все-таки это hard-coded для 2 ниток. Да, можно для 4, но все равно решение остается hard-coded. И предлагаю не частить, а послушать что люди скажут. Поэтому беру паузу  Улыбающийся
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #6 : Май 02, 2014, 10:40 »

Такое легко можно сделать для любого количества ниток. Главное требование, что это количество делилось на 2, но для этого алгоритма это вполне адекватное требование.
Реальных ниток будет больше, на каждую пару +1
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #7 : Май 02, 2014, 12:09 »

Цитировать
Как же будем "разпоточивать"? Да, и давайте по-взрослому: число созданных потоков не должно превышать число ядер

Спасибо

Эта задача аналогична распараллеливанию transform из этой темы http://www.prog.org.ru/topic_25963_15.html
Где вместо std::transform нужно поставить MergeSort)

« Последнее редактирование: Май 02, 2014, 12:11 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Май 03, 2014, 05:57 »

Эта задача аналогична распараллеливанию transform из этой темы http://www.prog.org.ru/topic_25963_15.html
Где вместо std::transform нужно поставить MergeSort)
В том-то и дело что нет, в данном случае число задач неизвестно заранее.

Такое легко можно сделать ..
Вам это ничего (никого) не напоминает? Улыбающийся "Прошу исполнить"
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #9 : Май 03, 2014, 07:36 »

Вам это ничего (никого) не напоминает? Улыбающийся
А вы про что/кого?

"Прошу исполнить"
Не вопрос.
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #10 : Май 03, 2014, 08:11 »

Ловите:

Код
C++ (Qt)
void sort( int *A, int first, int last, unsigned int numthread )
{
       assert( A );
       assert( first < last );
 
       if( numthread )
       {
               thread th1( bind( &sort, A, first, (first+last)/2, numthread - 1 ) );
               thread th2( bind( &sort, A, (first+last)/2+1, last, numthread - 1 ) );
               th1.join();
               th2.join();
       }
       else
       {
               thread th1( bind( &mergeSort, A, first, (first+last)/2 ) );
               thread th2( bind( &mergeSort, A, (first+last)/2+1, last ) );
               th1.join();
               th2.join();
       }
       merge( A, first, last );
}
 

numthread - это необходимое количество квадратов пар потоков.

Можно сделать красивей, но мне пока лень. Улыбающийся
« Последнее редактирование: Май 03, 2014, 08:58 от Old » Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #11 : Май 03, 2014, 14:51 »

Цитировать
В том-то и дело что нет, в данном случае число задач неизвестно заранее.

Ааа.. понятненько)

Ну так old уже предложил вариант)
Думаю, что ещё можно эту рекурсию в компил тайме раскрутить.. (через мета шаблонную магию)
« Последнее редактирование: Май 03, 2014, 14:56 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Май 04, 2014, 06:27 »

Ловите:
Это (может быть) помогло бы девушке сдать лабу, но не более того. Формально да, все нитки запущены, но ведь они толкаются и ждут друг друга. Производительность/КПД такой реализации ужасна.

Да, и UI кто-то всегда должен сопли подтирать, нечего там всем рассиживаться на join.
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #13 : Май 04, 2014, 07:27 »

Что за глупости? Никто там не толкается. Опять вас понесло в голословные утверждения про производительность и КПД? Улыбающийся
Всю основную работу делает заданное количество ниток рекурсивно. Дополнительные нити ждут их и процессор не едят. Если начнете думать, то и с UI все будет в порядке.

Это реализация сделанная на коленке за несколько минут, можно избавиться от объединяющих ниток, но нужно писать дополнительный код. Мне лень, да и не даст это особого прироста.

Так что очень ждем от вас "профессиональную" реализацию и будем сравнивать. Улыбающийся

« Последнее редактирование: Май 04, 2014, 08:00 от Old » Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.103 секунд. Запросов: 22.