Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

June 30(Sat), 2007

[] 知ってる言語

shinhさんとこ読んで、なんか確認したくなった。「知ってる」はまあ、今てきとうにちゃっちゃとその言語でなんか意味のあるプログラム書いたりできるか、くらいで。

C, Java, Scheme, Common Lisp, JavaScript, Perl, VerilogHDL

VerilogHDL とか入れてるのは単に大学の VerilogHDL 実験のレポートを今書いてるから、という話。

コードを読んだり、マニュアル読んで思いだしながらならなんか作ったりもできるかも、くらいなら Emacs Lisp, PHP, x86, MIPS とか入れよかな。AWK はワンライナーしか書いたことないし。bash は完全に欠片も残さず忘れた。BASIC は一行たりとも実行させたことも無いけど、大学受験では使った。

hello world 書いたことある程度の言語なら、C++, Postscript, Ruby, Prolog, OCaml 。

「使える」言語はというと、「使った=実用するプログラムを書いたことがある」言語とすると、Perl, PHP だけ。

「知ってる言語 = 言語名だけでもいいから知ってる言語」にしない限り、「知ってる言語>年齢」にはならないということがわかった。

ここはいっそのこと HTML, LaTeX, SVG, はてな記法 とかもプログラミング言語だ、とか言えばいい。

[] TinyWM

小さいことはいいことだ。

TinyWMがかっこいいです。別にゴルフな書き方してるわけでもなく、50行程度。「こんなにちっちぇえウィンドウマネージャーは他にねえだろ!」とか。愉快だね。

ふつーに wm 書けるような人からすりゃどうということもないもんかもしれんが、「wm とかすごく難しいんでしょう?」とおじけづく若者にとても良いと思う。

h_sakuraih_sakurai 2007/07/02 04:58 window managerなのかぁ

hogeloghogelog 2007/07/02 21:05 自分ウィンドウマネージャーに求める機能は割と少ない方なんで、こんくらいの規模のプログラムいじるとちょうど楽しそうかな、と。
ちょうどメイン環境を Linux に移したところでもあったんで。

h_sakuraih_sakurai 2007/07/04 01:50 なるほどー

トラックバック - http://d.hatena.ne.jp/hogelog/20070630

June 28(Thu), 2007

[] Firefox の中とかでも C-h を Backspace, C-d を Delete などとして扱いたい。

xbindkeys, xvkbd を入れて、.xbindkeysrc に

# C-h as Backspace
"xvkbd -text '\b'"
  control + h
# C-d as Delete
"xvkbd -text '\d'"
  control + d

としておいて xbindkeys を起動しておけばいけるかなあと思った。全然いけなかった。ごくたまに意図する動作をすることもあるけど基本的にうまくいかない。うーん。どうすりゃいいんだろう。Firefox の textarea だけの話だったら、任意のエディタで編集できる拡張機能もたしかあったけど。

[] 速度

Gauche って結構速いらしい。CLISP は遅い。GCL は速い。

それというのも、大学の課題の N-Queens を解くコードのプロトタイプを Scheme で書いて、うまくいったからさて課題で定められてる Common Lisp にコードを書き換えて clisp にやらせたら、まあ遅かったわけです。コンパイルできることに気付いてコンパイルしたら多少速くなったけど、それでも遅い。

以下それぞれ 8-Queens を解いてもらう。求める解は一つ。

Gauche

gosh> (load "./n-queens.scm")
#t
gosh> (time (n-queens 8))
;(time (n-queens 8))
; real   0.740
; user   0.730
; sys    0.000
((4 . 8) (2 . 7) (7 . 6) (3 . 5) (6 . 4) (8 . 3) (5 . 2) (1 . 1))

CLISP

