c++ - 排序优化

Question

我目前正在学习算法类(class)，因此决定实现一些排序算法并比较它们是一种很好的做法。 我实现了合并排序和快速排序，然后比较了它们的运行时间以及 std::sort: 我的计算机不是最快的，但对于 1000000 个元素，我在 200 次尝试后平均得到:

1. std::sort -> 0.620342 秒
2. 快速排序 -> 2.2692
3. 合并排序 -> 2.19048

我想询问是否可以就如何改进和优化我的代码的实现提出意见。

void quickSort(std::vector<int>& nums, int s, int e, std::function<bool(int,int)> comparator = defaultComparator){
if(s >= e)
    return;

int pivot;
int a = s + (rand() % (e-s));
int b = s + (rand() % (e-s));
int c = s + (rand() % (e-s));

//find median of the 3 random pivots
int min = std::min(std::min(nums[a],nums[b]),nums[c]);
int max = std::max(std::max(nums[a],nums[b]),nums[c]);
if(nums[a] < max && nums[a] > min)
    pivot = a;
else if(nums[b] < max && nums[b] > min)
    pivot = b;
else
    pivot = c;

int temp = nums[s];
nums[s] = nums[pivot];
nums[pivot] = temp;

//partition
int i = s + 1, j = s + 1;
for(; j < e; j++){
    if(comparator(nums[j] , nums[s])){
        temp = nums[i];
        nums[i++] = nums[j];
        nums[j] = temp;
    }
}
temp = nums[i-1];
nums[i-1] = nums[s];
nums[s] = temp;

//sort left and right of partition
quickSort(nums,s,i-1,comparator);
quickSort(nums,i,e,comparator);

这里 s 是第一个元素的索引，e 是最后一个元素之后的索引。 defaultComparator 只是以下 lambda 函数:

auto defaultComparator = [](int a, int b){ return a <= b; };

std::vector<int> mergeSort(std::vector<int>& nums, int s, int e, std::function<bool(int,int)> comparator = defaultComparator){
std::vector<int> sorted(e-s);
if(s == e)
    return sorted;
int mid = (s+e)/2;
if(s == mid){
    sorted[0] = nums[s];
    return sorted;
}
std::vector<int> left = mergeSort(nums, s, mid);
std::vector<int> right = mergeSort(nums, mid, e);

unsigned int i = 0, j = 0;
unsigned int c = 0;
while(i < left.size() || j < right.size()){
    if(i == left.size()){
        sorted[c++] = right[j++];
    }
    else if(j == right.size()){
        sorted[c++] = left[i++];
    }
    else{
        if(comparator(left[i],right[j]))
            sorted[c++] = left[i++];
        else
            sorted[c++] = right[j++];
    }
}
return sorted;

谢谢大家

Answer 1

我看到的第一件事是，你传递了一个 std::function<>其中涉及虚拟调用，这是最昂贵的调用策略之一。尝试使用简单的模板 T(它可能是一个函数)——结果将是直接函数调用。

第二件事，在优化 和 存在就地变体时，永远不要在本地容器中执行此结果 ( vector<int> sorted; )。进行就地排序。客户应该知道你缩短了他们的 vector ；如果他们愿意，可以提前复印一份。您出于某种原因采用非常量引用。 [1]

第三，与 rand() 相关的成本它远非可以忽略不计。除非你确定你需要 quicksort() 的随机变体(及其关于“没有太糟糕的顺序”的好处)，仅使用第一个元素作为枢轴。或中间。

使用 std::swap()交换两个元素。很有可能，它被翻译成 xchg(在 x86/x64 上)或等价物，这是很难被击败的。可以从程序集输出中验证优化器是否识别出您打算在这些地方交换而不是明确的。

您找到三个元素的中位数的方式充满了条件移动/分支。就是nums[a] + nums[b] + nums[c] - max - min ;但越来越 nums[...] , min和 max同时还可以进一步优化。

避免 i++瞄准速度时。虽然大多数优化器通常 会创建良好的代码，但它有可能不是最理想的。优化时要明确(交换后 ++i)，但_only_when_optimizing_。

但最重要的一个:valgrind/callgrind/kcachegrind。个人资料，个人资料，个人资料。只优化真正慢的部分。

[1] 此规则有一个异常(exception):您从非 const 容器构建的 const 容器。这些通常是内部类型，并且在多个线程之间共享，因此最好在需要修改时将它们保留为 const & copy。在这种情况下，您将在函数中分配一个新容器(const 或非 const)，但您可能会保留 const 容器以方便用户使用 API。