hogloidのブログ

へなちょこ

GCJ multithread

これは何?
  • C++11以降で、GCJ形式(手元で複数ケースの計算をして提出するタイプの問題)の実行が数倍速くなる雛形
なんで速くなるの?
  • 最近のコンピュータは大抵コアが複数個ついてるので、複数テストケース(=完全に独立に並列で動かせる)なら同時に動かした方が速いため
  • 4コア8スレッドでは3~5倍程度の高速化が見込めます(i9やRyzen 7 以降ならもっと…)。一方ノートパソコン用CPUは2コア4スレッドやそれ以下が多いのであまり期待できません。

コンパイルオプション: g++ A.cpp -std=c++11 -pthread

#include <thread>
#include <vector>
#include <iostream>
using namespace std;
int Tnum;
class Main{
//変数・関数はここで定義
public:
  void input(){
//標準入力を受け取る
  }
  void operator()(){
//問題を解く
  }
  void output(){
//出力を行う
  }
};

const int MAX_T=105;
Main solver[MAX_T];
int main(){
  cin>>Tnum;
  for(int i=0;i<Tnum;++i){
    solver[i].input();
  }
  vector<thread> threads;
  for(int i=0;i<Tnum;++i){
    threads.push_back(thread(ref(solver[i])));
  }
  for(auto& t:threads){
    t.join();
  }
  for(int i=0;i<Tnum;++i){
    printf("Case #%d: ",i+1);
    solver[i].output();
  }
  return 0;
}

使用例(GCJ 2017 Round3 A問題)
(ちなみにこの問題、時間のかかるケースが2個ぐらいしか入っていないので、あまり速くなりません)

int Tnum;
class Main{
public:
  set<string> done;
  int len;
  int solve(string s){
    int tot=0;
    REP(i,len) tot+=s[i]-'0';
    if(tot>len) return 1;
    if(done.count(s)) return 0;
    done.insert(s);
    int res=1;

    string perm;
    REP(i,len){
      REP(t,s[i]-'0') perm+='1'+i;
    }
    REP(t,len-tot) perm+='0';
    sort(ALL(perm));
    do{
      res+=solve(perm);
    }while(next_permutation(ALL(perm)));
    return res;
  }
  string s_in;
  void input(){
    cin>>s_in;
  }
  int ans;
  void operator()(){
    len=s_in.size();
    ans=solve(s_in);
  }
  void output(){
    cout<<ans<<endl;
  }
};
const int MAX_T=105;
Main solver[MAX_T];
int main(){
  cin>>Tnum;
  for(int i=0;i<Tnum;++i){
    solver[i].input();
  }
  vector<thread> threads;
  for(int i=0;i<Tnum;++i){
    threads.pb(thread(ref(solver[i])));
  }
  for(auto& t:threads){
    t.join();
  }
  for(int i=0;i<Tnum;++i){
    printf("Case #%d: ",i+1);
    solver[i].output();
  }
  return 0;
}

参考:
std::thread::thread - C++入門
免責: GCJやその他コンテストでこれを使用した場合のいかなるトラブルについても責任を持ちません。