東方算程譚

Oriental Code Talk ── επιστημηが与太をこく、弾幕とは無縁のシロモノ。

目次

Blog 利用状況

ニュース

著作とお薦めの品々は

著作とお薦めの品々は
東方熱帯林へ。

あわせて読みたい

わんくま

  1. 東京勉強会#2
    C++/CLI カクテル・レシピ
  2. 東京勉強会#3
    template vs. generics
  3. 大阪勉強会#6
    C++むかしばなし
  4. 東京勉強会#7
    C++むかしばなし
  5. 東京勉強会#8
    STL/CLRによるGeneric Programming
  6. TechEd 2007 @YOKOHAMA
    C++・C++/CLI・C# 適材適所
  7. 東京勉強会#14
    Making of BOF
  8. 東京勉強会#15
    状態遷移
  9. 名古屋勉強会#2
    WinUnit - お気楽お手軽UnitTest

CodeZine

  1. Cで実現する「ぷちオブジェクト指向」
  2. CUnitによるテスト駆動開発
  3. SQLiteで組み込みDB体験(2007年版)
  4. C++/CLIによるCライブラリの.NET化
  5. C# 1.1からC# 3.0まで~言語仕様の進化
  6. BoostでC++0xのライブラリ「TR1」を先取りしよう (1)
  7. BoostでC++0xのライブラリ「TR1」を先取りしよう (2)
  8. BoostでC++0xのライブラリ「TR1」を先取りしよう (3)
  9. BoostでC++0xのライブラリ「TR1」を先取りしよう (4)
  10. BoostでC++0xのライブラリ「TR1」を先取りしよう (5)
  11. C/C++に対応した、もうひとつのUnitTestFramework ─ WinUnit
  12. SQLiteで"おこづかいちょう"
  13. STL/CLRツアーガイド
  14. マージ・ソート : 巨大データのソート法
  15. ヒープソートのアルゴリズム
  16. C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す
  17. .NETでマンデルブロ集合を描く
  18. .NETでマンデルブロ集合を描く(後日談)
  19. C++/CLI : とある文字列の相互変換(コンバージョン)
  20. インテルTBBによる選択ソートの高速化
  21. インテルTBB3.0 によるパイプライン処理
  22. Visual C++ 2010に追加されたSTLアルゴリズム
  23. Visual C++ 2010に追加されたSTLコンテナ「forward_list」
  24. shared_ptrによるObserverパターンの実装
  25. .NETでマンデルブロ集合を描く(番外編) ── OpenCLで超並列コンピューティング
  26. StateパターンでCSVを読む
  27. 状態遷移表からStateパターンを自動生成する
  28. 「ソートも、サーチも、あるんだよ」~標準C++ライブラリにみるアルゴリズムの面白さ
  29. インテルTBBの同期メカニズム
  30. なぜsetを使っちゃいけないの?
  31. WPFアプリケーションで腕試し ~C++でもWPFアプリを
  32. C++11 : スレッド・ライブラリひとめぐり
  33. Google製のC++ Unit Test Framework「Google Test」を使ってみる
  34. メールでデータベースを更新するココロミ
  35. Visitorパターンで遊んでみたよ
  36. Collection 2題:「WPFにバインドできる辞書」と「重複を許す検索set」
  37. Visual C++ 2012:stateless-lambdaとSQLiteのぷち拡張
  38. 「Visual C++ Compiler November 2012 CTP」で追加された6つの新機能

@IT

  1. Vista時代のVisual C++の流儀(前編)Vista到来。既存C/C++資産の.NET化を始めよう!
  2. Vista時代のVisual C++の流儀(中編)MFCから.NETへの実践的移行計画
  3. Vista時代のVisual C++の流儀(後編) STL/CLRによるDocument/Viewアーキテクチャ
  4. C++開発者のための単体テスト入門 第1回 C++開発者の皆さん。テスト、ちゃんとしていますか?
  5. C++開発者のための単体テスト入門 第2回 C++アプリケーションの効率的なテスト手法(CppUnit編)
  6. C++開発者のための単体テスト入門 第3回 C++アプリケーションの効率的なテスト手法(NUnit編)