[1]> (load "n-queens.lsp")
[2]> (time (n-queens 8))
Real time: 8.19814 sec.
Run time: 8.192512 sec.
Space: 47481224 Bytes
GC: 90, GC time: 0.652032 sec.
((4 . 8) (2 . 7) (7 . 6) (3 . 5) (6 . 4) (8 . 3) (5 . 2) (1 . 1))
[3]> (compile-file "n-queens.lsp")
[4]> (load "n-queens.fas")
[5]> (time (n-queens 8))
Real time: 1.467878 sec.
Run time: 1.464092 sec.
Space: 13066840 Bytes
GC: 25, GC time: 0.144006 sec.
((4 . 8) (2 . 7) (7 . 6) (3 . 5) (6 . 4) (8 . 3) (5 . 2) (1 . 1))

GNU Common Lisp (gcl)

>(load "n-queens.lsp")
>(time (n-queens 8))
real time       :      5.630 secs
run-gbc time    :      4.450 secs
child run time  :      0.000 secs
gbc time        :      1.050 secs
((4 . 8) (2 . 7) (7 . 6) (3 . 5) (6 . 4) (8 . 3) (5 . 2) (1 . 1))
>(compile-file "n-queens.lsp")
>(load "n-queens.o")
>(time (n-queens 8))
real time       :      0.420 secs
run-gbc time    :      0.420 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
((4 . 8) (2 . 7) (7 . 6) (3 . 5) (6 . 4) (8 . 3) (5 . 2) (1 . 1))

俺の書いた N-Queens のコードになんか問題とかが色々あるとか想定したとしても。Scheme と Common Lisp でコードはまずまったく等価に書いたし。わりとびっくりした。

通りすがりのlisper通りすがりのlisper 2007/06/29 08:10 CLISP 版ってコンパイルしてますか? Gauche は自動的にバイトコードにコンパイルしますが、
CLISP だと compile 関数で関数毎にコンパイルするか、 compile-file + load しないとバイトコードに
コンパイルしませんよ。

hogeloghogelog 2007/06/29 12:54 えーと clisp のコンパイル版のコードが hoge.fas だという理解で正しいのならば。
真ん中の clisp の実行画面の [3], [4], [5] でコンパイルしてロードし直して、8-Queens の時間をはかってます。

しかし Gauche て自動的にバイトコンパイルするわけですね。考えりゃ当然なのかもしれませんが、気づきませんでした。

通りすがりのlisper 通りすがりのlisper 2007/06/30 18:19 目が節穴してました orz
下段のほうの結果ならそんなもんでしょうね。Gauche は結構最適化もがんばってるみたいですから。

hogeloghogelog 2007/07/02 21:02 やーまあ処理系の出力わりと削りましたし。
ってーか GCL はどうやら本当にすごいっぽくてびっくりでした。同じコードが処理系でここまで速度の違いがでるとは。

トラックバック - http://d.hatena.ne.jp/hogelog/20070628

June 24(Sun), 2007

[] 無線LANめんどい

使ってる無線LAN子機は Buffalo の WLI-U2-KG54L。環境は Vine Linux。

  • まずは apt-get から ndiswrapper, kernel-module-ndiswrapper(kernel のバージョンにあわせたやつ), wireless-tools, wpa_supplicant とか入れた。
  • Windows 2000用の WLI-U2-KG54L ドライバを ndiswrapper -i NETU2KGL.INF でインストール
  • 子機を USB 端子に差し込んでも(lspci, ndiswrapper -l とかで)認識してくんないので usbutils を入れる。lsusb, ndiswrapper -l でも認識されるようになる。
  • modprobe ndiswrapper したらフリーズした。カーネルのスタックサイズが云々という話じゃないかなと思う。
  • カーネルの再構築→めんどくさい
  • 今日は雨だしあきらめる
トラックバック - http://d.hatena.ne.jp/hogelog/20070624

June 23(Sat), 2007 大学のレポートに Brainfuck とか下品なお言葉書いていいのかねえ

[] Vine Linux 入れた

無線LAN の設定めどい。とりあえず有線でつないだ。GNOME がうざくて困る。.Xclients からたちあげたいんだけど、どうすんだっけなあ。俺は evilwm が使いてーのですよ。

あと emacs キーバインドが使えない場所が多くて不便。窓使いの憂鬱を使えばどこでも好きなところで emacs キーバインドだったんけど。

[] COINS で Brainfuck のコンパイラ (3)

