随笔-88  评论-224  文章-23  trackbacks-0
基本原理
   数据输入随机分布的情况下,快速排序具有较好的性能表现,但当元素个数比其关键字的取值范围大,而这个范围相对较小时,使用一种关键字索引统计排序会快很多,因为它的时间复杂度是线性的,基本原理是使用数组(为描述方便,特称统计数组),其下标对应关键字的值,存储元素按待排序关键字的值统计的出现次数,然后再按元素关键字的值,结合统计数组,放回到最终位置上。常规的实现是使用一个辅助空间来有序存储原来的所有元素,再从辅助空间拷贝到原空间,而这个辅助空间大小至少和原空间一样大,因此这种实现很耗内存,它的好处在于算法是稳定的。为了减少内存占用和拷贝开销,进一步提高性能,本文讲述一种改进的方案,仅在原空间上移动数据就能达到排序效果,但牺牲了稳定性。为方便下文的讨论描述,设关键字取值范围为KeyRange,值域是闭区间[min,max],min为最小值,max为最大值,统计数组为CntArray。显然,这里关键字的类型是整型,在标准c/c++中,整型至少有char,unsigned char,short,unsigned short,int,unsigned int,long,unsigned long 8种,对于有符号整型,KeyRange中的min和(或)max会取负值,所以要映射到CntArray的下标0到max-min之间。

设计实现
   在算法设计封装上,为了支持在编译期或运行期给出关键字min和max的值,每种元素类型的实现有两种函数版本:对于运行期版本,考虑到当min和max的实际取值在较小的范围内,统计数组可以在栈而不是堆上分配,这样有助于一定的性能提升,因而使用了boost中的auto_buffer组件,为方便灵活配置auto_buffer的内部静态空间大小,因此在函数外部提供了接口以输入这个阈值(常量模板参数);对于编译期版本,为了代码重用,内部则是调用对应的运行期版本来实现的。关于统计数组的运用,其个数和空间大小则取决于因元素类型而不同的实现,这里元素类型分为三种:基本整型、类类型和指针类型,下面就这三种类型分别详述对应的算法实现。

   实现算法的函数名称为statistic_sort,对于不同的元素类型,函数所带的参数不同,类类型和指针类型比基本整型多了一个获取关键字方法的参数,这里的参数包括模板类型形参和函数调用形参,其内部实现则调用了辅助函数__init_index_array__aux_index_sort。
   1)基本整型:在这种情况下,元素本身就是关键字,CntArray每项存储的是下标值对应的元素出现的次数,空间大小是max-min+1,对应的运行期版本实现如下 
 1template<class _KeyT,class _RandIt>
 2void __init_index_array(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max,size_t* cnt)
 3{
 4    assert(_min <= _max);
 5    std::fill_n(cnt,_max-_min+1,0);
 6}

 7
 8template<class _KeyT,class _RandIt>
 9void __aux_index_sort(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max,size_t* cnt)
10{
11    typedef typename std::iterator_traits<_RandIt>::value_type value_type;
12    BOOST_STATIC_ASSERT((boost::is_same<_KeyT,value_type>::value));
13
14    for (_RandIt it = _first; it != _last; ++it)
15    {
16        assert(_min <= *it && *it <= _max);
17        ++cnt[*it-_min];
18    }

19    for (size_t i = 0,j = 0; i < _max - _min + 1++i)
20    {
21        while(cnt[i]--)    *(_first + (j++)) = i + _min;
22    }

23}

24
25template<class _KeyT,size_t N,class _RandIt>
26void statistic_sort(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max)
27{
28    using namespace boost::signals2::detail;
29    auto_buffer<size_t,store_n_objects<N> > cnt(_max-_min+1);
30
31    __init_index_array<_KeyT>(_first,_last,_min,_max,cnt.data());
32    __aux_index_sort<_KeyT>(_first,_last,_min,_max,cnt.data());
33}
   编译期版本如下 
 1template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt>
 2inline void __init_index_array(_RandIt _first,_RandIt _last,size_t* cnt)
 3{
 4    BOOST_STATIC_ASSERT(_min<=_max);
 5    __init_index_array(_first,_last,_min,_max,cnt);
 6}

 7
 8template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt>
 9void __aux_index_sort(_RandIt _first,_RandIt _last,size_t* cnt)
10{
11    BOOST_STATIC_ASSERT(_min<=_max);
12    __aux_index_sort(_first,_last,_min,_max,cnt);
13}

