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 |
本体サイト

2005年03月27日(日) いそがしや…

向こう二週間は次のような理由でまともな内容は書けないかも。

[]準備がやばい… 準備がやばい…を含むブックマーク 準備がやばい…のブックマークコメント

いつもはぐうたらな私がいつに無く働いております…。

といいますか、ICPC世界大会が一週間後ですよ。ほんとですか。

今まで全然準備をしてこなかったしわ寄せが。

ただでさえ初海外で大変なのに、去年から

会場に自由な紙媒体資料の持込が制限されて

あらかじめこちらで上限25PageのPDF資料を

作らないといけないことになったので、それを作らないといかん…。

なんだかんだで今まで私はアルゴリズム勉強とか

ほとんど自己流で勉強してきたので、体系的知識があんまりない。

何を書いていいのかさっぱり分からない。

資料を自分で作らなければならないといっても、

自分で作るものなので、すべての内容は既知なわけです。

つまり、わざわざ資料として持ち込むほどの価値のある

"既知の"内容というのはかなり制限されるわけで、

それぐらい価値のある内容を25Page分も集めるのに

むちゃくちゃ苦労しておるわけですな。

かといってページをあまらせるとそれはそれでもったいないし、

M氏に、余裕だな、とか言われるわけです。

うーん…この調子で大会までに準備間に合うのか…。

最近問題もあんまり解いていないし、XPの練習もしていないから

ちゃんと息が合うかどうか…うーむ。


どうでもいいけど、京大トップページからたどれるところに

この前の謁見の記事が載りましたよ。

http://www.kyoto-u.ac.jp/notice/05_notice/ippan/050325.htm

大学のほうもプロモーションをしてくれたということで、

私もプロモーションしたほうがいいのかな…

なので、紹介させてもらっておきます。

なんか微妙に間違ってる箇所がいくつかあるような気がするけど…

まぁ、いいか。

来年は東京らしいので、出場資格のある皆様、是非出ましょう。