さて、前回までで中身からっぽの実行ファイルを出力するところまでは書いた

いちおう実行ファイルを出力するところまで書きました。クラスファイルとかソースとかもぶちこんだアーカイブ。

http://konbu.s13.xrea.com/lib/coins/bffront-20070623.tar.bz2

% tar jxf bffront-20070623.tar.bz2
% cd bffront
% ./bfc.sh example/hello.bf
% ./a.out
Hello World!
% ./bfc.sh example/echo.bf
% ./a.out
sdfijasi
sdfijasi

%

UNIX な環境で、COINS のクラスファイルがクラスパスに入ってるならこんな感じで実行できるはず。

SimpleMain.java (COINS のアーカイブの example ディレクトリにも入ってます)、coins.ir.hir.HIR, coins.ir.hir.HIR0, coins.sym.Sym,coins.sym.Sym0 あたりの情報をもとに、 Brainfuck → HIR するコードを書きました。

まああとは Brainfuck から C言語に変換して、そっから COINS のC言語コンパイラを使って目的とする HIR を出力させたり。

そんなわけで以下コード。変更加えた BFtoHIR.java だけ。全コードは bffront-20070623.tar.bz2 に。

続きを読む

トラックバック - http://d.hatena.ne.jp/hogelog/20070623

June 22(Fri), 2007

[] ハードディスクに Linux 入れよ

cygwin じゃあなんだかんだで色々不便もあったりする。VMWare Player は不便は特に無いけど、パフォーマンスはやっぱりちょと落ちる。主にメモリが足らん。メモリが1GBくらいあれば平気な気するけど。

あー、やっぱ久々に FreeBSD 入れようかなあ。めんどくさいし、たいして OSOS した探究心も無いからとりあえず Vine 入れとこ。大学の計算機に入ってる OS と合わせとくと楽なことも多いし。

トラックバック - http://d.hatena.ne.jp/hogelog/20070622

June 21(Thu), 2007

[] ふつーにてこずってます

COINS で書いてる Brainfuck コンパイラが。うーん。なんか「,.」あたりは呼べたりすっけど、あちこちのほげが volatile でほげほげとか言われたり。たぶん volatile がどうこうとかいうわけじゃなくて、ふつーにへぼく間違いまくったコード書いてんだと思う。いいかげんちゃんと http://www.coins-project.org/ のドキュメントとか読まなきゃいけないのかもしれない。

Brainfuck -> C は簡単

まあ、書くまでもないことか。つーかまあ Brainfuck -> HIR も簡単なんだろうけど、俺が HIR の構造と COINS の使い方をよくわかってないから書けてねえだけだな。

#include <stdio.h>

int bfc(FILE *);
int main(int argc, char *argv[]){
  FILE *fp;
  if(argc==1)
    return 0;
  if((fp = fopen(argv[argc-1], "r")) == NULL){
    printf("cannot open file\n");
    return 1;
  }
  bfc(fp);
  return 0;
}
int bfc(FILE *bf){
  int c;
  puts("#include <stdio.h>");
  puts("#define MAXMEM 30000");
  puts("int main(){");
  puts("static char mem[MAXMEM];");
  puts("int mp = 0;");
  while((c = fgetc(bf)) != EOF){
    switch(c){
      case '+': puts("++mem[mp];"); break;
      case '-': puts("--mem[mp];"); break;
      case '>': puts("++mp;"); break;
      case '<': puts("--mp;"); break;
      case '.': puts("putchar(mem[mp]);"); break;
      case ',': puts("mem[mp] = getchar();"); break;
      case '[': puts("while(mem[mp]){"); break;
      case ']': puts("}"); break;
    }
  }
  puts("return 0;}");
  return 0;
}

あーなるほど

VarNode とか使いまわしちゃ駄目なんだなー、とかやって少しは進む。HIR.assignStmt がうまくない。

トラックバック - http://d.hatena.ne.jp/hogelog/20070621

June 18(Mon), 2007 まだbfコンパイラ書けてないのに見切り発車で書き始める

[] COINS で Brainfuck のコンパイラ (1)

