并行快速排序:使用Boost Bind进行递归？

Question

我正在努力使quicksort并行,线程是第一次尝试.非线程版本正确排序,但线程没有(没有惊喜).我发现有趣的是当我删除线程但保持boost :: bind调用它仍然无效.如果boost :: bind不是我想要的,请提供建议.绑定似乎是使我的函数与boost线程一起工作的最简单(或唯一)方法.

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();
}

Answer 1

Boost绑定或多或少会创建一个仿函数,在调用时,它将使用您想要的参数调用所需的函数.在这种情况下,您正在创建仿函数但从不调用它.尝试:

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是什么以及为什么你没有将指针传递给你正在排序的数组.

另请注意,这种线程化方法可能不会给出非常快的速度,因为当你进入非常小的类别时,启动和调度新线程的开销远远大于好处(另外你将创建大量的线程,这是坏).你真正想要的是一个线程池,它运行在一些最佳大小的块或更大的块上,并具有固定数量的线程.当达到小于限制的大小时,它会连续地执行所有操作(对于较小的静止,您显然希望从快速排序更改为插入排序).

另请注意,您加入的顺序无论如何都会导致串行执行...您希望在启动两个线程后加入两个线程.