Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2008年11月09日(日) GCJ準備

[]GCJテンプレート GCJテンプレートを含むブックマーク GCJテンプレートのブックマークコメント

前回日記を書いたときから一回も練習をしていないことに気づいた。

もうすぐそこに迫ってきているというのに。

テキサスに行ったときは

メダルを持ち帰ってきます、などと臆面もなく言っていたが、

今回はとてもじゃないが何も期待できない。

こんなに何もせずに勝てるわけないじゃない。


それはそれとして。

Round2のときにデュアルコアが使えてれば後一問通ったのに、と思って

Round3のときに準備したテンプレートでも公開してみることにする。

Round3が終わったときには、やっぱりプログラムはオーダーだ、

とか思って東京Local大会には持っていかなかったのだが、

計算機の気まぐれで通るという綱渡りになってしまったので、

Finalにはやっぱり持っていこうと思う。

あまり大きなテンプレートバグが入っていたら怖いから、

できれば避けたかった所なのだが致し方あるまい。

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>

#include <pthread.h>

using namespace std;

//-----

template <class T>
class parallel_scheduler{
public:
  parallel_scheduler(int cpu_num):cpu_num(cpu_num){
    T::init();
    init();
  }

  void go(){
    string line;getline(cin,line);
    int cases=atoi(line.c_str());
    for (int i=1;i<=cases;i++){
      T *t=new T();
      t->read();
      while (running>=cpu_num)
	usleep(10*1000);
      schedule(i,t);
    }
    while(running>0)
      usleep(10*1000);
  }

private:
  void init(){
    running=0;
    next=1;
    pthread_mutex_init(&run_m,NULL);
    pthread_mutex_init(&ans_m,NULL);
  }

  void schedule(int cn,T *t){
    pthread_mutex_lock(&run_m);
    running++;
    pthread_mutex_unlock(&run_m);

    pthread_t tid;
    pair<int,pair<T*,parallel_scheduler*> > *p=
      new pair<int,pair<T*,parallel_scheduler*> >(cn,make_pair(t,this));
    pthread_create(&tid,NULL,start,p);
    pthread_detach(tid);
  }

  static void *start(void *arg){
    pair<int,pair<T*,parallel_scheduler*> > *p=
      (pair<int,pair<T*,parallel_scheduler*> >*)arg;
    int cn=p->first;
    T *t=p->second.first;
    parallel_scheduler *ps=p->second.second;
    delete p;

    ostringstream oss;
    t->solve(oss);
    delete t;

    ps->register_ans(cn,oss.str());
    ps->end();

    return NULL;
  }

  void end(){
    pthread_mutex_lock(&run_m);
    running--;
    pthread_mutex_unlock(&run_m);
  }

  void register_ans(int cn,const string &ans){
    pthread_mutex_lock(&ans_m);
    anss.insert(make_pair(cn,ans));
    while(anss.count(next)!=0){
      cout<<"Case #"<<next<<": "<<anss[next]<<endl;
      anss.erase(next);
      next++;
    }
    pthread_mutex_unlock(&ans_m);
  }

  int cpu_num;
  int running;

  map<int,string> anss;
  int next;

  pthread_mutex_t run_m;
  pthread_mutex_t ans_m;
};

template <class T>
class sequential_scheduler{
public:
  sequential_scheduler(){
    T::init();
  }

  void go(){
    string line;getline(cin,line);
    int cases=atoi(line.c_str());
    for (int i=1;i<=cases;i++){
      T *t=new T();
      t->read();
      ostringstream oss;
      t->solve(oss);
      delete t;
      cout<<"Case #"<<i<<": "<<oss.str()<<endl;
    }
  }
};

//-----

class solver;

#define PARALLEL

int main(int argc,char *argv[])
{
#ifdef PARALLEL
  int cpu_num=2;
  if (argc==2) cpu_num=atoi(argv[1]);
  cerr<<"PAR: "<<cpu_num<<endl;
  parallel_scheduler<solver>(cpu_num).go();
#else
  cerr<<"SEQ:"<<endl;
  sequential_scheduler<solver>().go();
#endif
  return 0;
}

//-----

class solver{
public:
  solver(){
    // テストケースごとの初期化処理
  }
  ~solver(){
    // テストケースごとの終了処理
  }

  static void init(){
    // 全体の初期化処理
  }

  void read(){
    // テストケースをcinから読み込む
  }

  void solve(ostream &cout){
    // 解く。出力は引数のcoutに。
  }
};

スレッド数の指定と、万一の時のための自明コードによる逐次版を用意。

テストケースを読み込みながら、CPUが埋まっていなければそのテストケーススケジュールする。

埋まってたらどれかが空くまで待機。

出力はバッファして、先頭から順に確定し次第出力。

例外のこととか何も考えられていないな。だがそれがいい

さて、ライブラリを作る作業をせねば…。

トラックバック - http://d.hatena.ne.jp/tanakh/20081109