Параллельная быстрая сортировка: рекурсия с использованием Boost Bind?
Я работаю над параллельной быстрой сортировкой, первая попытка - потоки. Непоточная версия сортируется правильно, а многопоточная - нет (неудивительно). Что мне показалось интересным, так это когда я удалил потоки, но сохранил вызовы boost :: bind, это все еще не работает. Если boost :: 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();
}
Ответы 1
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 и почему вы не передаете указатель на массив того, что вы сортируете.
Также обратите внимание, что этот метод многопоточности, скорее всего, не даст большого ускорения, потому что, когда вы добираетесь до очень мелких сортировок, накладные расходы на запуск и планирование нового потока намного больше, чем выгода (плюс вы будете создавать огромное количество потоков, которые плохой). Что вам действительно нужно, так это пул потоков, который работает с некоторым фрагментом оптимального размера или больше и имеет фиксированное количество потоков. Когда достигаются размеры, меньшие, чем предел, он выполняет все последовательно (а для меньших размеров вы, очевидно, захотите перейти от быстрой сортировки к сортировке вставкой).
Также обратите внимание, что порядок, который вы присоединяете, в любом случае приводит к последовательному выполнению ... вы хотите присоединиться к обоим потокам после запуска обоих потоков.