2

Вот есть такая реализация быстрой сортировки:

template<class iterator>
void qsort(iterator begin, iterator end)
{
    if (begin == end)
        return;

    const auto distance = std::distance(begin, end);
    iterator p = std::next(begin, distance / 2);
    iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
    iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});

    qsort(begin, it1);
    qsort(it2,  end);
}

Я хочу реализовать паралельное выполнение этого алгоритма. Можно конечно сделать так:

template<class iterator>
void qsort(iterator begin, iterator end)
{
    if (begin == end)
        return;

    const auto distance = std::distance(begin, end);
    iterator p = std::next(begin, distance / 2);
    iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
    iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});

    std::thread t1(qSort<Iterator>, begin, middle1);
    std::thread t2(qSort<Iterator>, middle2, end);

    t1.join();
    t2.join();
}

но это очевидно далеко не лучшая реализация т.к. количество потоков будет равно log(n).

Вопрос: как правильно реализовать многопоточный алгоритм быстрой сортировки? Можно написать класс который будет лимитировать количество потоков и передавать его в функцию, но стандартная реализация std::sort может выполняться в нескольких потоков, при этом ее сигнатура не меняется, хотелось бы реализовать что-то подобное.

0

2 ответа 2

5

Чтоб решить проблему именно с сигнатурами функцию с дополнительным параметром просто не показывайте пользователю, а функция, которой должен пользоваться клиент должна быть с такой же сигнатурой как и сейчас:

template<class iterator>
void qsort(iterator begin, iterator end)
{
  qsort_internal(begin, end, 4);
}

template<class iterator>
void qsort_internal(iterator begin, iterator end, int max_threads)
{

  ...
  if (max_threads > 1) {
    //сортируем многопоточно
    // но уменьшаем max_threads в рекурсивном вызове
  } else {
    // сортируем в этом же потоке 
  }

}

Нужно понимать, что такая наивная реализация, скорее всего не даст особого прироста, а скорее всего будет медленее, на небольших массивах даже существенно медленнее. Поищите тут, неоднократно обсуждался вопрос и трудности связанные с ускорением алгоритмов путем параллелизации и в частности с ускорением быстрой сортировки.

4

Для таких задач обычно используются пул потоков с фиксированным числом потоков (одна из его реализаций), добавление задачи в пул по производительности в худшем случае эквивалентно блокировке мьютекса.

Стандартные реализации параллельных алгоритмов обычно использует скрытый от пользователя (глобальный) пул потоков. Или же OpenMP, реализация которого также использует пул потоков, но могут использовать какие-то дополнительные особенности платформы.

Можно найти примеры сортировки при помощи std::async, который также может использовать глобальный пул потоков. Но на практике реализации стандартных библиотек могут создавать новый поток вместо использования пула, из-за чего смысла в этом нет.

Если говорить конкретно о сортировке, у вас вряд ли получится приблизиться к стандартной реализации. Подобные алгоритмы вообще плохо распараллеливаются на ЦП, из-за чего для их реализации используется множество не очевидных приемов (и результат все-равно сомнительный). Если вам действительно интересно ускорение сортировки - рекомендую смотреть в сторону GPU (thrust::sort, например).

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.