AWARDS


Microsoft MVP
for Visual Developer - Visual C++


Wankuma MVP
for いぢわる C++


Nyantora MVP
for こくまろ中国茶

Xbox

Links

記事カテゴリ

書庫

日記カテゴリ

マルチスレッドに向かないバブルソートを無理くり…

ネタ元 → 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]
…ね♪

投稿日時 : 2009年12月19日 4:15

コメントを追加

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 8:58 なちゃ

これ、マルチスレッドで速くなっているだけではないですよね?
まあマルチスレッドの効果もあると思いますが。

ちなみにシングルコアで実行するとどの程度の時間になるでしょうか?
また、Nがもっと大きい場合などは、処理時間の変化の傾向はどうなるでしょうか?

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 9:02 なちゃ

推測では、
分割による計算量の変化で約2倍
デュアルコアの場合、マルチコアによる同時実行で約2倍
ってところに収束しますかね?
※もちろんオーバーヘッドで単純にこうはならないですが

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 10:55 こあら

> 一方が他方の処理終了を待ってなきゃいかんのでシングルスレッドと大差ない

2つのスレッドが一つの配列を(分割せずに)同時にバブルソートした場合、
(理想的には)2つめのスレッドは、1つめのスレッドが要素一つをソート済みの配列に対してソートを実行するわけだから、
実質二番目に並べる要素を処理することになります。
1つめのスレッドの次のループでは、実質三番目に並べる要素を処理する・・・

理想的過ぎますでしょうか?



もう一つ。(こちらはスケーラビリティなしですが)

「先頭から昇順」と「末尾から降順」の2スレッドを並列で動かすとどうなるかなー?って思いました。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 21:50 επιστημη

> マルチスレッドで速くなっているだけではないですよね?

です。バブルソートの時間計算量はΟ(N^2)なので要素数が半分になればかかる時間は1/4、
それをふたつやるので1/2、それにマージの分を追加となります。
ですからシングルスレッドならスピードは2倍弱となりますです。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 22:56 επιστημη

要素数を三倍に増やし、シングルスレッドのを追加したところ:

single : 1997 [ms]
single2: 905 [ms]
multi : 546 [ms]

となりました。
ふたつメのが予想より速いんだけど
まあ納得のいく結果でわないかと。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 23:26 なちゃ

おお、まあ概ね理屈どおりな感じですねー

>ふたつメのが予想より速いんだけど
int型30000個で120000バイトつまり120KB
L1キャッシュが64KBで120KBが半分になってたまたま全部キャッシュに乗るようになったとか。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/19 23:36 なちゃ

あ、でも普通は命令キャッシュとデータキャッシュで32KBずつか、だとするとちょうどってわけでもないですね。
まあ、キャッシュに丸ごと乗った状態での処理の割合が4分の1と16分の1くらいと考えると、それなりに違いは出てくるのかも。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/20 0:03 なちゃ

仮におおざっぱに、L1キャッシュに全部のってるときの処理速度がおよそ倍になると仮定してみると、
それぞれおよそ16分の1および4分の1が倍速になって、処理時間の割合はおおよそ
15.5:7(3.5*2)
15.5が1957msとすると7は901ms
うーん意外といい数字だ…

仮にデータ数を今の半分にすると、処理時間は約
900ms:260ms
辺りになると推測してみる。

# re: マルチスレッドに向かないバブルソートを無理くり&hellip; 2009/12/20 0:20 なちゃ

何度もすみません、ちょっと間違い
>900ms:260ms
じゃなくて
450ms:130ms
ですね。
あー最初の数値からみるとちょっと外れそうだ…
やっぱりそう単純にはいかなそうですね…

タイトル
名前
URL
コメント