ネタ元 → Multi-Core と Multi-Thread
# わんくま同盟 東京勉強会 #39 の復讐復習ね。
Jittaさんのゆーとーり、複数の処理が互いに依存している場合マルチスレッド化はできない…
てゆーか、一方が他方の処理終了を待ってなきゃいかんのでシングルスレッドと大差ないわけで、
マルチスレッドによる効果が薄くなるす。
お互いの処理が依存せず、つまり待ち合わせ(同期/排他)がなく、勝手気ままにオノレの道を
突き進むことができるなら、マルチスレッド化すればコアの数だけ同時実行できるから
そりゃ速くなるわな、と。
ソート対象となる配列を前半と後半に分け、それぞれをソートする分には互いに干渉せず
ぶん回れますわね。ほんでもって、ソートされた前半と後半をマージすりゃソート完了。
C++ と PPL(Parallel Patterns Library) でやってみまひょ。
#include <iostream> // cout
#include <algorithm> // randum_shuffle, inplace_merge, etc.
#include <vector> // vector
#include <ppl.h> // parallel_invoke
#include <cassert> // assert
#include <windows.h> // GetTickCount
using namespace std;
using namespace Concurrency;
// バブるソート
template<typename Iterator>
void bubble_sort(Iterator first, Iterator last) {
Iterator lastSwapped = last;
--lastSwapped;
do {
Iterator limit = lastSwapped;
lastSwapped = first;
for ( Iterator i = first; i != limit; ++i ) {
if ( i[0] > i[1] ) {
iter_swap(i, i+1);
lastSwapped = i;
}
}
} while ( lastSwapped != first );
}
int main() {
const int N = 10000;
// 元ネタの準備
int* src = new int[N];
for ( int i = 0; i < N; ++i ) src[i] = i;
random_shuffle(src, src+N);
vector<int> data;
// 整列してればtrueを返す関数オブジェクト
auto in_order = [&]() {
return adjacent_find(data.begin(), data.end(),
[](int x, int y) { return x > y;}) == data.end();
};
{ // ふつーにバブる
data.assign(src,src+N);
DWORD t = GetTickCount();
bubble_sort(data.begin(), data.end());
cout << "single: " << GetTickCount() - t << " [ms]\n";
assert( in_order() ); // ソートできたかな?
}
{ // 前半と後半を同時にバブり、しかるのちマージ
data.assign(src,src+N);
DWORD t = GetTickCount();
// PPL使ってふたついっぺんに実行!
parallel_invoke(
[&](){ bubble_sort(data.begin(), data.begin()+N/2); },
[&](){ bubble_sort(data.begin()+N/2, data.end()); }
);
// マージして一本にする
inplace_merge(data.begin(), data.begin()+N/2, data.end());
cout << "multi : " << GetTickCount() - t << " [ms]\n";
assert( in_order() ); // ソートできたかな?
}
delete[] src;
return 0;
}
実行結果:
single: 219 [ms]
multi : 93 [ms]
…ね♪