Модераторы: feodorv, GremlinProg, xvr, Fixin
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сортировка, многоядерный процессор 
:(
    Опции темы
User008
Дата 28.1.2010, 07:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 306
Регистрация: 9.9.2009

Репутация: нет
Всего: 1
Как наиболее быстро отсортировать массив с многоядерным процессором?
PM MAIL   Вверх
comcon1
Дата 28.1.2010, 08:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: нет
Всего: 17
изучайте:
http://www.iti.fh-flensburg.de/lang/algori...eren/algoen.htm

З.Ы. "кто быстрее" этот как "чья девка красивее"


--------------------
user posted image
comcon1 on twitter
PM MAIL   Вверх
User008
Дата 28.1.2010, 13:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 306
Регистрация: 9.9.2009

Репутация: нет
Всего: 1
Хотелось бы увидеть пример сортировки для многоядерного процессора.
Я вот думаю используя быструю сортировку, получить количество ядер, и создавать поток, если есть свободные ядра. Может есть более удобный способ?
PM MAIL   Вверх
xvr
Дата 28.1.2010, 14:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 40
Всего: 223
Цитата(User008 @ 28.1.2010,  13:58)
Я вот думаю используя быструю сортировку, получить количество ядер, и создавать поток, если есть свободные ядра. Может есть более удобный способ?

Есть. Использовать компиляторы с поддержкой OpenMP. И прописать соотвествующие прагмы в соотвествующие места
PM MAIL   Вверх
comcon1
Дата 28.1.2010, 15:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: нет
Всего: 17
Ты хочешь изобретать велосипед или хочешь сортировать?


--------------------
user posted image
comcon1 on twitter
PM MAIL   Вверх
User008
Дата 28.1.2010, 19:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 306
Регистрация: 9.9.2009

Репутация: нет
Всего: 1
Хочу посмотреть пример
PM MAIL   Вверх
comcon1
Дата 29.1.2010, 12:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: нет
Всего: 17
Блин, за вас за всех надо гуглить?
http://www.dreamincode.net/forums/showtopic84296.htm


--------------------
user posted image
comcon1 on twitter
PM MAIL   Вверх
User008
Дата 31.1.2010, 08:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 306
Регистрация: 9.9.2009

Репутация: нет
Всего: 1
Код

void sort(unsigned int *beg, unsigned int *end)
{
    unsigned  x = beg[(end-beg)/2];
    unsigned *p = beg, *q = end;

    do { 
        while (*p < x) ++p; 
        while (*q > x) --q;
        if (p <= q)
        {
            std::iter_swap(p, q);
            ++p; --q;
        }
    } while (p <= q);

    #pragma omp parallel sections
    {
        #pragma omp section
        if (beg < q) sort(beg, q);

        #pragma omp section
        if (p < end) sort(p, end);
    }
}

Сделал так, но сортироваться стало намного дольше

Это сообщение отредактировал(а) User008 - 31.1.2010, 08:25
PM MAIL   Вверх
xvr
Дата 31.1.2010, 12:18 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 40
Всего: 223
Цитата

Сделал так, но сортироваться стало намного дольше
Параллелить нужно цикл, а не рекурсивные вызовы процедур. QSort в чистом виде не очень удобен для распараллеливания.
Лучше порезать массив на части, в каждой из них сделать (в параллель) QSort, а затем сделать слияние результатов.
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Системное программирование и WinAPI"
Fixin
GremlinProg
xvr
feodorv
  • Большое количество информации и примеров с использованием функций WinAPI можно найти в MSDN
  • Описание сообщений, уведомлений и примеров с использованием компонент WinAPI (BUTTON, EDIT, STATIC, и т.п.), можно найти в MSDN Control Library
  • Непосредственно, перед созданием новой темы, проверьте заголовок и удостоверьтесь, что он отражает суть обсуждения.
  • После заполнения поля "Название темы", обратите внимание на наличие и содержание панели "А здесь смотрели?", возможно Ваш вопрос уже был решен.
  • Приводите часть кода, в которой предположительно находится проблема или ошибка.
  • Если указываете код, пользуйтесь тегами [code][/code], или их кнопочными аналогами.
  • Если вопрос решен, воспользуйтесь соответствующей ссылкой, расположенной напротив названия темы.
  • Один топик - один вопрос!
  • Перед тем как создать тему - прочтите это .

На данный раздел распространяются Правила форума и Правила раздела С++:Общие вопросы .

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Chipset, Step, Fixin, GremlinProg, xvr. feodorv.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Системное программирование и WinAPI | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0568 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.