14
15template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt>
16void statistic_sort(_RandIt _first,_RandIt _last)
17{
18    size_t cnt[_max-_min+1];
19
20    __init_index_array<_KeyT,_min,_max>(_first,_last,cnt);
21    __aux_index_sort<_KeyT,_min,_max>(_first,_last,cnt);
22}
   从上面可看出,有两处使用了BOOST_STATIC_ASSERT宏在编译期检测减免不必要的错误,一是诊断关键字的取值范围是否合理,二是诊断迭代器指向的元素和关键字类型是否相同,这一技术在下面的代码中也多次用到。
   2)类类型:在这种情况下,用到了两个CntArray,一个是起始数组Beg,空间大小为max-min+2(其实下标max-min+1用不上),每项存储的是比对应关键字小的所有元素出现的次数,也就是关键字在序列中的起始索引;另一个是结束数组End,每项存储的是对应关键字的结束索引。这两个数组用来判断元素是否处于最终正确的位置上,如果是,那么就不移动元素,否则,要移动元素到End指示的位置上,在移动前,为防止覆盖目标位置上的元素,需临时保存目标位置处的元素和该元素对应的目标位置,继续这个过程,直到目标位置等于当前位置时停止。不同于基本整型,元素的关键字是元素的内部成员,需要通过一种方法来获取,而这种方法可以是自由普通函数,也可以是类的成员函数,还可以是函数对象,只要最终能满足调用规则即可,这个调用规则是返回关键字类型,带1个类型为元素常量引用的参数。对应的运行期版本实现如下    
 1template<class _KeyT,class _RandIt,class _Func>
 2void __init_index_array(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max,size_t* cnt_beg,size_t* cnt_end,_Func _getKey)
 3{
 4    typedef typename std::iterator_traits<_RandIt>::value_type value_type;
 5
 6    typedef typename boost::remove_pointer<_Func>::type F;
 7    typedef typename boost::function_traits<F>::result_type result_type;
 8    typedef typename boost::function_traits<F>::arg1_type arg_type;
 9    typedef typename boost::add_const<value_type>::type const_type;
10    typedef typename boost::add_reference<const_type>::type const_reference;
11
12    BOOST_STATIC_ASSERT((boost::is_same<result_type,_KeyT>::value));
13    BOOST_STATIC_ASSERT((boost::is_same<arg_type,const_reference>::value));
14
15    size_t N = _max - _min + 1;
16    std::fill_n(cnt_beg,N + 1,0);
17
18    for (_RandIt it = _first; it != _last; ++it)
19    {
20        assert(_min <= _getKey(*it) && _getKey(*it) <= _max);
21        ++cnt_beg[_getKey(*it) - _min + 1];
22    }

23    for (size_t i = 1;i < N;++i)
24    {
25        cnt_beg[i] += cnt_beg[i - 1];
26    }

27    std::copy(cnt_beg,cnt_beg + N,cnt_end);
28}

29
30template<class _KeyT,class _RandIt,class _Func>
31void __aux_index_sort(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max,size_t* cnt_beg,size_t* cnt_end,_Func _getKey)
32{
33    typedef typename std::iterator_traits<_RandIt>::value_type value_type;
34
35    typedef typename boost::remove_pointer<_Func>::type F;
36    typedef typename boost::function_traits<F>::result_type result_type;
37    typedef typename boost::function_traits<F>::arg1_type arg_type;
38    typedef typename boost::add_const<value_type>::type const_type;
39    typedef typename boost::add_reference<const_type>::type const_reference;
40
41    BOOST_STATIC_ASSERT((boost::is_same<result_type,_KeyT>::value));
42    BOOST_STATIC_ASSERT((boost::is_same<arg_type,const_reference>::value));
43
44    size_t  beg,end,pos,k;
45    value_type val,tmp_val;
46    _KeyT key,tmp_key;
47
48    for (_RandIt it = _first; it != _last; ++it)
49    {
50        val = *it;     key = _getKey(val);
51        assert(_min <= key && key <= _max);
52
53        beg = cnt_beg[key-_min],end = cnt_end[key-_min],pos = std::distance(_first,it);
54        if (pos < beg)
55        {
56            for (k = end; k != pos; k = cnt_end[tmp_key-_min],val = tmp_val)
57            {
58                tmp_val = *(_first + k); tmp_key = _getKey(tmp_val);
59                *(_first + k) = val; ++cnt_end[_getKey(val)-_min];
60            }

61            *(_first + k) = val; ++cnt_end[_getKey(val)-_min];
62        }

63        else if (pos == end)
64        {
65            ++cnt_end[key-_min];
66        }

67        else if (pos > end)
68            assert(false);
69    }

70}

