使用选择算法的编译时间递归排序

Luc 发表于 Dev

卢克

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

我想排序数组x的元素istart以元素iend升序排列。数组x具有N元素。输入数组中的数据x仅在运行时才知道，因此只能在运行时对数据进行排序。但是，我想生成C ++代码，即sort_asc()在编译时对所有递归函数的调用。此外，我想在CUDA设备功能中使用此代码。由于CUDA是C ++的子集，具有少量扩展，因此我认为这是问的正确地方。不幸的是，我不认为CUDA不支持constexprBoost或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;
}

然后我将sort函数称为：

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 ++元编程中编写此代码。有什么办法可以使此代码起作用？

卢克

我想出了以下元代码，它可以工作。

template < class T >
__forceinline void swap
( 
    T &a, 
    T &b 
)
{
    T c = a;
    a = b;
    b = c;
}

template< int istart, int N, int iend, int iend_min_istart >
class SORT
{
    public:
        static __forceinline void sort( float *x, int *idx )
        {
            // sort code.
            int   min_idx = istart;
            float min_val = x[ min_idx ];
            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 ] );
            swap( idx[ istart ], idx[ min_idx ] );
            SORT<istart+1, N, iend, iend-(istart+1)>::sort( x, idx );
        }
};

template< int istart, int N, int iend >
class SORT<istart,N,iend,-1>
{
    public:
        static __forceinline void sort( float *x, int *idx )
        {

        }
};

void main( int argc, char *argv[] )
{
    float arr[] = {1,4,2,7,5};
    int   idx[] = {0,1,2,3,4};
    SORT<0,5,3,2-0>::sort( arr, idx );
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-02-5

我来说两句

0条评论

登录后参与评论

来自分类Dev

Related 相关文章

文章