(http://www.teu.ac.jp/icpc/ ためしに叩いたら、微妙に出来てる)

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

2005年03月24日(木) 逐次型言語と関数型言語の狭間

[]C言語からHaskellへの変換 C言語からHaskellへの変換を含むブックマーク C言語からHaskellへの変換のブックマークコメント

http://www.sun-inet.or.jp/~yaneurao/ こちらにてD言語にも移植されている

http://www.glexcess.com/ このデモをHaskell移植してみた。

実は去年の夏ごろに移植しようかと思っていたのだが、

GHC6.2ではHOpenGLからテクスチャサポートがはずされていたので

断念せざるを得なかった。

そういうわけなので、GHC6.4が出た暁には移植してやろうとかねてより

考えていたのだが…。

http://fxp.infoseek.ne.jp/haskell/glexcess_haskell.zip

ここにシーン1とシーン2を移植したものを公開してみた。

どうしてシーン1とシーン2だけなのかというと、

あまりにも移植作業が大変だったもんで

このあたりで力尽きてしまったというか、なんというか。

というわけで、先日書いたHaskellで書くのが大変なものというのは

与えられたCプログラムと同じ動作をするプログラムのことであった。

グローバル変数配列などを使われるとすんなりと

コードを変換することが非常に困難になってしまう。

そういうわけなので、それなりにまともに書こうと思うと、

Cのプログラムが何をやろうとしているのかを逆に読み取り、

そういうことを行うHaskellプログラムを書く必要がある。

IORefを使いまくってプログラム全体をIOまみれにしてやったら

一対一対応もつくのかもしれないが…うーむ。


…ということで、このプログラムシステム部分は割と綺麗に書けていると思うので、

残りのシーンをどなたか移植して下さりはしないだろうか。

残り10シーン…ぐは…うんざりだ。

yaneuraoyaneurao 2005/03/24 15:17 す、、すごい!!

h_sakuraih_sakurai 2005/03/24 23:53 ゲームの次は、デモすか。はぁ。すごいですねぇ。
前のゲームもですが、マシンパワーが足りないせいか、
FPSが遅くなってしまいます。

tanakhtanakh 2005/03/25 06:13 ここ最近以前より格段に多くHaskellを見るようになってきましたが、
やはりもっと人を取り込むためにはこういうキャッチーな
分野をしっかりカバーできるのだということをアピールすることが
不可欠ではないのかなと思いまして…。
マシンパワーですか。うーん。
こっちの環境はLet’s note W2なので、そんなに
速いマシンではないんですけどね。
デモのシーン2はうちでも重いです。
毎フレーム万のオーダーのオブジェクトを作ったり
壊したりしているはずなのでちょっと厳しいかもしれませんね。

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

2005年03月21日(月) world final warmup 2

[] world final warmup 2  world final warmup 2を含むブックマーク  world final warmup 2のブックマークコメント

なんだかんだで後二週間を切っている。

進まぬ準備。

Haskellerだけに、作業を遅延評価してしまっているようだ。


そんなわけで、この前の acm.uva.es の world final warmup 2 に

参加した。またもや世界大会レベルの難問ぞろい

(一問むちゃくちゃ簡単なのがあるけどな…)

http://acm.uva.es/cgi-bin/OnlineJudge?Volume:108

問題はここの10830〜10839の十問。

書けば通るだろうと思われたチェスの必勝手探索問題に

早い段階で手を付けてしまって大きく時間をロスしたので

開始から5時間には3問しか解けなかった。

実装系問題には簡単には手を付けるなということか。

しかし、以降24時間までの延長戦で怒涛の追い上げを見せて

結局7問正解の12/250位。

ここのコンテストでこんな順位取れたの初めてだよ…。


ところで、解いているときに発見的に分かったことなのだが、

¥Large¥sum_{i=1}^{n} n mod i

これを効率よく(というかO(n^{¥frac{1}{2}})で)求めるアルゴリズムがあるんだな。

解いている人が異常に多かったのだが、有名なことだったのだろうか。

しかし、整数は奥が深い…。

tsutomu3tsutomu3 2005/03/22 10:39 O(n^0.5)のアルゴリズムとは、どのようなものでしょうか?

tanakhtanakh 2005/03/23 10:20 これはですね・・・文章で書くのは少し難しいのですが・・・。
map (100 `mod`) [1..100] あたりを眺めていれば分かるかと思うんですが、実はこの数列、等差数列の集合になっているんですよ。
それで、それをもとに計算するとO(n^0.5)で済みます。

tsutomu3tsutomu3 2005/03/23 11:28 すいません。さっぱりわかりません。あきらめます。

Nazo9xNazo9x 2005/03/23 13:52 reverse $ map (100 `mod`) [1..100]
こうするとわかりやすいかも・・・
とはいっても眺めてみただけだけど。

h_sakuraih_sakurai 2005/03/23 19:56 ベクターのどこかに、競技の説明のPDFがあって分かりやすかったきがしたなぁ。図が一番ですよね。

tanakhtanakh 2005/03/24 06:08 うーん。やっぱり説明が良く無かったですね…。
確かに逆にすれば分かりやすいですね。
たとえば、32の場合だと、reverse $ map (32 `mod`) [1..32] は
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,2,4,6,8,10,2,5,0,4,2,2,0,2,0,0] となりまして、これは
[0,1,2,3,..,15] [0,2,4,6,8,10] [2,5] [0,4] ...
と区切ると、それぞれ左から差が1,2,3,4の等差数列です。
[0,4]よりも左は等差数列の長さが1以下になるので
見かけ上無秩序です。
形式的に言えば、差がiの等差数列がfloor(n/(i+1))+1 〜 floor(n/i)
に存在しているということになります。
そういうことなので、等差数列をなしている部分をまとめて計算することにより
計算量を減らすことができて、その減らせる量を考えるとO(n^0.5)
であることが分かります。
…ということですが、どうでしょうか。
やっぱり図が書けた方が説明はしやすいですね…。

tsutomu3tsutomu3 2005/03/24 10:03 ありがとうございます。なんとなく(雰囲気だけ)わかったような気もします。

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

2005年03月19日(土) 疲れている…

現在作っているHaskellプログラムがめちゃくちゃ難航。

"とあること"に対してはとても疲れることが分かった。

まぁ、近日中にでも公開できれば良いだろうか。

[]総長に謁見 総長に謁見を含むブックマーク 総長に謁見のブックマークコメント

世界大会出場を受けて総長に挨拶に行ってきた。

総長が図書館横のあたらし目の建物に居られることは

知らなかったが、なんだか物々しい警備であった。

ここ最近まで一階部分は一般公開されていたようなのだが、

なんんでも最近の授業料値上げ騒動?と石垣問題で

一階部分を占拠されたりしたらしいので、

