> バブルソートを並列化（ひとつの配列に対して、複数のスレッドがそれぞれバブルソートを実行）したら、ソート全体の計算量はn倍に増えますが、入れ換えの回数は変わらず、入れ換えを並列で処理できる分だけ、ソート全体の処理時間は短くなるように思います。
はい。もし、スレッドの切り替えに時間がかからないのであれば、そうなるでしょう。
ところが、実際には、スレッドの切り替えにはコストがかかります。また、実際に並列動作するのは、CPU のパイプライン並列化と違って、コア数の数に限られます。前のエントリーで検証したように、コア数+1～2を超えると、スレッド切り替えのコストの方が多くなることがあります。
http://blogs.wankuma.com/jitta/archive/2009/10/21/182308.aspx
> 自分がわからないのは、その検証をどこまでまじめにやろうとしているのか、です。
今回のエントリは、「マルチ スレッドでやる」ことを前提としておらず、「マルチ スレッドにむかないアルゴリズムがある」ことを検証することです。何らかの処理を、処理スピードを上げる必要があるなら、ほかのアプローチをすると思います。
つまり、「マルチ スレッドにむかないアルゴリズムは、何かあるかな？バブル ソートなんてどうだろう」というアプローチでした。これが、「ソートを、できるだけ速く、CPU を効率的に使ってやりたい」であれば、他のアルゴリズムを探すでしょう。
> しかしこんな時間でも Service Unavailable になるのか…orz
ほかのエントリーに、海外からスパム コメントがついているので、そういう関係かとorz
投稿日時 : 2009年12月20日 23:02