「COINS を使えば簡単にコンパイラが作れるよ」という宣伝文句にのせられて、試しに COINS を利用して Brainfuck のコンパイラを作ってみましょう。実用上の意味はありませんけれども、入門編ということで。

参考文献は

あたりです。

JDK、ANT のインストール

COINS のコンパイラ(C、Fortran77)を利用するだけなら JRE だけでもいいですけど、コンパイラを作りたいならば JDK 1.4 以降と Apache Ant が必要。なんかまあ、適当に入れておいてください。

公式には JDK 5 までが動作確認されてるみたいです。一応手元の環境では JDK 6 で動かしてますけど、(たぶん)ちゃんと動いてます。

あと GNU Make も必要なので、無い人はそれも。

COINS のインストール

まずはアンケートなどに答えつつ、Jar アーカイブのダウンロードを。

http://www.coins-project.org/download/dl.cgi

ダウンロードするのはどっちでもいいですけど、まあ日本語のドキュメントなどが付いててお得ってことで日本語版で。

適当なところにインストールしましょう。ここでは「~/lib」あたりにインストールしてみます。

~/lib  % jar xf coins-1.4.2.2-ja.jar
~/lib  % cd ..
~  % cat >hoge.c
#include <stdio.h>
int main(){puts("hogehoge");}
~  % java -classpath lib/coins-1.4.2.2-ja/classes coins.driver.Driver -coins:assembler=as -b x86 hoge.c
~  % ./a.out
hogehoge
~  %

うーん大学で生まれたものなんて「がくじつてき」にはきっとすごいんだけど使いにくいに違いない、という俗な偏見を砕く簡単さ。

COINS の開発環境づくり

そこまでやったら、あとは coins-1.4.2.2-ja/src 以下に 適当なディレクトリを掘って、コンパイラドライバと対象言語(Brainfuck)から HIR(高水準内部表現)への変換のためのコードを書けばいいだけです。

クラスパスの設定

bash 系だったら .profile とかに「 export CLASSPATH=$CLASSPATH:.:~/lib/coins-1.4.2.2-ja/classes 」とか、csh 系だったら setenv とかで、環境変数クラスパスに追加しておくと「java -cp ~/lib/coins-1.4.2.2-ja/classes ...」とかしなくてよくなるので、後々楽だと思います。

[] COINS で Brainfuck のコンパイラ (2)

とりあえず、コンパイラプログラムのドライバ部分を作ります。コマンドライン引数を読んでファイルを開いたり、オプションを設定したりほげほげほげ……というのは面倒なので、COINS で用意されている coins.driver.Driver クラスを使います。こいつを継承することで、めんどくさいところはだいたいうまいことやってくれます。

Brainfuck のフロントエンドは bffront パッケージとしてまとめて、BFDriver, BFtoHIR という二つのクラスから作ることにします。 BFDriver は coins.driver.Driver を継承した Brainfuck のドライバです。あと一つ、拡張子を設定するファイルも作る必要があります。拡張子指定ファイルは bfsuffix としました。

http://konbu.s13.xrea.com/lib/coins/bffront-070618.jar

% jar xf bffront-070618.jar
% cd bffront
% ls
BFDriver.java  BFtoHIR.java  bfsuffix  build.xml  classes/  hello.bf
% java -cp $CLASSPATH:classes bffront.BFDriver -coins:suffix=bfsuffix -coins:assembler=as -b x86 hello.bf
% ./a.out
% java -cp $CLASSPATH:classes bffront.BFDriver -coins:suffix=bfsuffix -coins:assembler=as -b x86 hello.bf -S
% cat hello.s
 .ident "Coins Compiler version: coins-1.4.2.2 + BackEnd-0.8.1"
/* JavaCG for target:x86 convention:standard */

        .section .text
        .align  4
        .global main
main:
        pushl   %ebp
        movl    %esp,%ebp
.L2:
        leave
        ret

%

見てわかりますが、まだ BFtoHIR が空っぽなので、中身が空っぽのプログラムを吐くだけです。コンパイラの体裁だけ整えたところ。

以下コード。

続きを読む

[] ふと気付いた。

