Visual C++ 2010に追加されたSTLアルゴリズム@CodeZine で忘れてたのがありました。
■ minmax_element
template<class Iterator, class Predicate>
std::pair<Iterator,Iterator>
minmax_element(Iterator first, Iterator last, Predicate pred);
シーケンス[first,last)から、最初に見つけた最小要素 と 最後に見つけた最大要素 を指すイテレータをペアにして返します。
最小/最大要素を見つけてくれるアルゴリズムはそれぞれmin_element/max_elementがあるんだけど、minmax_elementはそいつらの合わせ技。
大きなメリットはmin_element,max_elementを一度ずつ呼び出すより速いす。要素数Nに対し3/2N程度だそうで、前者の2Nに比べて25%ほどの時短となるます。
コレ使って単純選択ソートをちょびっと速くします。単純選択ソートのアルゴリズムはめっちゃ単純:
「i=0..N-1に対し、data[i]～data[N-1]中の最少要素とdata[i]を交換する」こんだけ。コード書けば:
while ( first != last ) {
iter_swap(first, min_element(first,last));
++first;
}
loop回るたんびに未ソートな要素がいっこずつ減ってくんだから、minmax_elementならふたっつずつ減ってくれんでないのん? と。
ってなわけで書いてみた。ソート対象は挿入/削除がチョー速いlist<T>で。
#include <iostream>
#include <array>
#include <list>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <windows.h>
using namespace std;
// フツーの単純選択ソート
DWORD min_selection_sort(list<int>& data) {
DWORD t = GetTickCount();
for ( auto first = data.begin(); first != data.end(); ++first ) {
iter_swap(first,min_element(first,data.end()));
}
return GetTickCount() - t;
}
// ヒネクレた単純選択ソート
DWORD minmax_selection_sort(list<int>& data) {
DWORD t = GetTickCount();
list<int> smaller, bigger;
while ( !data.empty() ) {
auto mm_pair = minmax_element(data.begin(),data.end());
smaller.splice(smaller.end(), data, mm_pair.first);
if ( mm_pair.first != mm_pair.second ) {
bigger.splice(bigger.begin(), data, mm_pair.second);
}
}
data.splice(data.begin(),bigger);
data.splice(data.begin(),smaller);
return GetTickCount() - t;
}
int main() {
const int N = 20000;
array<int,N> src;
iota(src.begin(),src.end(),0);
random_shuffle(src.begin(),src.end());
DWORD t;
list<int> data;
data.assign(src.begin(),src.end());
t = min_selection_sort(data);
assert( is_sorted(data.begin(), data.end()));
cout << t << endl;
data.assign(src.begin(),src.end());
t = minmax_selection_sort(data);
assert( is_sorted(data.begin(), data.end()));
cout << t << endl;
}
実行結果:
1092 (min_selection)
967 (minmax_selection)
一割ちょいかー、けっこーややこしくなってっから、こんなもんかなー
もっとエレガントな実装がありそな希ガス。