快速排序 C++ 中的 Lambda

Question

我正在编写一个快速排序函数，其中的 lambda 随机选择一个轴进行快速排序。当我最初构建没有 lambda 的排序函数时，我对函数进行了基准测试，该函数在 0.012 秒内对 25,000 个字符串的列表进行排序。现在我已经实现了一个 lambda，无论我如何选择枢轴点，它都需要 15 秒的相同算法来对相同的列表进行排序。我知道这是不正确的。这是我的代码，你知道为什么这会对这种类型的性能产生如此大的影响吗？

void quickSort (vector <string> &L, function<int(const vector<string> &, 
int,int)> pickPiv, int a, int b){

if (b ==-1){
    b = L.size();
}
const int n = b-a;

if (n<=1){
    return;
    // if list has one element or less then we are done sorting, this breaks the recursion
}
int piv = pickPiv (L,a,b);

swap (L[a],L[piv]);
piv =a;
for (int i =piv+1; i<b; i++){
    if (L[i] < L[piv]){

        swap(L[i],L[piv+1]);
        swap (L[piv],L[piv+1]);
        ++piv;
    }

}

quickSort(L,[](const vector <string> L, int a, int b) -> int {

   //return a;// if we want first element pivoting 
    int randpiv = rand()%(b-a +1)+a;
    return randpiv;
},a, piv);

quickSort(L,[](const vector <string> L, int a, int b) -> int {

   // return a; // if we want first element pivoting 
    int randpiv = rand()%(b-a +1)+a;
    return randpiv;
},piv+1,b);

}

Answer 1

正如评论中指出的那样，将 L 按值传递给 pickPiv 非常慢，但是您的代码存在更多问题。

您根本不需要将 L 传递给您正在定义 的 lambda 表达式，因为它们只在 a 和 [=15 上运行=].

您不应该使用 lambda 表达式进行递归，而是传递现有的 pickPiv

强烈考虑使用 std::uniform_int_distribution 来选择你的随机轴心点。

void quickSort (vector <string> &L, function<int(int,int)> pickPiv, int a, int b){

    if (b ==-1){
        b = L.size();
    }
    const int n = b-a;

    if (n<=1){
        return;
    }
    int piv = pickPiv(a, b);

    std::swap(L[a], L[piv]);
    piv =a;
    for (int i = piv+1; i<b; i++){
        if (L[i] < L[piv]){

            swap(L[i], L[piv+1]);
            swap(L[piv], L[piv+1]);
            ++piv;
        }

    }
    quickSort(L, pickPiv, a, piv);
    quickSort(L, pickPiv, piv+1, b);
}

int main(){
    std::random_device rd;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()

    std::vector<int> vec = { 4, 2, 7, 19, 3 };
    quickSort(vec, [&gen](int a, int b){
        std::uniform_int_distribution<> dis(a, b);
        return dis(gen);
    }, 0, -1);
}

快速排序 C++ 中的 Lambda

Lambda in Quicksort C++

c++

benchmarking

lambda

quicksort