俺、とある問題でトップ記録保持者だ。世界中からキワモノ中のキワモノが集まるあなごるで!

hello world ですけど。

http://golf.shinh.org/p.rb?hello+world#ranking

一番最初に PHP で恥ずかしげもなく 13B の Hello, World! したのが俺ってことですね。光栄の至り!

June 14(Thu), 2007

[] 日本人だなあ俺も

大学の図書館で Bjarne Stroustrup 先生の

C++ Programming Language, The

C++ Programming Language, The

を借りてきた。まず思ったのが、表紙にある著者名が超でけえ。本のタイトルよりも著者名の方が大きい。「The Creator of C++」なんて肩書まで表紙に書いちゃってる。これが欧米人のノリなんだろか。

あと全然関係無いけど、電通大で情報系な授業受けたりしてて思うんだけど、意外と *UNIX なソフトとか、あんま好きじゃない人多いね。 Emacs 使ってて C-[PNFB] とかも使ってなかったりするんだから。それでもプログラム書いたりして、補完機能など使わず律儀にファイル名全部打ち込んで cc 、./a.out して課題のプログラミングをこなしていったりする。きっと GNU screen とか vim なんて、ずっと使わんのだろうなあ。

まあいつも vim でプログラム書いてる俺だって、Visual Studio とか Eclipse とか好きな人とかからすると変ちくりんに見えたりするのだろうけれど。

Bjarne Stroustrup インタビュー (?)

http://www.kh.rim.or.jp/~nagamura/misc/stroustrup-interview.html

やっばい超おもしれえ

[] Coins めも(1)

大学の実験で Coins いじってるんでめも。コンパイラの作り方は

http://www.coins-project.org/advanceduse/index.html

あたりに軽く書いてある。

あと情報処理学会誌でやってた連載「21世紀のコンパイラの道しるべ」の連載第一回(Vol.47 No.4 2006年4月号)と第二回(Vol.47 No.5 2006年5月号)では C言語のサブセットの C0 言語というもののコンパイラの作り方を解説している。第三回以降では SSA 最適化とかの話が書かれてました。

Coins はコンパイルの過程にて、まずソース言語から高水準内部表現(HIR)に変換、それから低水準内部表現(LIR)に変換、ほんでもって実際のマシンのアセンブラコードに変換して、アセンブルします。なんで、新たにコンパイラを作るにはソース言語から HIR への変換をすればいいわけです。

ほんだば HIR ってどんなんさっつーのを調べよう。

http://www.coins-project.org/

あたりから色々たどって、この辺とか

http://www.coins-project.org/COINSdoc/hir/hir-frame.html

http://www.coins-project.org/international/COINSdoc.en/infra/infra-frame.html

あとなにより Coins に含まれてる src/coins/ir/hir/HIR.java とかあたり読むべしとのこと。もしくは javadoc-ja/coins/ir/hir/HIR.html とか。

さてと。読も。

とりあえず

やっぱソース読むのが一番早いかなたぶん。

