ぼうメモ帳

2004-06-25 酒だ、酒!!

JavaDoc

| JavaDocを含むブックマーク

いま作ってるツールのソースコメントを整備しています。もう2ヶ月近くコメントには手付かずだったので、ソースとの乖離が…

同期を取るために2時間ぐらいがんばったんだけど、力尽きました。明日一日つぶさないとダメかなあ。

早いとこドキュメントを公開しないといけないし、でも、進捗報告書も書かないといけないし、研究も進めないといけないし、土日は徹夜か。

Java GUIプログラミング Vol.3

| Java GUIプログラミング Vol.3を含むブックマーク

ISBN:4877830537

キター!!

第一巻から2年半たって、やっとでた第三巻。たしか第一巻の帯には、2ヶ月ごとに刊行と書いてあったのに、もはやでないとさえ思っていたら、よりにもよってこんな忙しい時期にでるなんて、現実逃避のネタができました。

学部時代に予約したこと、売店の記録に残ってるかなあ。

トラックバック - http://d.hatena.ne.jp/susumu/20040625

2004-06-22 ヒキコモリな生活

注文してた本が届いた

| 注文してた本が届いたを含むブックマーク

今までプログラミングの本ばかり買っていたけど、来年からSEとして働くことになると思うので(理系院を出てSEか、鬱だ)、ネットワークデータベースに関する本をチョコチョコと読み始めることにする。と思って、ネタも兼ねてSoftEther本を買ってはみたものの、蓋を開けてみればただの説明書だったからちと鬱。

トラックバック - http://d.hatena.ne.jp/susumu/20040622

2004-06-20 日曜日の夜は。。。

日曜日の夜は愚痴が多くなる

日曜日の夜は愚痴が多くなるを含むブックマーク

コンピュータ理工学を専攻している学生(学部生)、40人中、まともにmalloc/freeを扱えるのが2名のみって、うちの大学生ってやっぱりダメダメなんだなと実感した一日でした。

一番多いミスが、freeしない。次に多いミスが、freeをする場所が違う、あとはfreeをする順番が違う、インデクシングとの複合技などなど。これでもハードの学生かと…

トラックバック - http://d.hatena.ne.jp/susumu/20040620

2004-06-17 二日酔いでだるい

決まりました

| 決まりましたを含むブックマーク

半年近い就職活動の結果、IT関連の会社(俗に言うSIer)で来年から働くことになりました。長かった就職活動もやっと終わり。やっとこさ人生の折り返し地点を迎えられそうです。

金沢大会WEB予選問題D

| 金沢大会WEB予選問題Dを含むブックマーク

http://ccserv.adm.ehime-u.ac.jp/ICPC/problems/domestic/d2002/problems/D.html

今日、コーチを引き受けているチーム(といっても、私はチームの登録をしただけで指導とかは何もしてない)から、実行効率の良いアルゴリズムについてのアイディアはないかという質問を受けたので、1年ぶりにACM関連の問題についてまじめに取り組んでみる。

問題の内容は、0〜9までの数字を使って、ヒット&ブローをやるとき、トライした数列に関するヒットとブローの数から、正しい答えを推測するプログラムを書けというもの。

問題の桁数と、トライした回数、トライした数列とそのときのヒット&ブローの数が入力として与えられる。そして、そのヒントから推測される答えを出力する。このとき、答えが1つに絞りきれない場合はNOを出力する。

単純な全探査アルゴリズムは、全部の順列を生成しながら、すべてのトライした数列とのヒットとブローの数を求めて、これが入力のヒットとブローの数と一致しているかをしらべる。すべて一致していた場合、その数列は推測される答えとなる。

これは、最大10! = 3628800個の数列を調べなければならず、とにかく実行時間が掛かる。私のノートPCで実際に動かしてみたところ(centrino1.3GHz)、データセット1を解くのに40秒、データセット2を解くのに48秒かかった。これではちと時間がかかりすぎて、恥ずかしい。

さて、全部の順列について調べつくす全探査では効率が悪すぎるので、数列生成途中でヒントと照らし合わせるという枝狩りを仕込んでみた。すると、データセット1、データセット2とも3秒掛からない時間で解くことができた。

ま、こんなもんか。

#include <stdio.h>

struct a {
  char word[11];
  int  usage[11];
  int  hit;
  int  blow;
} hints[100];

int size, num;

int update( char lastanswer[ ], char current[ ], int usage[ ], int index )
{
  int i, flag=0;
  int ans = 0;

  for( i=0; i<num; i++ ){
    if( hints[i].word[index] == current[index] )
      hints[i].hit--;
    else if( hints[i].usage[ current[index]-'0'] == 1 )
      hints[i].blow--;
    if( hints[i].hit < 0 || hints[i].blow < 0 )
      flag = 1;
  }
  if( flag == 0 )
    ans = allpat( lastanswer, current, usage, index+1 );
  if( ans > 1 ) return ans;
  
  for( i=0; i<num; i++ ){
    if( hints[i].word[index] == current[index] )
      hints[i].hit++;
    else if( hints[i].usage[ current[index]-'0'] == 1 )
      hints[i].blow++;
  }

  return ans;
}

