ネタ元 →
Multi-Core と Multi-Thread のコメント:
どこまでをバブルソートと呼ぶかにもよるけど、交換の仕方を調整すると並列にできますよ、という例。
http://ja.wikipedia.org/wiki/奇偶転置ソート
ただ並列にする処理の1つ1つがとても小さいので、有意な差は出るかどうかは謎。
やってみよぉぢゃありませんか。
# いやさとっちゃんが急遽倍尺でやらんならんそぉなので、ネタ出しに協力的意味でｗｗｗ
1 7 6 5 8 2 4 3 があったとき、
[1] ふたつずつのペアをつくる。1 7 6 5 8 2 4 3
[2] それぞれのペアについて必要なら入れ替え 1 7 5 6 2 8 3 4
[3] ひとつずらしてペアをつくる 1 7 5 6 2 8 3 4
[4] それぞれのペアについて必要なら入れ替え1 5 7 2 6 3 8 4
[5] [1]～[4] をくりかえし。
[2],[4] の際、ペアの入れ替えは互いに独立だから並行処理できんぢゃん、と。
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <ppl.h>
#include <Windows.h>
using namespace std;
using namespace Concurrency;
// 単スレッドで地道にソート
void single_bubble_sort(int* data, int N) {
bool swapped;
auto swapper = [&](int i) {
if ( data[i] > data[i+1] ) {
iter_swap(data+i,data+i+1);
swapped = true;
}
};
do {
swapped = false;
for ( int i = 0; i < N-1; i += 2 ) { swapper(i); }
for ( int i = 1; i < N-1; i += 2 ) { swapper(i); }
} while ( swapped );
}
// PPLで並行処理
void multi_bubble_sort(int* data, int N) {
bool swapped;
auto swapper = [&](int i) {
if ( data[i] > data[i+1] ) {
iter_swap(data+i,data+i+1);
swapped = true;
}
};
do {
swapped = false;
parallel_for(0,N-1,2,swapper); // へーこー
parallel_for(1,N-1,2,swapper); // しょり
} while ( swapped );
}
int main() {
const int N = 10000;
int* src = new int[N];
iota(src, src+N, 10);
random_shuffle(src,src+N);
int* data = new int[N];
DWORD t0, t1;
copy(src,src+N,data);
t0 = GetTickCount();
single_bubble_sort(data,N);
t1 = GetTickCount();
assert( is_sorted(data,data+N) );
cout << (t1 - t0) << endl;
copy(src,src+N,data);
t0 = GetTickCount();
multi_bubble_sort(data,N);
t1 = GetTickCount();
assert( is_sorted(data,data+N) );
cout << (t1 - t0) << endl;
delete[] data;
delete[] src;
}
こいつを実行するとですね:
171 (single)
2855 (multi)
なんともトホホな結果です。処理単位があまりにちんこいために、
スレッド/タスクこしらえたり切り替えたりのコストをペイできんのですな。
# dual-coreでの結果です。octa-coreくらいになればちっとはマシかも。