c++ - 编译时递归排序与选择算法

Question

是否可以使用选择算法在 C++ 中编写编译时递归排序函数？

我想对数组 x 进行排序来自元素 istart到元素 iend按升序排列。数组 x有N元素。输入数组中的数据 x仅在运行时已知，因此只能在运行时对数据进行排序。但是，我想生成 C++ 代码，即所有对 sort_asc() 的递归函数调用。在编译时。此外，我想在 CUDA 设备功能中使用此代码。由于 CUDA 是 C++ 的一个子集，具有一些扩展，我认为这是问的正确地方。不幸的是，我认为 CUDA 不支持 constexpr关键字，既不是 Boost 也不是 STL。

我想出了下面的升序排序代码。

// sort in ascending order.
template< int istart, int N, int iend, int iend_min_istart >
inline void sort_asc
(
    float *x
)
{
    int   min_idx = istart;
    float min_val = x[ min_idx ];
    #pragma unroll
    for( int i=istart+1; i<N; i++ ){
        if( x[ i ] < min_val ){
            min_idx = i;
            min_val = x[ i ];
        }
    }
    swap( x[ istart ], x[ min_idx ] );
    sort_asc< istart+1, N, iend, iend-(istart+1) >( x );
}   

哪里iend_min_istart = iend - istart .如果iend_min_istart < 0则递归完成，因此我们可以将终止条件写为:

// sort recursion termination condition.
template< int istart, int N, int iend > 
inline void sort_asc< -1 >
(
    float *x
)
{
    // do nothing.
}

交换函数定义为:

void d_swap
( 
    float &a, 
    float &b 
)
{
    float c = a;
    a = b;
    b = c;
}

然后我将排序函数调用为:

void main( int argc, char *argv[] )
{
    float x[] = { 3, 4, 9, 2, 7 };   // 5 element array.
    sort_asc< 0, 5, 2, 2-0 >( x );   // sort from the 1st till the 3th element.
    float x_median = cost[ 2 ];      // the 3th element is the median
}

但是，此代码无法编译，因为 c++ 不支持函数的部分模板特化。此外，我不知道如何在 C++ 元编程中编写它。有什么方法可以使这段代码工作吗？

Answer 1

这次使用选择排序。 (Variant using merge sort。)没有任何保证，但通过了一个简单的测试:

// generate a sequence of integers as non-type template arguments
// (a basic meta-programming tool)
template<int... Is> struct seq {};
template<int N, int... Is> struct gen_seq : gen_seq<N-1, N-1, Is...> {};
template<int... Is> struct gen_seq<0, Is...> : seq<Is...> {};


// an array type that can be returned from a function
// and has `constexpr` accessors (as opposed to C++11's `std::array`)
template<class T, int N>
struct c_array
{
    T m[N];

    constexpr T const& operator[](int p) const
    {  return m[p];  }

    constexpr T const* begin() const { return m+0; }
    constexpr T const* end() const { return m+N; }
};


// return the index of the smallest element
template<class T, int Size>
constexpr int c_min_index(c_array<T, Size> const& arr, int offset, int cur)
{
    return Size == offset ? cur :
           c_min_index(arr, offset+1, arr[cur] < arr[offset] ? cur : offset);
}

我们的目标是能够在编译时进行排序。我们可以为此使用多种工具(宏、类模板、constexpr 函数)，但是constexpr在许多情况下，函数往往是最简单的。

函数c_min_index以上是 C++11 对 constexpr 的限制示例函数:它只能包含一个 return 语句(加上 static_assert 和 using )，并且至少对于某些可能的参数必须产生一个常量表达式。这意味着:没有循环，没有赋值。所以我们需要在这里使用递归，并将中间结果传递给下一次调用(cur)。

// copy the array but with the elements at `index0` and `index1` swapped
template<class T, int Size, int... Is>
constexpr c_array<T, Size> c_swap(c_array<T, Size> const& arr,
                                  int index0, int index1, seq<Is...>)
{
    return {{arr[Is == index0 ? index1 : Is == index1 ? index0 : Is]...}};
}

由于 constexpr，我们无法修改参数函数限制，我们需要返回整个数组的拷贝，只是为了交换两个元素。

函数需要 Is...是一个整数序列 0, 1, 2 .. Size-1 , 由 gen_seq<Size>{} 制作(在其基类中)。这些整数用于访问数组 arr 的元素。 .像 arr[Is]... 这样的表达会产生arr[0], arr[1], arr[2] .. arr[Size-1] .在这里，我们通过对当前整数应用条件来交换索引:a[0 == index0 ? index1 : 0 == index1 ? index0 : 0], ..

// the selection sort algorithm
template<class T, int Size>
constexpr c_array<T, Size> c_sel_sort(c_array<T, Size> const& arr, int cur = 0)
{
    return cur == Size ? arr :
           c_sel_sort( c_swap(arr, cur, c_min_index(arr, cur, cur),
                              gen_seq<Size>{}),
                       cur+1 );
}

同样，我们需要用递归替换循环 (cur)。其余的是一个直接的选择排序实现，语法笨拙:从索引开始 cur ，我们找到剩余数组中的最小元素，并将其与 cur 处的元素交换.然后，我们对剩余的未排序数组重新运行选择排序(通过递增 cur )。

#include <iostream>
#include <iterator>

int main()
{
    // homework: write a wrapper so that C-style arrays can be passed
    //           to an overload of `c_sel_sort` ;)
    constexpr c_array<float,10> f = {{4, 7, 9, 0, 6, 2, 3, 8, 1, 5}};
    constexpr auto sorted = c_sel_sort(f);
    for(auto const& e : sorted) std::cout << e << ", ";
}