先日の combsort 、比較/交換する要素間の距離(gap)をぢわぢわ縮めていく
bubblesort の改良版なわけですが。
どのくらいずつ縮めていくか、 つまり gap = gap / ratio; における ratio は
実験的に 1.3 だという。ホントかしら? ってんでやってみた。
template<typename Iterator>
void combsort(Iterator first, Iterator last, double gap_ratio) {
auto gap = std::distance(first,last); // 要素間の距離:最初は要素数から
Iterator iter1, iter2;
bool swapped;
do {
gap = gap / gap_ratio; // ちょびっと狭める
if ( gap == 0 ) gap = 1;
swapped = false;
Iterator iter1 = first;
Iterator iter2 = first;
std::advance(iter2,gap); // iter1,iter2間をgapだけ離す
while ( iter2 != last ) { // これ以降はbubblesortと同じね
if ( *iter2 < *iter1 ) {
swapped = true;
std::iter_swap(iter1,iter2);
}
++iter1;
++iter2;
}
} while (swapped || gap != 1);
}
void random_test() {
const int N = 50000;
array<int,N> source;
array<int,N> target;
iota(source.begin(), source.end(), 0); // [0..N) の配列を用意
map<int,double> hist;
const int trial = 10;
for ( int t = 0; t < trial; ++t ) {
random_shuffle(source.begin(), source.end()); // ぐちょぐちょにかき混ぜて
double time;
for ( int i = 110; i < 140; ++i ) {
double ratio = i / 100.0;
copy(source.begin(), source.end(), target.begin());
{
orz::ScopedWatch watch(time);
combsort(target.begin(), target.end(), ratio); // 昆布ソート
}
if ( is_sorted(target.begin(),target.end()) ) {
hist[i] += time; // 所要時間を積算
} else {
cout << "oops. disordered!" << endl;
return;
}
}
}
// 平均値を出力
for ( int i = 120; i < 140; ++i ) {
cout << "ratio= " << i/100.0 << " time=" << hist[i]/trial << endl;
}
}
結果:
ratio= 1.2 time=6.64967
ratio= 1.21 time=6.56539
ratio= 1.22 time=6.37233
ratio= 1.23 time=6.56348
ratio= 1.24 time=6.18083
ratio= 1.25 time=6.18782
ratio= 1.26 time=6.25421
ratio= 1.27 time=6.07581
ratio= 1.28 time=6.26599
ratio= 1.29 time=6.02135
ratio= 1.3 time=6.55121
ratio= 1.31 time=6.80597
ratio= 1.32 time=6.47621
ratio= 1.33 time=6.12299
ratio= 1.34 time=6.59149
ratio= 1.35 time=13.3166
ratio= 1.36 time=20.2281
ratio= 1.37 time=34.2606
ratio= 1.38 time=54.2303
ratio= 1.39 time=64.2049
ふむ、この場合に限って言えば 1.29 のときが最速。
1.33のあたりにヘコみがあるのも面白いですな。
とはいえ 1.3近傍が実験的によさげな値なのは確かなようです。