并行快速排序:使用BoostBind的递归

Question

我正在努力使quicksort并行，线程是第一次尝试。非线程版本排序正确，但线程版本则不正确（这并不奇怪）。我发现有趣的是，当我删除线程但保留boost:：bind调用时，它仍然不起作用。如果boost:：绑定不是我想要的，请提供一个建议。绑定似乎是使我的函数与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 bind或多或少会创建一个函子，当被调用时，它将使用所需的参数调用所需的函数。在这种情况下，您正在创建函子，但从未调用它。尝试：

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

我猜第一个论点是什么把事情搞砸了。我认为绑定需要参数是可复制的，而引用并不是真的，它可能是在创建一个副本并将引用传递给它，这就是为什么什么都没有改变的原因。尝试：

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

了解fVec是什么以及为什么不将指针传递给正在排序的数组会有所帮助。

还要注意的是，这种线程方法可能不会带来太多的加速，因为当你进行非常小的排序时，启动和调度一个新线程的开销远远大于好处（此外，你将创建大量线程，这很糟糕）。你真正想要的是一个线程池，它在某个最佳大小或更大的块上运行，并具有固定数量的线程。当达到小于限制的大小时，它会按顺序执行所有操作（对于更小的大小，您显然希望从快速排序更改为插入排序）。

还要注意，你加入的顺序无论如何都会导致串行执行。。。您希望在启动两个线程后连接这两个线程。