doubleのRadixSort
バケットソートの欠点を補える基数ソート(RadixSort)
バケットソートは計算量O(N)の素晴らしい必殺技ですが、
如何せんバケツのサイズに限度があり、用途が限定されます。
この問題を、痛みを伴いながら一部解決できる方法として、基数ソートが上げられます。
doubleの配列を基数ソートで
この基数ソートをdoubleの配列に適用してみようという今回の試み。
doubleの配列を1バイト毎にバケットソートすれば、なんと配列のソートが完成するというものです。
素直に実装してみるとこのような感じになりました。
ターゲットはIEEEのreal*8、ソースはlittle-endian依存です。
union DataDouble { double d; u_char c[8]; }; typedef std::list<DataDouble> List ; typedef List::const_iterator ListIter ; typedef std::array<List, 256> Array ; typedef Array::iterator ArrayIter ; void RadixSort( std::vector<double>& array ) { size_t size = array.size() ; // byte毎の操作用に共用体に移し替え std::vector<DataDouble> target ; target.resize(size) ; for ( size_t i = 0 ; i < size ; ++i ) { target[i].d = array[i] ; } //1byte毎にバケットソート Array box; size_t digit = 8 ; size_t minusStartIndex = 0; for ( size_t i = 0 ; i < digit ; ++i ) { for ( auto j : target ) { box[j.c[i]].push_back(j) ; } size_t count = 0 ; for ( ArrayIter aIt = box.begin(), aEnd = box.end() ; aIt != aEnd ; ++aIt ) { for ( ListIter lIt = aIt->begin(), lEnd = aIt->end() ; lIt != lEnd ; ++lIt ) { if ( ( i == digit - 1 ) && ( lIt->c[i] & 0x80 ) && minusStartIndex == 0 ) { minusStartIndex = count; } target[count++] = *lIt ; } aIt->clear() ; } } //負値を考慮 std::reverse( target.begin(), target.begin() + minusStartIndex ); std::reverse( target.begin(), target.end() ); for ( size_t i = 0 ; i < size ; ++i ) { array[i] = target[i].d ; } }
さて、ここから高速化にトライ?