警備強化をしているらしいのだ。

初めて入る大学の中核部であったが、なんだかすごかった。

京大にもこんなところがあったのか、と思った。

秘書室秘書と思しき人が何人も居た。

待合室には各種新聞、各種雑誌が置いてあった。

大学広報誌「くれなゐもゆる」とか、初めて見た。


副学長に挨拶した後、総長に会う。緊張した。

1st placeに格上げされた賞状を手に説明。

途中、どういうことをするコンテストなのか私が説明する

場面もあったが、全然うまく説明できなかった。

駄目だ…。

とにもかくにも、ICPCについて広報して頂けるということになった。

情報学科以外にも知ってもらえると京大も層が厚くなるだろう。

奇しくも世界大会の日時と入学式の日時がほぼ同じなので、

入学式でも忘れていなければお話しいただけるとのこと。

今年京大に入学する人はぜひともご注目を。

最後に皆で記念撮影。写真写り悪し。うーむ。


帰り際、めったに入れるところではないので

周りの様子を撮影したりしたが、警備上の理由からか

むやみな公開はしないでくれとのこと。

うーん、ものものしい。

さて、私が次回ここに来れるのは、勝利報告か、来年か…

(それとももう無いのか)

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

2005年03月15日(火) shu-thing

[]Haskell シューティングゲーム Haskell シューティングゲームを含むブックマーク Haskell シューティングゲームのブックマークコメント

東大の夜に作ったシューティング

このへんで公開された。

やっぱり難しい…。これクリアできるの?

万が一クリアできた場合、Haskellへの熱いメッセージが拝めます。

まぁ、ソース読んだら分かるんだけど…。

h_sakuraih_sakurai 2005/03/17 22:39 クリアしてしまいました。ボスが、、、感動しました。笑
エンディング見てて、アンチエイリアスかかっていなくても、動くと結構、滑らかに見えるもんだなぁと感心しました。

tanakhtanakh 2005/03/19 15:19 うーむ…クリアできましたか。
動きのあるシーンは粗が目立ちにくいんですかね?なるほど。

nushionushio 2005/05/26 14:50 [このへん]は移動しました。
この記事にひょっとしてたどり着いた人のためお知らせしときます。
http://www.geocities.jp/takascience/

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

2005年03月14日(月) 練習会

[]練習会 練習会を含むブックマーク 練習会のブックマークコメント

みたび東京へ。

なんだかどっと疲れた。

前日から行って東大に泊まっていたのだが、

GHC6.4のWindows版が出ていたので、

M氏と朝までHaskellシューティングを作ってしまった。

最初は何かポリゴンがへろへろと動くだけだったのだが、

「自機から弾を撃たないと」

「敵を出すんや」

「やっぱり敵も弾を撃ってこないと」

「敵の行動パターンが一通りではあかん」

弾幕弾幕

「爆発エフェクトも付けんと」

「やっぱりボスがいないとだめだろ」

タイトル画面を作るんや」

「ここまで作ったんだからエンディングも付けんといかんだろ」

…というわけでおもったより進展してしまった。

しかし、できたものが難しすぎ。ボスまで行くのすら大変。

シューティングは難しくてちょうどいいとはM氏の弁だが、

そうなのか?


その後仮眠をとって、練習会

体はだるいし頭は働かないし食欲は皆無だしで、最悪のコンディションだった。

またもなぜかしら順位は良かったが…これまた楽観もできないだろう。

とかなければならない問題をすべて解いたわけではないから。

とりあえず、大好きなパーザー問題が出たのは嬉しかったが、

(パーザー問題が好きなのではなくてパーザーを書くのが好きなのだが)

そこに極めてたちの悪い引っ掛けがあったのは残念だ。

パーザーが解けないのがくやしくてくやしくてくやしくて、

開始二時間Wrong Answerの山を築いていた。

結論から言うと、区間演算には落とし穴があるので手を出すな?

まぁ、もうその辺は分かったので今度出たら大丈夫だとは思うが…

とりあえず終了後激励される。

Honorable mention 取ったらぼこぼこだぞ、とか。


それから京都にとんぼ返り。

帰りの新幹線で、誤って喫煙席に座ってしまったので、

たっぷり燻されてしまった。

前も斜め前も横もその横も後ろも喫煙者だなんて…。

結構がんばって帰ったのに、終電一個前だった。疲れた。

