基本原理 在數(shù)據(jù)輸入隨機(jī)分布的情況下，快速排序具有較好的性能表現(xiàn)，但當(dāng)元素個(gè)數(shù)比其關(guān)鍵字的取值范圍大，而這個(gè)范圍相對(duì)較小時(shí)，使用一種關(guān)鍵字索引統(tǒng)計(jì)排序會(huì)快很多，因?yàn)樗臅r(shí)間復(fù)雜度是線性的，基本原理是使用數(shù)組（為描述方便，特稱(chēng)統(tǒng)計(jì)數(shù)組），其下標(biāo)對(duì)應(yīng)關(guān)鍵字的值，存儲(chǔ)元素按待排序關(guān)鍵字的值統(tǒng)計(jì)的出現(xiàn)次數(shù)，然后再按元素關(guān)鍵字的值，結(jié)合統(tǒng)計(jì)數(shù)組，放回到最終位置上。常規(guī)的實(shí)現(xiàn)是使用一個(gè)輔助空間來(lái)有序存儲(chǔ)原來(lái)的所有元素，再?gòu)妮o助空間拷貝到原空間，而這個(gè)輔助空間大小至少和原空間一樣大，因此這種實(shí)現(xiàn)很耗內(nèi)存，它的好處在于算法是穩(wěn)定的。為了減少內(nèi)存占用和拷貝開(kāi)銷(xiāo)，進(jìn)一步提高性能，本文講述一種改進(jìn)的方案，僅在原空間上移動(dòng)數(shù)據(jù)就能達(dá)到排序效果，但犧牲了穩(wěn)定性。為方便下文的討論描述，設(shè)關(guān)鍵字取值范圍為KeyRange，值域是閉區(qū)間[min,max]，min為最小值，max為最大值，統(tǒng)計(jì)數(shù)組為CntArray。顯然，這里關(guān)鍵字的類(lèi)型是整型，在標(biāo)準(zhǔn)c/c++中，整型至少有char,unsigned char,short,unsigned short,int,unsigned int,long,unsigned long 8種，對(duì)于有符號(hào)整型，KeyRange中的min和（或）max會(huì)取負(fù)值，所以要映射到CntArray的下標(biāo)0到max-min之間。
設(shè)計(jì)實(shí)現(xiàn)
在算法設(shè)計(jì)封裝上，為了支持在編譯期或運(yùn)行期給出關(guān)鍵字min和max的值，每種元素類(lèi)型的實(shí)現(xiàn)有兩種函數(shù)版本：對(duì)于運(yùn)行期版本，考慮到當(dāng)min和max的實(shí)際取值在較小的范圍內(nèi)，統(tǒng)計(jì)數(shù)組可以在棧而不是堆上分配，這樣有助于一定的性能提升，因而使用了boost中的auto_buffer組件，為方便靈活配置auto_buffer的內(nèi)部靜態(tài)空間大小，因此在函數(shù)外部提供了接口以輸入這個(gè)閾值（常量模板參數(shù)）；對(duì)于編譯期版本，為了代碼重用，內(nèi)部則是調(diào)用對(duì)應(yīng)的運(yùn)行期版本來(lái)實(shí)現(xiàn)的。關(guān)于統(tǒng)計(jì)數(shù)組的運(yùn)用，其個(gè)數(shù)和空間大小則取決于因元素類(lèi)型而不同的實(shí)現(xiàn)，這里元素類(lèi)型分為三種：基本整型、類(lèi)類(lèi)型和指針類(lèi)型，下面就這三種類(lèi)型分別詳述對(duì)應(yīng)的算法實(shí)現(xiàn)。
實(shí)現(xiàn)算法的函數(shù)名稱(chēng)為statistic_sort，對(duì)于不同的元素類(lèi)型，函數(shù)所帶的參數(shù)不同，類(lèi)類(lèi)型和指針類(lèi)型比基本整型多了一個(gè)獲取關(guān)鍵字方法的參數(shù)，這里的參數(shù)包括模板類(lèi)型形參和函數(shù)調(diào)用形參，其內(nèi)部實(shí)現(xiàn)則調(diào)用了輔助函數(shù)__init_index_array和__aux_index_sort。 1）基本整型：在這種情況下，元素本身就是關(guān)鍵字，CntArray每項(xiàng)存儲(chǔ)的是下標(biāo)值對(duì)應(yīng)的元素出現(xiàn)的次數(shù)，空間大小是max-min+1，對(duì)應(yīng)的運(yùn)行期版本實(shí)現(xiàn)如下
1
template<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} 編譯期版本如下
1
template<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宏在編譯期檢測(cè)減免不必要的錯(cuò)誤，一是診斷關(guān)鍵字的取值范圍是否合理，二是診斷迭代器指向的元素和關(guān)鍵字類(lèi)型是否相同，這一技術(shù)在下面的代碼中也多次用到。 2）類(lèi)類(lèi)型：在這種情況下，用到了兩個(gè)CntArray，一個(gè)是起始數(shù)組Beg，空間大小為max-min+2（其實(shí)下標(biāo)max-min+1用不上），每項(xiàng)存儲(chǔ)的是比對(duì)應(yīng)關(guān)鍵字小的所有元素出現(xiàn)的次數(shù)，也就是關(guān)鍵字在序列中的起始索引；另一個(gè)是結(jié)束數(shù)組End，每項(xiàng)存儲(chǔ)的是對(duì)應(yīng)關(guān)鍵字的結(jié)束索引。這兩個(gè)數(shù)組用來(lái)判斷元素是否處于最終正確的位置上，如果是，那么就不移動(dòng)元素，否則，要移動(dòng)元素到End指示的位置上，在移動(dòng)前，為防止覆蓋目標(biāo)位置上的元素，需臨時(shí)保存目標(biāo)位置處的元素和該元素對(duì)應(yīng)的目標(biāo)位置，繼續(xù)這個(gè)過(guò)程，直到目標(biāo)位置等于當(dāng)前位置時(shí)停止。不同于基本整型，元素的關(guān)鍵字是元素的內(nèi)部成員，需要通過(guò)一種方法來(lái)獲取，而這種方法可以是自由普通函數(shù)，也可以是類(lèi)的成員函數(shù)，還可以是函數(shù)對(duì)象，只要最終能滿足調(diào)用規(guī)則即可，這個(gè)調(diào)用規(guī)則是返回關(guān)鍵字類(lèi)型，帶1個(gè)類(lèi)型為元素常量引用的參數(shù)。對(duì)應(yīng)的運(yùn)行期版本實(shí)現(xiàn)如下
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，一是來(lái)獲取_getKey的返回類(lèi)型，二是來(lái)獲取_getKey的參數(shù)類(lèi)型，并用BOOST_STATIC_ASSERT來(lái)診斷它們是否和預(yù)期的類(lèi)型相同。由于function_traits尚不支持函數(shù)對(duì)象，為了支持使用類(lèi)的成員函數(shù)這一方式來(lái)獲取元素關(guān)鍵字，所以這里對(duì)它進(jìn)行了特化，代碼如下
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} 編譯期版本實(shí)現(xiàn)如下
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）指針類(lèi)型：包括基本整型和類(lèi)類(lèi)型指針，指針指向真正的元素，在這種情況下，其實(shí)現(xiàn)和類(lèi)類(lèi)型一樣，只是獲取關(guān)鍵字函數(shù)的參數(shù)類(lèi)型為指針常量引用而已。 從以上全部實(shí)現(xiàn)可以看出，算法并沒(méi)有限制關(guān)鍵字的取值范圍，而是由_min和_max決定，也就是說(shuō)所謂的特定小范圍依賴于實(shí)際應(yīng)用，而這個(gè)范圍的上限，理論上則取決于數(shù)組空間可支持的最大大小，只不過(guò)當(dāng)范圍相對(duì)元素個(gè)數(shù)較小時(shí)，具有良好的性能。
應(yīng)用示例
1//自定義類(lèi)型
2struct Item
3{
4 int key;
5 int other;
6
7 int GetKey() const
8 {
9 return key;
10 }
11};
12//自由普通函數(shù)定義
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//支持?jǐn)?shù)組,元素類(lèi)型為int
23int p[100000];
24//在編譯期指定關(guān)鍵字范圍
25statistic_sort<int,-32768,32767>(p,p+sizeof(p)/sizeof(p[0]));
26//在運(yùn)行期指定關(guān)鍵字范圍
27statistic_sort<int,65536>(p,p+sizeof(p)/sizeof(p[0]),-32768,32767);
28
29//支持容器
30//元素類(lèi)型為Item*,成員函數(shù)獲取關(guān)鍵字,在運(yùn)行期指定關(guān)鍵字范圍
31vector<Item*> v1;
32statistic_sort<int,65536>(v1.begin(),v1.end(),-32768,32767,std::mem_fun(&Item::GetKey));
33
34//元素類(lèi)型為Item,成員函數(shù)獲取關(guān)鍵字,在編譯期指定關(guān)鍵字范圍
35vector<Item> v2;
36statistic_sort<int,-32768,32767>(v2.begin(),v2.end(),std::mem_fun_ref(&Item::GetKey));
37
38//自由普通函數(shù)獲取關(guān)鍵字
39//元素類(lèi)型為Item,在運(yùn)行期指定關(guān)鍵字范圍
40vector<Item> v3;
41statistic_sort<int,65536>(v3.begin(),v3.end(),-32768,32767,GetObjKey);
42//元素類(lèi)型為Item*,在編譯期指定關(guān)鍵字范圍
43vector<Item*> v4;
44statistic_sort<int,-32768,32767>(v4.begin(),v4.end(),GetPtrKey); 以上所有代碼在vc2008和gcc4.6下編譯通過(guò)，測(cè)試結(jié)果表明： ● 當(dāng)元素類(lèi)型為基本整型，且個(gè)數(shù)大于關(guān)鍵字取值范圍較多時(shí)，statistic_sort比stl::sort快很多倍，用數(shù)組存儲(chǔ)元素的比容器快。 ● 當(dāng)元素類(lèi)型為類(lèi)類(lèi)型和指針類(lèi)型時(shí)，性能還取決于獲取關(guān)鍵字方法的實(shí)現(xiàn)，當(dāng)機(jī)器直接支持高效獲取關(guān)鍵字時(shí)（如位運(yùn)算），則比快速排序要快，而用自由普通函數(shù)方式獲取關(guān)鍵字的比類(lèi)成員函數(shù)要快。 ● 所有編譯期版本比運(yùn)行期要快。
posted on 2012-05-31 12:11
春秋十二月 閱讀(1808)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
Algorithm