C++11 : スレッド・ライブラリひとめぐり

// nは素数?
bool is_prime(int n) {
  for ( int i = 2; i < n; ++i ) {
    if ( n % i == 0 ) {
      return false;
    }
  }
  return true;
}

// lo以上hi未満の範囲に素数はいくつある?
int count_prime(int lo, int_hi) {
  int result = 0;
  for ( int i = lo; i < hi; ++i ) {
    if ( is_prime(i) ) {
      ++result;
    }
  }
  return result;
}

/* 
 * M未満の素数はいくつある?
 */
void single(int M) {
  chrono::system_clock::time_point start = chrono::system_clock::now();
  int result = count_prime(2,M);
  chrono::duration<double> sec = chrono::system_clock::now() - start;
  cout << result << ' ' << sec.count() << "[sec]" << endl;
}

int main() {
  const int M = 100000;
  single(M);
}

/* 実行結果:
9592 1.64009[sec]
*/

#ifndef DIV_RANGE_H_
#define DIV_RANGE_H_

// [lo,hi) を n等分する
template<typename T =int>
class div_range {
private:
  T lo_;
  T hi_;
  T stride_;
  int n_;
public:
  div_range(T lo, T hi, int n) 
    : lo_(lo), hi_(hi), n_(n) { stride_ = (hi-lo)/n; }
  T lo(int n) const { return lo_ + stride_ * n; }
  T hi(int n) const { return (++n < n_) ? lo_ + stride_*n : hi_; }
};
#endif

/* Win32 thread のためのwrapper */

// <0>:loi, <1>:hi , <1>:result
typedef tuple<int,int,int> thread_io;

DWORD WINAPI thread_entry(LPVOID argv) {
  thread_io& io = *static_cast<thread_io*>(argv);
  get<2>(io) = count_prime(get<0>(io), get<1>(io));
  return 0;
}

/* 
 * M未満の素数はいくつある?
 */
void multi(int M, int nthr) {
  vector<HANDLE> handle(nthr);
  vector<thread_io> io(nthr);
  div_range<> rng(2,M,nthr);

  for ( int i = 0; i< nthr; ++i ) {
    io[i] = thread_io(rng.lo(i), rng.hi(i), 0);
  }

  chrono::system_clock::time_point start = chrono::system_clock::now();
  for ( int i = 0; i< nthr; ++i ) {
    handle[i] = CreateThread(NULL, 0, &thread_entry, &io[i], 0, NULL);
  }
  WaitForMultipleObjects(nthr, &handle[0], TRUE, INFINITE);
  chrono::duration<double> sec = chrono::system_clock::now() - start;

  int result = 0;
  for ( int i = 0; i < nthr; ++i ) {
    CloseHandle(handle[i]);
    result += get<2>(io[i]);
  }
  cout << result << ' ' << sec.count() << "[sec] : " << nthr << endl;
}

int main() {
  const int M = 100000;
  for ( int i = 1; i < 10; ++i ) multi(M, i);
}

/* 実行結果:
9592 1.6651[sec] : 1
9592 1.21607[sec] : 2
9592 0.970055[sec] : 3
9592 0.752043[sec] : 4
9592 0.631036[sec] : 5
9592 0.52903[sec] : 6
9592 0.549031[sec] : 7
9592 0.497028[sec] : 8
9592 0.470027[sec] : 9
*/