帰ったら三月なのに霰が降っていたようだった。寒かった。

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

2005年03月11日(金) GHC 6.4 Released!

[]GHC 6.4 GHC 6.4を含むブックマーク GHC 6.4のブックマークコメント

うわああああああ。

今見たらGHC6.4がついにリリースされとる。

去年の時点ではの11月にリリースとか書いてあったから、

それから毎日見に行ってましたよ。

それが12月になり、1月になり、2月になり…。

やっとですな。


何はともあれ、これでOpenGLでテクスチャが使える。

…と思ったら、Windows版はまだですか。

もうちょっと待ちます…。

[][]About Haskell について。 About Haskell について。を含むブックマーク About Haskell について。のブックマークコメント

久しぶりにこのページをみた。

Haskellの利点として短いクイックソートが例に挙げられていた。

昔はふむふむと読んでいたのだが、今読んでみると

若干の違和感を感じた。

それというのは、Cで書かれたクイックソートのほうだ。

たしかに例に挙げられているCでのクイックソートは長くて分かりにくい。

ちょっとした不注意でバグを盛り込んでしまうだろう。


だから、多分今私が確実に動作するクイックソートを短時間でC++で作れ、

といわれたらきっと次のようなコードを作成する。

void qsort(vector<int> &v)
{
  if (v.size()==0) return;
  vector<int> low,high;
  int t=v[0];
  for (int i=1;i<v.size();i++){
    if (v[i]<t) low.push_back(v[i]);
    else high.push_back(v[i]);
  }
  qsort(low);
  qsort(high);
  int c=0;
  for (int i=0;i<low.size();i++) v[c++]=low[i];
  v[c++]=t;
  for (int i=0;i<high.size();i++) v[c++]=high[i];
}

実際のところこのコードはすぐにかけたし、間違いもしなかった。

というのも、このコードはHaskellのものと本質的に変わるところがなく、

間違える余地もほとんどないからである。


そういうわけで、クイックソートを引き合いにして

Haskellの有利性を説くのはいかがなものかと思った。

もちろん、Haskellの定義のほうが遥かに簡素だが、

クイックソートの実装においてそこまでの断裂があるわけではなかろう。

[]超難問現る… 超難問現る…を含むブックマーク 超難問現る…のブックマークコメント

L-Gap Substrings

これは難問である。K氏とM氏と三人で何時間も考えたけど分からなかった。

DPなんだろうか。問題のサイズから考えるとそうとしか思えないが。

うーん。

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

2005年03月08日(火) 複素数と平面幾何

この前の文章がやねうらおさんのところで紹介されたもんで、

予想以上の反響になった。

何はともあれ、いろいろな人に読んでいただけて有難いもんです。

内容のほうが今ひとつ煮え切らないような感じになってしまっていたので

もっと批判的なご意見もいただくかと思ったが、

同じように感じているというものが多く、

嬉しくもあり意外でもあった。

まぁ、なにかもっと真髄のようなものをつかめたら

続きでもかきます。

[]複素数による平面幾何プログラミング 複素数による平面幾何プログラミングを含むブックマーク 複素数による平面幾何プログラミングのブックマークコメント

ICPCが近いので、ライブラリを作らないといかん…。

というわけで、平面幾何。

平面幾何を扱うのにcomplexを使うのはもはや常識(?)

なのかもしれないが、そこをちょっとおさらいしてみることにする。

最初このテクニックを見たとき、

自分でstruct point{ int x,y; }; とか、

演算子の定義とかを書く必要がないのか、と思ったのだが

私の考えが浅かった。複素数で点を扱うと、

複素数平面上で平面幾何を扱うことになり、

便利な関数がたくさん利用できるということになる。

さらに、回転が簡単にかけたりするので、問題を回転させて

より簡単な問題に帰着したりできるかもしれない。


typedef complex<double> pt;

pt x,y;
pt z=x+y;
double c;
pt w=c*z;

このようなことが何もせずに使える。

  • 二点間の距離
abs(x-y);

ベクトルvのx軸となす角は、

arg(v);

ベクトルuとvのなす角は

arg(u/v);

と書ける。


ベクトルuをベクトルvに移す写像fを

pt f=polar(abs(u)/abs(v),arg(u/v));

簡潔に書ける。

ベクトルu,vの内積

real(u*conj(v));

で求めることができる。

(成分を計算することにより簡単に確かめられる)