coins/ir/hir/*.java

とか。

いややっぱり

ソース読んでコンパイラ書いてあれこれ「ん? よくわかんねーぞ?」な部分が出てから

http://www.coins-project.org/advanceduse/index.html

とか読むとありがたさ倍増。

トラックバック - http://d.hatena.ne.jp/hogelog/20070614

June 13(Wed), 2007

[][] IDEっつーもんを使ってみようかなと。

Java6 環境のついでに NetBeans もインストール。ちょっとしたプログラム書く必要のあるレポート課題があるんで、NetBeans 使って Java で消化してみよう。

http://java.sun.com/javase/ja/6/download.html

こっからダウンロード、インストール。わりと時間かかるっけど、まあ気長に。

サンのドキュメントでも読んでのんびり待ちましょう。

http://java.sun.com/javase/reference/api.jsp

つーか日本語資料多いな。日本の Sun の中の人はがんばってるんですね。

さて。

インストールも済んでちまちまとコードを書いたり。うーん、当たり前だが全部 vim だけでコード書くのとは全然違う。

うーん。習得している Java の知識を使いにくい。NetBeans が生成したコードのどの隙間に好き勝手なコードを書いていいのかわからん。今回のレポートのプログラムはやっぱし vim で書こう。どうせ一回使っておさらばなプログラムだし。

あ、

コンパイルが速くなるのは良かったです。

nowokaynowokay 2007/06/17 22:36 「Javaクラス」を作れば、通常通りだと思います。

hogeloghogelog 2007/06/17 23:47 なんか昔 VC で MFC 使ってプログラミングしたときの、全然できなさ加減を思いだして、つい逃げました。
マウスを使ったルックアンドフィールな UI は苦手意識が強いってだけかもしれません。なんでもそうかもしれませんが、慣れるまでは居心地悪いんですよね。
あとまあ最大の居心地の悪さは、エディタの違いだったりするんですけど。これも慣れりゃ慣れますけど。

トラックバック - http://d.hatena.ne.jp/hogelog/20070613

June 12(Tue), 2007

[]

大学の実験で COINS いじったり VerilogHDL いじったり。楽しいなあまったく。とりあえず COINS の環境を自宅 PC でも整える。普通にC言語のプログラムがコンパイルできる。楽しいなこれは。とりあえずなんか簡単な言語のコンパイラでも作ろう。

[] volatile ってなんだ。

そういえば俺最近C言語の本とか読んでねえなあと思って、今大学の図書館で K&R の原本を借りてちょいちょい読んでる。英語慣れしたいから英語の本読んでんだけど、なんか変に読み飛ばす癖が付いてるような気もしてほげら。

Appendix がありがたいです。Grammer とか Library とか。volatile の説明はよーわからんかった。ぐぐって調べたら、うん、よくわからんはたらきをする修飾子するらしい。わからんっつーか、微妙というか。基本的には最適化を防ぐ感じらしい。

ライブラリは色々あってびっくりした。例えば tmpnam とか。

~/docs/c  % cat tmpname.c
#include <stdio.h>
int main(){
        puts(tmpnam(NULL));
        return 0;
}
~/docs/c  % cc tmpname.c -o tmp
~/docs/c  % ./tmp
/tmp/t924.0
~/docs/c  %

なんと親切な関数だろう。誰だ C言語は皮を被ったアセンブリ言語とか言った奴は。

俺は「Java はライブラリが充実していて便利だね!」とか言う前に、手元のC言語の標準ライブラリくらいはもうちょっと理解してるべきだと思った。

トラックバック - http://d.hatena.ne.jp/hogelog/20070612

June 10(Sun), 2007

[] SVG+JavaScript な組み合わせでアニメーション on Firefox

まあ表題の通り。

http://konbu.s13.xrea.com/lib/js/furiko_anim.svg

ちなみにこの動きはバネっぽい振り子の運動のシミュレーションみたいなそんなかんじ。Firefox1.5以降用。

無限ループの中で

  setTimeout(function(){hogehoge...}, time_quantum);

とかやって、hogehoge 部分で SVG 要素をいじる操作すればアニメーションになるよねー、というかんじ。

以下リンク先の SVG画像のコード。

続きを読む

[][] レポートの書き方

明日提出のレポートを、まあこんなもんかなというところまで纏めて、思った。なんか俺はレポートの書き方というものを間違っているのではないかと。数値計算のレポートなのに、数値計算数値計算した考察とかはたぶんレポートの1/10かそれ以下くらいにしかならない。アルゴリズムとか計算プログラムの設計方針とかが1/3くらいで、残りはプログラムとか枝葉末節なスクリプトのコードとかが占める。うーん。

たくさん書けばそのうち慣れっかねー。

June 09(Sat), 2007

追記(2007/06/24)

ダイクストラ法の復習をしました。以下に書いてあるのは全然ダイクストラ法じゃないということが判明しました。とっぺんぱらりのぷう

一応書き直してみた。けどなんつうか、問題例がいいかげん過ぎて参考にはならないような。「#define EDGECOST 1」とか。普通はこの部分が色々な値になる。

[][] ダイクストラ法をC言語で。

なんか最近微妙にまわりでダイクストラ法がブームらしいので、C言語で書いてみる。つっても、汎用的な書き方ってのをどうやるかは知らないんだけど。大学の同級生とか後輩とかがプログラムで迷路を解く課題に苦しめられたらしいので、俺的理解のダイクストラ法で迷路を解いてみる。

コードが長くなっちゃうんで、問題となる迷路はコードに埋め込みでこんな5×5のcharで与える。sがスタート地点、gがゴール地点、0が通路で1が壁を意味する。斜め移動は無し、地点間のコストは全て1。

(文字列末尾の '\0' 入れると長さ6の char だけど気にしない)

	char *route_dat[] = {
		"s0001",
		"10100",
		"00000",
		"01011",
		"0000g"
	};

ほんでまあ、この元となる経路データ route_dat から、最短経路を求めるのに適した経路データ構造に変換してからダイクストラ法で解いた。

実行結果はこんな。

% ./dijkstra
(0,0)
(0,1)
(1,1)
(2,1)
(2,2)
(3,2)
(4,2)
(4,3)
(4,4)

うんまあとりあえずこの問題では合ってるらしいよ。

肝心のデータ構造とダイクストラ法を用いた関数はこんな。

struct node{
  char key; // 元々の文字
  int col, row; // 座標
  struct node *link[4]; // リンク
  int linked_count; // このノードからリンクしている数

  int is_shortest; // 既に最短経路か否か
  int cost; // スタート地点からのコスト
  struct node *parent; // このノードの親ノード
};
typedef struct{
  int cols, rows;
  struct node nodes[MAX_COL][MAX_ROW];
  struct node *start, *goal;
} Route;
int relax(Route *route, struct node *curnode){
  int i;
  for(i=0;i<curnode->linked_count;++i){
    struct node *linked = curnode->link[i];
    int newcost = curnode->cost + EDGECOST;
    if(linked->cost > newcost){
      linked->cost = newcost;
      linked->parent = curnode;
    }
  }
  return 1;
}
struct node *nextnode(Route *route){
  struct node *minnode = NULL;
  int i, j;
  for(i=0;i<route->cols;++i){
    for(j=0;j<route->rows;++j){
      struct node *n = &route->nodes[i][j];
      if(!n->is_shortest && (minnode==NULL || minnode->cost > n->cost)){
        minnode = n;
      }
    }
  }
  minnode->is_shortest = 1;
  return minnode;
}
int dijkstra(Route *route, struct node *start, struct node *goal){
  struct node *curnode = start;
  while(curnode != goal){
    relax(route, curnode); // 最短経路がわかった点からパスがある点の更新
    curnode = nextnode(route); // コストが一番小さい点を次の点に
    if(curnode == NULL){
      return 0;
    }
  }
  return 1;
}

ダイクストラ法の実装は適当。ここではいいかげんな二次元配列で実装してますけど、本当は二分ヒープで実装したプライオリティーキューとかでやると良いらしいですよ。

以下全コード。データの変換にわりと行数つかってる。

続きを読む

[] マウス脳とキーボード脳

なんかこう、マウスでかちかちぐいーんかち、とやってるときと、キーボードでぺちぺちぺちとやってる時では、脳味噌のモードが違う気がする。

[] まあそんなことはあとで考える。

いいかげん月曜提出のレポート終わらせて、次のレポートにとりかかりますよ、と。しかしあれだなあ。だいたい週に2、3個のレポート課題がなんかの講義で出るから、学期終わるまでは常にレポートある状態なんだな。まあ嫌いじゃない。溜めっちまうと辛いけど。今期は順番に消化中。

というわけでいきますか。常微分方程式の数値計算レポート書くます。プログラム書くのは直ぐ終わったけど数学的な考察とかに手こずります。まあもうすぐ終わらせる。

次にとりくむレポートは楽しい楽しいコンパイラ。数値計算も楽しさ無いわけじゃないけれども。

トラックバック - http://d.hatena.ne.jp/hogelog/20070609

June 08(Fri), 2007

[] Java 習作。

http://konbu.s13.xrea.com/lib/Draw.jar

適当に書いたドロープログラム。ソースコードとかも同梱。保存とかエクスポート機能とかつけてみるところまではやった。

ダブルバッファリングとやらをまったくやっていない。Graphics2D オブジェクトを312個書くなら、馬鹿正直に直接に312回 draw を呼ぶ。

これは流石にそのうちやる。>ダブルバッファリング

Graphics2D オブジェクトってなんのことだ>俺

たぶん Shape オブジェクトとか書こうと思った、のかなあ。

動作環境とか

たぶん JRE1.5 以降で動く。ウィンドウズはダブルクリックで、linux とかだと java -jar Draw.jar 。ソースコードも jar に同梱。コンパイルは javac *.java で。

電通大のJ科の学生は Java 実験でこれをコピーして出したらばれると思う。来年もこの課題やるのか知らないけど。

トラックバック - http://d.hatena.ne.jp/hogelog/20070608

June 07(Thu), 2007 main=195 のやつ。

[] main めも

http://d.hatena.ne.jp/shinichiro_h/20060830

shinhさんのコード参考に。

% cat imain.c
int main = 0x90c332b0;
% cc imain.c -o imain
% ./imain.exe ; echo $?
50
% cat cmain.c
char main[] = "\xb0\x32\xc3";
% cc cmain.c -o cmain
% ./cmain.exe ; echo $?
50
%

なるほどなあ。

一応書いておくと

b0 32		mov $32, %eax
c3			ret
90			nop

ですね。

参考文献

http://www.intel.com/jp/download/index.htm

http://www.intel.com/products/processor/manuals/index.htm

この辺。

日本語だと「IA-32 インテル® アーキテクチャー・ソフトウェア・デベロッパーズ・マニュアル」あたり。英語だと「Intel® 64 and IA-32 Architectures Software Developer's Manual」。

トラックバック - http://d.hatena.ne.jp/hogelog/20070607

June 05(Tue), 2007

[] 今日も計算機室にこもってレポート。

講義無い時間はこもってレポート書き。なんだけど、あんまし進まんかった。なんでなのかなんてのはわかってる。Cで書いた数値計算のプログラムを動かしたり、結果をいじったりするために、初めて使ってみた awk が思った以上におもしろくて、レポートにまで手があましまわらんかた。まあ、awk でやってたのはレポートに使うデータの整理だったりするんで、0じゃねえんだけど。時間と労力の先行投資と言って言えないこともないかねえ。まあ実際便利で、今後多用すると思う。

今回の実用例。なんだこれは。えーと、振り子運動のほげほげを求めるプログラムの誤差の値とかです。

% cat hoge
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e100   = 5.082833e+03
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e200   = 3.424186e+01
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e400   = 1.831664e+00
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e800   = 3.552234e-01
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e1600  = 1.140982e-01
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e3200  = 4.637212e-02
# Euler
  alpha = 0.000000,theta0 = 0.100000, omega0 = 0.000000, e6400  = 2.098815e-02

まあそんなんはどうでもいいんですけど。この結果を色々いじって LaTeX に埋め込んだり、gnuplot に投げてグラフを描いたり、したいわけですよ。そんなとき、awk みたいなひとが便利。

% cat hoge |awk '{if($11){printf("%.4e\n",before/$11);before=$11}}'
0.0000e+00
1.4844e+02
1.8694e+01
5.1564e+00
3.1133e+00
2.4605e+00
2.2094e+00
%

Builtin な色々のおかげでワンライナーが楽です。

もちろん Perl なんかでも同じことはできるんだけど、

% cat hoge |perl -ne'@a=/[^\s]+/g;printf"%.4e\n",$a[10] if$a[10]'
5.0828e+03
3.4242e+01
1.8317e+00
3.5522e-01
1.1410e-01
4.6372e-02
2.0988e-02
%

うーんまあこの場合どっちが使い捨てワンライナー書くの楽な気分かっつーと、俺は使うの初めてだったけど、それでも awk のが楽に感じた。

トラックバック - http://d.hatena.ne.jp/hogelog/20070605
最近のコメント
Connection: close