基数排序实现的优化：比标准排序慢于预期 - C++

问题描述 投票：0回答：1

同样的问题最初是在Python中发布的。按照@user24714692的建议，我在CPP中编码了所有内容并创建了一个新问题。

我已经在 C++ 中实现了基数排序的版本（该版本允许对值达到 n² 的整数进行排序，其中 n 是要排序的列表的大小），用于针对标准内置排序（三部分混合排序）进行基准测试排序算法）。

令人惊讶的是，即使不使用哈希图（使用直接访问数组），我的基数排序实现也比标准排序慢，即使对于较大的输入大小也是如此。由于我的时间复杂度为 O(n)，内置的时间复杂度为 O(nlogn)，因此应该有方法对我的编码进行微优化。我正在寻求有关优化实施以实现更好性能的建议。我这样做不是为了实际目的，而只是为了学习目的，因为我对编程相当陌生，因此我不会寻找外部库来神奇地改进我的代码，而不理解为什么它会变得更好。

我可以进行微观优化吗？我的代码真的是 O(n) 吗？

时间以秒表示：

Size Radix Sort No Hashmap std::sort 1.000e+03 2.981e-04 1.059e-04 1.000e+04 2.612e-03 1.330e-03 1.000e+05 3.157e-02 1.608e-02 2.000e+05 5.678e-02 3.460e-02 1.000e+06 3.820e-01 1.951e-01 2.000e+06 8.998e-01 4.029e-01 3.000e+06 1.365e+00 6.243e-01 4.000e+06 1.981e+00 8.314e-01 5.000e+06 2.607e+00 1.078e+00 6.000e+06 3.024e+00 1.317e+00 1.000e+07 5.679e+00 2.224e+00 
使用的代码：


#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <iomanip>

void radix_sort_no_hashmap(std::vector<long long>& arr, long long size) {
    std::vector<std::vector<long long>> least_sig_digit(size);
    for (long long num : arr) {
        long long q = num / size;
        long long r = num % size;
        least_sig_digit[r].push_back(q);
    }
    std::vector<std::vector<long long>> highest_sig_digit(size);
    for (long long k = 0; k < size; ++k) {
        for (long long q : least_sig_digit[k]) {
            highest_sig_digit[q].push_back(q * size + k);
        }
    }
    long long i = 0;
    for (long long k = 0; k < size; ++k) {
        for (long long num : highest_sig_digit[k]) {
            arr[i++] = num;
        }
    }
}

void benchmark_sorting_algorithms(std::vector<long long>& sizes, std::vector<double>& radix_times, std::vector<double>& std_sort_times) {
    for (long long size : sizes) {
        std::vector<long long> array(size);

        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<long long> dis(0, size-1);

        for (long long& num : array) {
            num = dis(gen);
            num = num * num; // To ensure large values
        }

        auto new_arr1 = array;
        auto start = std::chrono::high_resolution_clock::now();
        radix_sort_no_hashmap(new_arr1, size);
        auto end = std::chrono::high_resolution_clock::now();
        radix_times.push_back(std::chrono::duration<double>(end - start).count());

        auto new_arr2 = array;
        start = std::chrono::high_resolution_clock::now();
        std::sort(new_arr2.begin(), new_arr2.end());
        end = std::chrono::high_resolution_clock::now();
        std_sort_times.push_back(std::chrono::duration<double>(end - start).count());

        // Make sure that the arrays are sorted correctly
        for (long long i = 0; i < size; ++i) {
            if (new_arr1[i] != new_arr2[i]) {
                std::cout << "Sorting failed\n";
                return;
            }
        }
    }
}