ベクトルu,vに対して行列[u,v]の行列式を

imag(conj(u)*v);

で求めることができる。

(同上)

  • 三角形の符号付面積
double area(pt a,pt b,pt c)
{
  return imag(conj(b-a)*(c-a))*0.5;
}

点aを原点に平行移動させて、行列式より計算できる。

  • 二直線の交点

直線 a+su,b+tv (a,b,u,v はベクトル、s,tはスカラ変数)

の交点。(s,tを返す)

pair<double,double> cross_lines(pt a,pt u,pt b,pt v)
{
  double det=imag(conj(u)*v);
  if (abs(det)<epsilon) throw "交差しない";
  return make_pair(
    -imag(conj(v)*(b-a))/det,
    -imag(conj(u)*(b-a))/det);
}

証明は…成分を計算すると確かに正しいのだが、

式の意味するところは良く分からんです…。

交差しないときに例外を投げてしまっているが、

これはあんまり良くないので、実際に使うときは

うまいインターフェースを考えよう。

  • 円と直線の交点

直線 x=a+su と円 |x-c|=r の交点を求める。

(sを二つ返す)

pair<double,double> cross_circle_and_line(pt a,pt u,pt c,double r)
{
  pt ac=a-c;
  double b=real(u*conj(ac));
  double d=b*b-norm(u)*(norm(ac)-r*r);
  if (d<0) throw "交差しない";
  return make_pair(
    (-b+sqrt(d))/norm(u),
    (-b-sqrt(d))/norm(u));
}

単純に直線と円の式を解くと上の式は得られる。

  • 二円の交点

円 |x-c|=r と |x-d|=s の交点を求める。

pair<pt,pt> cross_circles(pt c,double r,pt d,double s)
{
  double di=abs(c-d);
  if (di>r+s || di<abs(r-s))
    throw "交差しない";
  double l=((r*r-s*s)/di+di)/2.0;
  double n=sqrt(r*r-l*l);
  pt e=c+(d-c)*l/di;
  pt p=(d-c)*n/di*pt(0,-1);
  return make_pair(e+p,e-p);
}

二つの円の交点と、二つの円の中心のなす凧形を考えれば

式が導出できるが、ややこしいので省略。

複素数ならではなことはできていないが、

短くする効果は十分だろう。

yaneuraoyaneurao 2005/03/09 09:28 こうして見ると複素数での平面幾何って面白いですネ。でも、3次元上の幾何には使えないので、どっちかって言うと、行列演算をtemplateで実装したものがあったほうがいいような..?

Nazo9xNazo9x 2005/03/09 17:42 使っていないので詳細はわからないけど。こんなのあるよ。
http://www.page.sannet.ne.jp/d_takahashi/boost/ublas/index.html

tanakhtanakh 2005/03/10 03:36 三次元以上の幾何は正直問題自体が難しいです…。
行列周りのライブラリがあれば確かに便利でしょうけど。
boostにこんなのがあったんですか。
boostは標準じゃないので、コンテストで使えないのが痛い…
逆に使えるとC++があまりにも有利になってしまいますが。

daismdaism 2005/03/11 20:07 検討違いならごめんなさい
http://vision.kuee.kyoto-u.ac.jp/~hiroaki/numerical/

tanakhtanakh 2005/03/11 23:54 これも行列が扱えるんですかね。いろいろあるんですね。

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

2005年03月06日(日) バグのないプログラムの書き方

今回、ちょっと最近思うところを文章にしてみたが、むちゃくちゃ疲れた。

難しい。しかもかなりしょんぼりなできになってしまった。

…もういいや。

[]バグのないプログラムの書き方 バグのないプログラムの書き方を含むブックマーク バグのないプログラムの書き方のブックマークコメント

突然であるが、プログラムにはバグが付き物だ。

それゆえに、統合開発環境にはGUIデバッガがついていたりして

プログラムの処理が追いやすくなっていたり、

テストケースを書いたりして部分的にバグの発生を制御したりする。


だが、それは本当だろうか?

もっと別の方法でバグの発生自体を抑制できないのだろうか。

ここのところ私はこのことばかりを考えていた。

Haskellをはじめたのもこのためだ。

そしてこれは私の中で、そろそろ結論に達しつつある。

(うーん。こんな深遠なテーマに軽々しく結論などと言っていいものか)


それで、結論から言えば、バグを抑える方法があるのは間違いない。

