基排序(LSD)和计数排序

Question

我正在阅读CLRS，为了练习，我滚动了我的基排序和计数排序版本。我看了一些参考实现，特别是罗塞塔代码中的迷幻剂1，我的执行情况要好得多(~10次)，尤其是在64位输入和最大输入范围已知的情况下。

我认为可以改进的地方之一是在计数排序中创建res。如果我现在可以使用reserve作为缺省值，初始化所有内容，然后对它们进行分配，那么速度会更快。但是，我不能使用push_back来生长它，因为在下面的循环中，res是随机增长的，而不是push_back所要求的线性增长。我不知道有任何数据结构可以具有运行时设置的大小，这些值也可以在循环后的copy行中得到很好的优化。

我对可变长度数组(如T res[n] )进行了实验，它的工作范围达到了堆栈限制。但是，不能将输入大小限制在堆栈的大小上。无论如何，这种更改对性能没有明显的影响。

如能提出改进建议，将不胜感激。

算法库

计数排序

// counting sort, assumes each input is integral between 0 to k
// O(n) if k = O(n)
template <typename Iter, typename Op>
void cnt_sort(Iter begin, Iter end, size_t k, Op op) {
    vector<int> counts(k);   // init to 0
    for (auto i = begin; i != end; ++i) // count # elems == i
        ++counts[op(*i)]; 
    for (size_t i = 1; i < k; ++i)
        counts[i] += counts[i-1];   // turn into # elems <= i
    vector<typename Iter::value_type> res(distance(begin, end)); // doing useless initialization here
    for (auto j = end;;) {
        --j;
        res[--counts[op(*j)]] = *j;
        if (j == begin) break;
    }
    copy(res.begin(), res.end(), begin); // compiler optimizes this out
}

基类

// radix sort, more practical than counting sort
// O(d(n + k)) running time where d is # digits, k is size of digit
class Digit_cmp {   // functor for comparing a "digit" (particular bits)
    const long long mask; // 0..63 bitfield to test against
    const size_t to_shift;
public:
    Digit_cmp(long long m, size_t ts) : mask(m), to_shift(ts) {}
    template <typename T>
    T operator()(T n) const {
        return (n & mask) >> to_shift; // mask then shift to unit digit ex. 0xfab20000 >> 16
    }
};

template <typename Iter>   
void rdx_sort(Iter begin, Iter end, int bits) { 
    // bits is # bits to consider up to if a max val is known ahead of time
    // most efficent when digits are base n, having lg(n) bits
    size_t r {static_cast<size_t>(log2(end - begin))};   // # bits in digit
    size_t k {static_cast<size_t>(pow(2, r))};           // range of digit
    size_t d {0};                   // current digit num
    for (long long mask = ~(~0 << r);; // ex. 0x000000ff for setting lower 8 bits on 32 bit num
        mask <<= r) {
        cnt_sort(begin, end, k, Digit_cmp(mask, r*d));
        ++d;
        if (mask & (1 << (bits-1))) break; // finished masking most significant digit
    }
}
template <typename Iter>   // range of input not known, just use max ex. 32 bits for ints
void rdx_sort(Iter begin, Iter end) {
    int bits {sizeof(typename Iter::value_type)*CHAR_BIT};
    rdx_sort(begin, end, bits);
}

Answer 1

我找到了一个清单，列出了一些你可以改进的东西，但是没有任何东西能显著改变你的工作方式：

• 在计数排序的末尾，可以使用std::move而不是std::copy将元素移动到原始集合。对于简单整数，它不应该改变任何东西，但如果您试图对大整数进行排序，它可能会产生很大的不同。
• 由于使用了sizeof(typename Iter::value_type)*CHAR_BIT，在标准库中有一种更实用的计算std::numeric_limits::digits的方法，因此您实际上可以重写rdx_sort如下:模板 //范围输入未知，只需使用max ex即可。ints的32位无效rdx_sort(Iter，Iter ){ int位{std::numeric_limits::digits}；rdx_sort(begin，end，bits)；}任何数字库(像一个大数字库)都可以专门化std::numeric_limits，而每个合适的数字库都是这样做的，所以我不应该让您的代码更不容易移植。顺便说一句，返回的值并不总是int，所以您可以做的最好的事情就是使用类型别名来使事情变得更清楚: template < type make Iter> // range of input不知道，只需使用max ex。用于ints的32位无效rdx_sort(Iter，Iter ){ value_type = typename Iter::value_type value_type bits {std::numeric_limits::digits}；rdx_sort(begin，end，bits)；}
• 要小心一些疯狂的假设: const长掩码；// 0.63位字段用于测试long long并不一定是64位整数，即使这种情况更常见。如果您想避免问题，应该使用std::int64_t从…。这种类型只存在于架构实际上有64位整数的情况下，bug --我想如果您的实现没有，那么无论如何您会遇到更多的问题。const std::int64_t掩码；// 0.63位域进行测试
• 您似乎在使用using namespace std;，这是像您这样的头专用库中的你应该really避免。使用此指令将每个名称从std::导入到全局命名空间中，供任何使用您的库的人使用，并且您肯定会在某个时候以名称冲突结束。考虑std::-qualifying从C和C++标准库(当然除了宏)的所有东西，甚至std::size_t：有些实现不会将名称从C标准库导入全局命名空间。
• 从函数名中删除随机元音将不再有帮助。考虑使用像counting_sort和radix_sort这样的全名。