71
72template<class _KeyT,size_t N,class _RandIt,class _Func>
73void statistic_sort(_RandIt _first,_RandIt _last,_KeyT _min,_KeyT _max,_Func _getKey)
74{
75    size_t len = _max - _min + 1;
76    using namespace boost::signals2::detail;
77    auto_buffer<size_t,store_n_objects<N> > cnt_beg(len + 1),cnt_end(len);
78
79    __init_index_array(_first,_last,_min,_max,cnt_beg.data(),cnt_end.data(),_getKey);
80    __aux_index_sort(_first,_last,_min,_max,cnt_beg.data(),cnt_end.data(),_getKey);
81}
   以上代码有两处用到了boost中的function_traits,一是来获取_getKey的返回类型,二是来获取_getKey的参数类型,并用BOOST_STATIC_ASSERT来诊断它们是否和预期的类型相同。由于function_traits尚不支持函数对象,为了支持使用类的成员函数这一方式来获取元素关键字,所以这里对它进行了特化,代码如下
 1namespace boost
 2{
 3    template<class _Result,class _Ty>
 4    struct function_traits<std::const_mem_fun_ref_t<_Result,_Ty> > 
 5    {
 6        typedef _Result result_type;
 7        typedef _Ty const& arg1_type;
 8    }
;
 9    template<class _Result,class _Ty>
10    struct function_traits<std::const_mem_fun_t<_Result,_Ty> > 
11    {
12        typedef _Result result_type;
13        typedef _Ty* const& arg1_type;
14    }
;
15}
   编译期版本实现如下
 1template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt,class _Func>
 2void __init_index_array(_RandIt _first,_RandIt _last,size_t* cnt_beg,size_t* cnt_end,_Func _getKey)
 3{
 4    BOOST_STATIC_ASSERT(_min <= _max);
 5    __init_index_array(_first,_last,_min,_max,cnt_beg,cnt_end,_getKey);
 6}

 7
 8template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt,class _Func>
 9void __aux_index_sort(_RandIt _first,_RandIt _last, size_t* cnt_beg,size_t* cnt_end,_Func _getKey)
10{
11    BOOST_STATIC_ASSERT(_min <= _max);
12    __aux_index_sort(_first,_last,_min,_max,cnt_beg,cnt_end,_getKey);
13}

14
15template<class _KeyT,_KeyT _min,_KeyT _max,class _RandIt,class _Func>
16void statistic_sort(_RandIt _first,_RandIt _last,_Func _getKey)
17{
18    size_t cnt_beg[_max - _min + 2], cnt_end[_max - _min + 1];
19
20    __init_index_array<_KeyT,_min,_max>(_first,_last,cnt_beg,cnt_end,_getKey);
21    __aux_index_sort<_KeyT,_min,_max>(_first,_last,cnt_beg,cnt_end,_getKey);
22}
   3)指针类型:包括基本整型和类类型指针,指针指向真正的元素,在这种情况下,其实现和类类型一样,只是获取关键字函数的参数类型为指针常量引用而已。
  从以上全部实现可以看出,算法并没有限制关键字的取值范围,而是由_min和_max决定,也就是说所谓的特定小范围依赖于实际应用,而这个范围的上限,理论上则取决于数组空间可支持的最大大小,只不过当范围相对元素个数较小时,具有良好的性能。

应用示例

 1//自定义类型
 2struct Item
 3{
 4    int key;
 5    int other;
 6
 7    int GetKey() const
 8    {
 9        return key;
10    }

11}
;
12//自由普通函数定义
13inline int GetObjKey(Item const& item)
14{
15    return item.key;
16}

17inline int GetPtrKey(Item* const& item)
18{
19    return item->key;
20}

21
22//支持数组,元素类型为int
23int p[100000];
24//在编译期指定关键字范围
25statistic_sort<int,-32768,32767>(p,p+sizeof(p)/sizeof(p[0]));
26//在运行期指定关键字范围
27statistic_sort<int,65536>(p,p+sizeof(p)/sizeof(p[0]),-32768,32767);
28
29//支持容器
30//元素类型为Item*,成员函数获取关键字,在运行期指定关键字范围
31vector<Item*> v1;
32statistic_sort<int,65536>(v1.begin(),v1.end(),-32768,32767,std::mem_fun(&Item::GetKey));
33
34//元素类型为Item,成员函数获取关键字,在编译期指定关键字范围
35vector<Item> v2;
36statistic_sort<int,-32768,32767>(v2.begin(),v2.end(),std::mem_fun_ref(&Item::GetKey));
37
38//自由普通函数获取关键字
39//元素类型为Item,在运行期指定关键字范围
40vector<Item> v3;
41statistic_sort<int,65536>(v3.begin(),v3.end(),-32768,32767,GetObjKey);
42//元素类型为Item*,在编译期指定关键字范围
43vector<Item*> v4;
44statistic_sort<int,-32768,32767>(v4.begin(),v4.end(),GetPtrKey);
   以上所有代码在vc2008和gcc4.6下编译通过,测试结果表明:
   ● 当元素类型为基本整型,且个数大于关键字取值范围较多时,statistic_sort比stl::sort快很多倍,用数组存储元素的比容器快。
   ● 当元素类型为类类型和指针类型时,性能还取决于获取关键字方法的实现,当机器直接支持高效获取关键字时(如位运算),则比快速排序要快,而用自由普通函数方式获取关键字的比类成员函数要快。
   ● 所有编译期版本比运行期要快。
posted on 2012-05-31 12:11 春秋十二月 阅读(1427) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理