実際に最近私が書く(C++の)コードのバグ発生率は以前と比べて

著しく低下した。その変化っぷりに自分でも驚くことしばしばなのだ。

やはりなにかコツがあるのだろう。

では、そのコツとはなんだろうか?


私の各コードのバグが少なくなった時期を考えてみると、

どうも、というか、やはりというか、Haskell勉強していた時期とかぶるようだ。

HaskellでのコーディングスタイルC++でのコーディングにも影響を与え、

その結果バグの出にくいコードが書けるようになったんだろうか。

しかし、これはあまりにも抽象的である。

もっと具体的に何がどのように変わるのか?

それが分かればバグのないプログラムを書くための一助となるかもしれない。


これに対する私の見解であるが、一言で言ってしまえば、

「無理をしない」である。

あらゆることについて無理をしない。

無理をせずに自明なコードだけ書いていればバグの入る余地がなくなる。

Haskellをやりだしてから細かいことを書かなくなった

(書きたくなくなった)。やりたいことを書けばいいのである。

これはある意味富豪的プログラミングに通じるのであるが、

今回の話は富豪的というところにとどまらない。

徹底的に首尾一貫して手を抜けというのである。


逆に言うと、手を抜くために思慮深くなれ、ということだ。

プログラムを書く前に、ちょっと待った。

ゆっくりと考えを巡らせてもっと簡素にかけないかを考える。

ここで言う簡素というのはプログラムの長さではない。

コード化する際に、いかに考える余地が入らないかである。


これでもあまりに抽象的である。

具体的に考える余地を減らすガイドラインを考えてみる。

HaskellC++での違いであるが、やはりもっとも大きな違いは

純粋関数的ということだろう。

プログラムが純粋関数的であるならば、

入力により出力が決まるのでバグの入る余地は圧倒的に

少なくなるはずである。

その最たるものとして、変数に代入を許さない、

これをC++でもなるべく守るようにする。

もちろん、C++変数に代入をせずにプログラムを作るのは

とても難しい。だから、完全に排除するのではなくて、

代入によってプログラムの見通しが悪くならないように心掛ける。

プログラムの離れた場所で同じ変数に代入を行わないとか、

変数の内容が掌握しやすければしやすいほど

プログラムから考える余地は減ると思う。

同じような理由で変数の生存区間を小さくするのも有効だろう。

同じ変数をいろいろなところで使わないのも重要だ。


もっと直接的な関数的な考え方としては、

再帰的なアルゴリズムを繰り返しに変換しない、というのがあるだろうか。

再帰的な関数と繰り返しに変換したものでは

たいてい再帰的な関数のほうが理解しやすく掌握しやすい。

int gcd_r(int a,int b)
{
  if (a%b==0) return b;
  else return gcd_r(b,a%b);
}

int gcd_i(int a,int b)
{
  while(a%b!=0){
    int c=b;
    b=a%b;
    a=c;
  }
  return b;
}

たとえば、GCDなら、上の再帰版はまったくの定義の通りで、

正しいことは自明であるが、

繰り返し版は注意深く読まないと正しいことが分からない。

速度の問題があるかもしれないが、繰り返しに変換できる

再帰関数ならばせいぜい定数倍である。

本質的に問題となるのは、呼び出し回数があまりにも多くなったとき

タックがあふれるかもしれない、ということであるが、

そのときは確かに仕方がない。

しかし、通常スタックは数MB存在するので、

タックフレームで呼び出し一回あたり数十B消費されたとしても

十万回は呼び出せる計算になり、このオーダーの再帰回数が

必要になるアルゴリズムはなかなかない。

(あるいは、よくできたコンパイラなら末尾呼び出しの

最適化を期待できるかもしれない。VCでは末尾再帰呼び出し

だけなら何とかがんばってくれていたような気がする。

まぁ、最適化してくれないものと考えておくのが正解かもしれないが)

ほかには、DPを実装するとき、これを元の再帰的なアルゴリズム+

キャッシュと実装するほうがテーブルを組織的に埋めていくよりも

楽な場合が多い。テーブルを組織的に埋めるには

添え字の問題や順序など、いろいろと神経を使うことが多い。

やはり考慮すべきことは少なければ少ないほうがいい。


後は、最近では当たり前であるが、

配列や文字列を値として扱う、つまりC++であっても

配列ポインタで持たないということだ。

(配列はともかく)文字列をポインタで持つとバッファ長など

