Quick Sort с использованием boost coroutine

204
04 апреля 2018, 10:46

Есть задание написать алгоритм быстрой сортировки с использованием сопрограмм из библиотеки boost. Вроде написал, но получается, что он по времени сортирует дольше чем без использования сопрограмм. Хотя в теории должен быстрее. Подскажите, что не так делаю?

template <class T>
using vector_t = std::vector<T>;
using coro_t = boost::coroutines2::coroutine<int32_t>;
template <class T>
void partition(coro_t::push_type& sink, vector_t<T>& v, int32_t left, int32_t right) {
    int32_t pivot = v[right];
    int32_t i = (left - 1);
    for (int32_t j = left; j <= right - 1; j++) {
        if (v[j] <= pivot) {
            i++;
            std::swap(v[i], v[j]);
        }
    }
    std::swap(v[i + 1], v[right]);
    sink(i + 1);
}
template <class T>
void quickSort(vector_t<T>& v, int32_t left, int32_t right) {
    if (left <= right) {
        coro_t::pull_type source{[&](auto &&arg1) {
            partition(arg1, v, left, right);
            quickSort(v, left, source.get() - 1);
            quickSort(v, source.get() + 1, right);
        }};
        source();
    }
}
int main() {
    vector_t<int32_t> v(10);
    std::cin >> v;
    std::cout <<"Vector before:\n" << v << std::endl;
    clock_t t = clock();
    quickSort(v, 0, v.size() - 1);
    t = clock() - t;
    std::cout << std::fixed << ((double) t) / CLOCKS_PER_SEC << std::endl;
    std::cout << "Vector after:\n" << v << std::endl;
}
Answer 1

Корутины работают в одном потоке, они в любом случае будут работать медленнее (на их создание всё же затрачивается время). Они дают преимущество только при асинхронных операциях.

Для ускорения нужны либо многопоточные корутины (в boost вроде бы есть что-то подобное), либо банальный пул потоков. Если хотите добиться ускорения - я бы рекомендовал сначала реализовать быструю сортировку с использованием std::async и посмотреть, получится ли вообще ускорение при распараллеливании. Для малых векторов точно не получится, результаты должны быть видны при сортировке примерно тысячи небольших строк (сортировка строк лучше демонстрирует применимость в реальных программах, для сортировки int вряд ли вообще нужна многопоточность).

READ ALSO
Перенос программы Qt, взаимодействующей с Mysql

Перенос программы Qt, взаимодействующей с Mysql

Имеется программа, написанная на Qt под linux, в которой происходит взаимодействие с БД MySqlНа компьютере с Qt она прекрасно работает, однако, при...

214
проблема с неполным типом и forward declaration

проблема с неполным типом и forward declaration

есть класс бинарного дерева:

222
Как вывести слова встречающиеся в обоих файлах?

Как вывести слова встречающиеся в обоих файлах?

Имеются 2 файла, в каждом из них словаНужно вывести на экран консоли слова, которые встречаются в обоих файлах

216
Взятие структуры из класса

Взятие структуры из класса

в сlass Points имеется структура

207