int main() {
    std::vector<long long> sizes = {1000, 10000, 100000, 200000, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 10000000};
    std::vector<double> radix_times;
    std::vector<double> std_sort_times;

    benchmark_sorting_algorithms(sizes, radix_times, std_sort_times);

    std::cout << "Size\t\tRadix Sort No Hashmap\t\tstd::sort\n";
    for (long long i = 0; i < sizes.size(); ++i) {
        std::cout << std::scientific << std::setprecision(3) << (float)sizes[i] << "\t\t" << radix_times[i] << "\t\t" << std_sort_times[i] << "\n";
    }
    return 0;
}

编辑：
有了 
-O3
，我得到（我添加了 
2.5*10^7
 和 
5*10^7
）：


Size            Radix Sort No Hashmap           std::sort
1.000e+03               1.240e-04               2.570e-05
1.000e+04               1.074e-03               3.021e-04
1.000e+05               8.306e-03               3.105e-03
2.000e+05               1.715e-02               6.766e-03
1.000e+06               1.513e-01               3.733e-02
2.000e+06               3.604e-01               7.737e-02
3.000e+06               5.512e-01               1.189e-01
4.000e+06               8.579e-01               1.681e-01
5.000e+06               1.290e+00               2.083e-01
6.000e+06               1.265e+00               2.477e-01
1.000e+07               2.485e+00               4.379e-01
2.500e+07               7.505e+00               1.150e+00
5.000e+07               1.585e+01               2.378e+00

编辑2：
我按照评论中的要求做了一个情节（我也添加了
2.5*10^7
和
5*10^7
）：

enter image description here

编辑3：
打印 Time/N 而不是 Time against N 来查看是否得到一个常量（添加了很多测试用例）：

enter image description here
    

	


c++

sorting


1个回答




    
    
    

        

            

                

                    
0
投票

                    
                

            

        

        
性能方面的主要问题是您的代码进行了大量的内存分配。这是非常昂贵的。 2D 向量中的每个向量都是动态增长的。这意味着在第一个 
.push_back()
 调用时，它为 
1
 或 
2
 元素分配空间，然后在第三次调用时为 
4
 元素分配空间，并将其所有日期复制到新分配的内存位置。然后
8
等等。上述值取决于实现并且并不精确。但这个想法是正确的。矢量扩展的成本很高。


std::sort
，相反，完全就地实施。它不会分配任何额外的空间来对范围进行排序。


您可以通过对您计划填充的向量调用 
.reserve(<needed memory capacity>)
 来避免这些分配。如果您知道向量有多少个元素，则此解决方案可以正常工作。或者可以根据一些经验知识提出一些估计。所以你的循环将如下所示：


std::vector<std::vector<long long>> least_sig_digit(size);
for(auto& loc_arr : least_sig_digit){
    loc_arr.reserve(<your future size estimation>)
}
for (long long num : arr) {
    long long q = num / size;
    long long r = num % size;
    least_sig_digit[r].push_back(q);
}

对向量填充方式的这种更改将显着提高代码性能。


如果您对向量未来的大小没有任何估计，您可以尝试使用 
std::deque
 而不是 
std::vector
。它有不同的分配政策，在您的情况下，最终的分配总量可能会减少。 
std::deque
 以固定大小的块分配内存，并且不会将数据从旧位置复制到新位置。因此，有时，当您必须应对动态增长时，速度可能会更快。但您将付出更慢的元素访问速度和更慢的迭代速度的代价。


那是很久以前的事了，当时我写了我的基数排序。
但我还建议您将元素拆分为“单词”，以便以不同的方式进行基数排序。现在您进行动态拆分。我的意思是，您的“单词”大小由您在运行时传递的 
deque
 定义。您可以根据字体大小来修复该大小。您正在使用 
size
。将每个值拆分为四个 
int64_t
 字节字。这样，您将通过 
16
 修复“内部”向量的大小，并且可以使用 
4
 代替 
std::vector<std::array<4, uint16_t>>
。这将需要更多的工作，因为您需要遍历数组 4 次，但它也将具有更好的内存局部性，因此最终结果会很好。


性能就是实验和测量。很少有事情是有保证的，但很多事情都值得尝试:)

    

	



    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.