温馨提示:本文翻译自stackoverflow.com,查看原文请点击:algorithm - Why is In-place QuickSort slower than normal version in C++?

algorithm - 为什么就地QuickSort比C ++中的普通版本慢?

发布于 2020-03-27 10:27:36

在我的macOS的Xcode中,当元素的数量为10、100时,我对quicksort进行了计时器测试。在将数量设置为1000之前,就地版本的运行时间比另一个版本的运行时间慢。我正在使用C ++进行此测试。这是我主要功能的代码:

    const int sort_size = 100000;
    clock_t begin, end;
    vector<int> vec_1;
    srand((unsigned)time(NULL));
    for (auto i = 0; i < sort_size; ++i) {
        auto r = rand() % sort_size;
        vec_1.push_back(r);
    }
    vector<int> vec_2(vec_1);
    begin = clock();
    auto sort_1 = QuickSort::exec(vec_1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);
    begin = clock();
    auto sort_2 = QuickSort::exec_in_place(vec_2, 0, sort_size - 1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);

这两个函数都使用了静态声明。

这是就地版本代码:

vector<int> QuickSort::exec_in_place(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }
    auto pivot = [=, &nums] () {
        auto pivot_idx = begin + (end - begin) / 2;
        auto pivot_val = nums[pivot_idx], idx_1 = begin;
        std::swap(nums[pivot_idx], nums[end]);
        for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
            if (nums[idx_2] > pivot_val) continue;
            std::swap(nums[idx_1], nums[idx_2]);
            idx_1++;
        }
        std::swap(nums[idx_1], nums[end]);
        return idx_1;
    }();
    exec_in_place(nums, begin, pivot - 1);
    exec_in_place(nums, pivot + 1, end);
    return nums;
}

我想拉出lambda函数并将其包装到另一个静态函数中,但是结果仍然相同。

这是我的另一个普通版本,它也使用了递归样式。

vector<int> QuickSort::exec(const vector<int> &nums) {
    if (nums.size() < 2) {
        return nums;
    }
    auto pivot = nums[0];
    vector<int> smaller;
    vector<int> greater;
    for (auto i = 1; i < nums.size(); ++i) {
        int num = nums.at(i);
        if (num < pivot) {
            smaller.push_back(num);
        } else {
            greater.push_back(num);
        }
    }
    auto smaller_nums = exec(smaller);
    auto greater_nums = exec(greater);
    smaller_nums.push_back(pivot);
    smaller_nums.insert(smaller_nums.end(), greater_nums.begin(), 
    greater_nums.end());
    return smaller_nums;
}

自从我将数量设置为1000、10000等以来,就地开始放慢速度。例如,当金额等于1000时,就地花费0.005356秒,而普通版本花费0.001464秒。当数量达到100k时,就地版本大约为50秒,而普通版本大约为0.5秒。有人可以告诉我为什么吗?

抱歉,没有任何语法错误,英语不是我的母语。

查看更多

查看更多

提问者
varrtix
被浏览
94
user11729096 2019-07-03 21:45

无法发表评论,但是在就地版本中,您不需要lambda,也不需要返回向量。未经测试,对原始代码的更改最少:

void exec_in_placex(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return;
    }

    auto pivot_idx = begin + (end - begin) / 2;
    auto pivot_val = nums[pivot_idx], idx_1 = begin;
    std::swap(nums[pivot_idx], nums[end]);
    for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
        if (nums[idx_2] > pivot_val) continue;
        std::swap(nums[idx_1], nums[idx_2]);
        idx_1++;
    }
    std::swap(nums[idx_1], nums[end]);
    auto pivot = idx_1;

    exec_in_placex(nums, begin, pivot - 1);
    exec_in_placex(nums, pivot + 1, end);
}

发布
问题

分享
好友

手机
浏览

扫码手机浏览