/* 順列を生成しつつ、ヒントを更新しながら探索を行う */
int allpat( char lastanswer[ ], char current[ ], int usage[], int index )
{
  int i, ans = 0;

  /* 数列が生成途中なら、生成を継続する */
  if( index < size ){
    for( i=0; i<10; i++ ){
      if( usage[i] == 1 ) continue;
      current[index] = '0' + i;
      current[index+1] = '\0';
      usage[i] = 1;
      ans += update( lastanswer, current, usage, index );
      usage[i] = 0;
      if( ans > 1 ) break;
    }
  }
  else {
    /* 順列生成が完了したら、正しいかどうかを調べる */
    for( i=0; i<num; i++ ){
      if( hints[i].hit != 0 || hints[i].blow != 0 )
        break;
    }
    if( i==num ){
      strcpy( lastanswer, current );
      ans++;
    }
  }

  return ans;

}

int search( char answer[ ] )
{
  char current[11];
  int usage[11];
  int ans;

  memset( answer, 0, 11 );
  memset( current, 0, 11 );
  memset( usage, 0, sizeof(usage) );

  ans = allpat( answer, current, usage, 0 );
  if( ans == 1 ) return 0;
  else return 1;
}

int main( int argc, char *argv[ ] )
{
  int i, j;
  int s;
  char answer[11];

  for(;;){
    /* L H の入力 */
    scanf( "%d %d", &size, &num );
    if( size == 0 || num == 0 ) break;

    /* Hintsの入力 */
    for( i=0; i<num; i++ ){
      scanf( "%s %d %d", hints[i].word, &hints[i].hit, &hints[i].blow );
      /* Hintsから、使われている文字について調べる */
      for(j=0; j<10; j++)
        hints[i].usage[j] = 0;
      for(j=0; hints[i].word[j]!='\0'; j++ )
        hints[i].usage[ hints[i].word[j]-'0' ] = 1;
    }
    
    s = search( answer );
    
    if( s == 0 )
      printf( "%s\n", answer );
    else
      puts( "NO" );
  }

  return 0;
}

ようわからんけど、正しくHTML表示されないなあ。

トラックバック - http://d.hatena.ne.jp/susumu/20040617

2004-06-09 面接

良くも悪くも、今日が最後の面接となることを祈ります。全身全霊を賭けて戦い、体がガタガタ。疲れたの一言に尽きる。

Code Reading

| Code Readingを含むブックマーク

ISBN4-8399-1265-3

勢いで買ってしまいました。今さっき2章を読み終えたところです。で、2章の内容はちょっとどうよって感じでした。面白いには面白いけど、偏りが激しくない?って感じです。まるで相撲取りとシーソーをした気分でした。

トラックバック - http://d.hatena.ne.jp/susumu/20040609

2004-06-02 鬱症状進行中

鬱症状のおかげで心身ともに危険な状態へとまっしぐら。このまま眠れない日々が続くようだと、病院へ通うことになるのか!? とにかく就職活動が落ち着くのを待つだけか。

javax.imageio.ImageIO.read()

| javax.imageio.ImageIO.read()を含むブックマーク

なんか、ImageIO.readを仕掛けると、時々スレッドが止まるんですが… マルチスレッドで動かしているのがいけないのか、それとも。。。ばぐ?

グラフシミュレータ

| グラフシミュレータを含むブックマーク

階層型グラフも扱えるようになったということで、さっそく適当な例題で実験してみました。題材は、去年の創造工房セミナの「もやもや消しゴム」です。

実際のLSI上で動作する回路の総モジュール数は3ステージ82モジュールですが、Javaによりモデリングされた回路は4ステージ44モジュールです。Javaモデルのほうが若干抽象度を高いですが、機能の粒度はほとんど変わりません。

モデリングに掛かった時間は、4時間です。画像入出力モジュールの設計や、シミュレータのテスト・デバッグなども含まれています。ですので、実際にモデリングに掛かった時間は半分ほどで、十分満足できる生産性だと思います。

さてその性能ですが… おせ〜 もう、遅いとかいうレベルじゃない。LSI上で動作する回路は、73万ピクセル毎秒ぐらいの性能で、リアルタイム画像をぎりぎりで扱えます。それに対し、シミュレータを使うと、5500ピクセル毎秒ということで、100分の1ぐらいの性能しか出ていません。ぎゃ〜 超細粒度並列処理(処理のほとんどがモジュール間の通信に費やされており、1つのモジュールには1つのスレッドが割り当てられている)の上に、シミュレーションを開始した瞬間、50ものスレッドが立ち上がるので、仕方がないといえば仕方がないのですけど。。。

さらに、ImageIO.readで止まる。そのたびにシミュレーションを強制中止して、再開するという情けない仕様。ふざけるな〜!!

もやもや消しゴムの解析

| もやもや消しゴムの解析を含むブックマーク

ほとんどのモジュールが、その処理時間の6割〜9割をモジュール間のread/writeに費やされている。その内訳は、HashMapの検索が6〜7割、LinkedListへの読み書きが2〜1割、雑用が2割と言った感じ。便利便利とHashMapを多用したのが間違いみたいだ。すこし、見直したい。

グラフの階層が深くなればなるほど、HashMapによるマッピングの階層も深くなる。そのため、HashMapの検索時間が相対的に増え、性能が低下している。そして、Channelの実装としてLinkedListを利用しており、大量のデータの読み書きのための性能低下を心配していたけど、HashMapの威力が大きすぎるために、思ったよりも影響はすくなさそう。

結論としては、今すぐHashMapの利用を見直せということか。

トラックバック - http://d.hatena.ne.jp/susumu/20040602
267947
Connection: close