これまた色々と神経を使う。要するにコンテナを使えということだ。


とまぁ、(いろいろと考えては見たものの)

あんまりたいしたことは書けなかったが、

やはりそういうコツがあるのは間違いない。

感覚的にそういうのがあるのは分かるのだが、

文章にするのはとても難しい。

今回、言いたいことがほとんど書けていないのだが、

これだけは言える。関数言語勉強したことにより

そういう考え方がC++でのコーディングにも影響を及ぼしているのだ。

(C++Haskellも使う方で、同じような考えの人は居られますかね…?)

yaneuraoyaneurao 2005/03/07 07:32 的を射てると思いますヨ > バグのないプログラムの書き方

tanakhtanakh 2005/03/07 19:21 そうですか。あんまり自信がなかったのでうれしいです。

soutarosoutaro 2005/03/08 01:00 はじめまして.僕はVBとOCamlでプログラミングしてる人ですが同感です.Haskellとかでプログラミングしていると「いかに定義から自明なプログラムを導けるか」という視点になるのかなと思います.

tanakhtanakh 2005/03/08 06:16 はじめまして。同感とは嬉しいです。そうですね、如何に行うか、をなるべく書かないようにする、とも言えますかね。この辺のところを具体的にはどうなのかを考えていると難しくなってくるんですけど…

kennakkennak 2005/03/08 10:56 誰でも読めるプログラムを書けって事ですね^^
同感です

tanakhtanakh 2005/03/08 22:03 うーん。言ってしまえばそうなんですかね。とにかく、できる限り考えるべきことを減らそうと。

2005年03月03日(木) ぶらり京都一人旅

今日のはプログラムに全然関係がない上に

無駄に長いので見たい人は下をクリックして見てくだされ。

nushionushio 2005/03/05 08:56 京都散歩楽しませてもらいました(^ー^

tanakhtanakh 2005/03/05 10:18 だから、散歩じゃないと…

susu 2006/03/30 00:57 京都出身なので、そこはかとなく見た風景がありますね。復活幼稚園、あったなぁ:-)

2005年03月02日(水) 腐ってもHaskeller

Imagine Cupは123点で終わりそうだなぁ…しくしく。

[]この前のをHaskellで解いてみる。 この前のをHaskellで解いてみる。を含むブックマーク この前のをHaskellで解いてみる。のブックマークコメント

最近はHaskellerらしからぬことばっかりやっていたので、

久しぶりにHaskellを使うことにした。

ここから、割合簡単なADIをHaskellで実装。

とりあえずリハビリということで。

しかし、副作用がないと良い。見通しが立てやすいね。


A問題

import Data.List
import Data.Char
import Control.Monad
import System.IO

data Tree = Leaf | Node [Tree]

buildTree s = inner s [] where
  inner [] (t:_) = t
  inner ('a':ss) stk = inner ss (Leaf:stk)
  inner (num:ss) stk = inner ss ((Node (reverse c)):r)
    where (c,r) = splitAt (ord num - ord '0') stk

optimize Leaf = (1,"a")
optimize (Node ls) = ret where
  os   = map optimize ls
  len  = length ls
  cand = [calc $ take len $ drop n os++os | n<-[0..len - 1]]
  calc ls = (dep,str) where
    dep = maximum [n+d | (n,(d,_)) <- zip [0..] ls]
    str = concat (map snd ls) ++ [chr (len + ord '0')]
  ret = minimumBy (\(a,_) (b,_) -> compare a b) cand

main = do
  h   <- openFile "chandelier.in" ReadMode
  num <- hGetLine h
  ls  <- replicateM (read num) (hGetLine h)
  let as = map (optimize . buildTree) ls
  mapM_ (\(n,s) -> print n >> putStrLn s) as

D問題

import Data.FiniteMap

main = readFile "game.in" >>=
  mapM (printAns.solve) . takeWhile (/=[0,0]) . map (map read . words) . lines

solve [n,m] = filt (==1) (ops!!m) $ foldl (flip $ filt (/=1)) s $ take m ops where
  s = [(a,b) | a<-[1..n], b<-[a+1..n]]
  ops = cycle [(+),( * )]

  filt cond op ls = 
    concat $ filter (cond.length) $ eltsFM $ addListToFM_C (++) emptyFM [(op a b,[(a,b)])| (a,b) <- ls]

