昨日のsortだけども、task schedulerなんか持ち出さなくても
parallel_doでやれるってことに気がついた。
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <cassert>
#include <tbb/tbb.h>
using namespace std;
template<typename InputIterator> inline
bool is_sorted(InputIterator first, InputIterator last) {
return adjacent_find(first, last, greater<iterator_traits<InputIterator>::value_type>()) == last;
}
// 単純選択ソート
template<typename InputIterator>
void selection_sort(InputIterator first, InputIterator last) {
while ( first != last ) {
iter_swap(first, min_element(first,last));
++first;
}
}
class sort_func {
public:
typedef vector<string>::iterator iterator;
typedef pair<iterator,iterator> range_type;
typedef vector<string>::difference_type difference_type;
protected:
static difference_type cutoff;
public:
void operator()(range_type range, tbb::parallel_do_feeder<range_type>& feeder) const {
difference_type size = distance(range.first, range.second);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(range.first, range.second);
} // さもなくば
else {
iterator mid = range.first;
advance(mid, size/2);
// 小さい要素群 と 大きい要素群 に振り分けて
nth_element(range.first, mid, range.second);
// それぞれを feeder に投げ込む
feeder.add(range_type(range.first,mid));
feeder.add(range_type(mid,range.second));
}
}
};
sort_func::difference_type sort_func::cutoff = 30;
int main() {
vector<string> source;
{
string value = "ABCDEFGH";
do {
source.push_back(value);
} while ( next_permutation(value.begin(), value.end()) );
assert( is_sorted(source.begin(), source.end()) );
random_shuffle(source.begin(), source.end());
}
{
cout << "quick sort ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
sort(input.begin(), input.end());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "sort_func ... " << flush;
vector<string> input = source;
sort_func::range_type range(input.begin(), input.end());
tbb::tick_count t = tbb::tick_count::now();
tbb::parallel_do(&range, &range+1, sort_func());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
}
実行結果:
quick sort ... 0.0685492 [sec]
sort_func ... 0.0577508 [sec]
おぉ、記録更新!