Параллельная быстрая сортировка: рекурсия с использованием Boost Bind?

Я работаю над параллельной быстрой сортировкой, первая попытка - потоки. Версия без потоков сортируется правильно, а версия с потоками - нет (это неудивительно). Что мне показалось интересным, так это то, что когда я удалил потоки, но сохранил вызовы boost::bind, это все равно не работает. Если boost::bind — это не то, что мне нужно, предложите вариант. Bind оказался самым простым (или единственным) способом заставить мою функцию работать с потоками повышения.

void Quicksort( fVec &Array, const int Left, const int Right )
{
    if( Right <= Left )
        return;

    int pivot = Left;
    const int pivotNewIndex = Partition( Array, Left, Right, pivot );

    // These function calls make it work fine
    //Quicksort( Array, Left, pivotNewIndex - 1 );
    //Quicksort( Array, pivotNewIndex + 1, Right );

    // boost::bind calls only swaps one element, doesn't actually sort
    boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
    boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

    // threaded version that doesn't work, same as above
    //boost::thread threadA( boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 ) );
    //threadA.join();
    //boost::thread threadB( boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right ) );
    //threadB.join();
}

c++ multithreading boost
person Brian Paden    schedule 08.11.2008    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Boost bind более или менее создает функтор, который при вызове вызывает нужную функцию с нужными аргументами. В этом случае вы создаете функтор, но никогда не вызываете его. Пытаться:

boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

Я предполагаю, что первый аргумент - это то, что все испортило. Я думаю, что bind требует, чтобы аргументы были копируемыми, а ссылки на самом деле не являются, вероятно, он создает копию и передает ссылку на нее, поэтому ничего не меняется. Пытаться:

boost::bind( &Quicksort, boost::ref(Array), Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, boost::ref(Array), pivotNewIndex + 1, Right )();

Было бы полезно узнать, что такое fVec и почему вы не передаете указатель на массив того, что вы сортируете.

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

Также обратите внимание, что порядок, к которому вы присоединяетесь, в любом случае приводит к последовательному выполнению... вы хотите присоединиться к обоим потокам после запуска обоих потоков.

person Greg Rogers    schedule 08.11.2008