printAns ls = do
  print $ length ls
  mapM_ (\(a,b) -> putStrLn $ show a ++ " " ++ show b) ls
  putStrLn ""

I問題

import Data.Char
import Control.Monad
import System.IO

data Tree = Node Char [Tree]

instance Show Tree where
  show (Node c []) = [c]
  show (Node c ls) = [c] ++ "(" ++ concat (map show ls) ++ ")"

main = openFile "org.in" ReadMode >>= inner where
  inner h = do
    n <- hGetLine h
    when (read n /= 0) $ do
      s <- hGetLine h
      t <- hGetLine h
      print $ solve (filter (not.isSpace) s) (filter (not.isSpace) t)
      inner h

solve [a] [b] = Node a []
solve (a:as@(aa:_)) (b:bs) = Node a child where
  roots = takeWhile (/=aa) bs ++ [aa]
  ar = reverse $ snd $ foldl slice (as,[]) $ tail (reverse roots) ++ "*"
  br = [filter (`elem` a) bs | a<-ar]
  child = reverse $ zipWith solve ar br
  slice (ss,ret) c = (sr,rr:ret)
    where (rr,sr) = span (/=c) ss

うーん…どれもHaskellならでは…な技を使えたわけでないなぁ。

いたって普通になってしもた。

コードはC++より抜群に短い。

C++のコードは長いので割愛。

A100行、D70行、I100行ぐらい。

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

2005年03月01日(火) 文章がかけないの…

む〜ん… む〜ん…を含むブックマーク む〜ん…のブックマークコメント

いろいろ書きたいことはあるけれども、

どうも文章がゴミみたいになっちゃって

公開してもしゃあないなぁ…みたいな感じで

いくつか没にして、最近ぜんぜん文章を公開できない。

まともなネタができるまで待ってたらいつまでかかるか分からんぞ

…ということで強制再開してみる。

[]世界大会向け合宿 世界大会向け合宿を含むブックマーク 世界大会向け合宿のブックマークコメント

また東京に行ってきたらしいです。

今回はお金京大から出るらしいけど、

帰りの特急券の領収書を貰うのを忘れたらしいです。

私はどうなってしまうのでしょう。

成績はまずまず…か?悪くはなかったけどこれで楽観もできないな。

一日目遠隔の韓国チームに負けたけど、それもまた一局。

とりあえずうちのチームは抱え死にが少なくていいね。

問題のほうは難しすぎて頭がおかしくなりそうでした。

あと、今回一日目にみんなで分担して問題を読んで考える、

みたいな企画があったけど、私は英語を読む人じゃないので、

泣きそうでした。ストレスたまりまくり。コードだけ書かせてくれい。


帰り際に"趣都"に寄り道をしてきた。

かなり久しぶり。確か5年ほど前に行ったときは

まだ趣都じゃ無かったような気がするんだけど。

秋葉原がそういう傾向に変化しつつあるということは、

大阪日本橋もその傾向があるのだろうか・・・?

想像できん。

M氏がおもむろにアレげな店に入っていったのにはびびった。

[]お受験の季節 お受験の季節を含むブックマーク お受験の季節のブックマークコメント

…て、それよりも、合宿中に国立大学試験があったのですよ。

妹が受験なのですが、そんなときに合宿に行っていていいのか?

まぁ、家に居ても何もできないけどね…。

とりあえず、私立のY学部に行っちゃうとうちの家計が崩壊するので、

個人的には国立に行ってほし……いとはよう言いませんが。

本人の行きたいところに行かせてやりたいとは思うけど、

さすがに親の年収の半分以上を持っていくようなところに行くのは

厳しいのでなかろうか。国立のY学部はだめなの?

ってことだけど、これは学力の問題があるのでなぁ…

数学理科だけ代わりに受けてやりたい。

[]Imagine Cup アルゴリズム部門 Imagine Cup アルゴリズム部門を含むブックマーク Imagine Cup アルゴリズム部門のブックマークコメント

これもそろそろ終わりなネタだけど、Imagine Cupに細々と参加。

何回かやったけど、最高128点。ぜんぜん駄目だ。

というか、問題が英語の時点で私にはお手上げ。

半分以上は英語解読に費やされるし、

そもそも読んでも理解できない文章も結構あるし…。

ああ、さんまんえんが…。

とりあえずアルゴリズム部門は来年から英語部門と改名してくれ。

それなら諦めがつく。

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