ぼうメモ帳

2004-07-31 眠い

愛媛大会

| 愛媛大会を含むブックマーク

http://www.ehime-u.ac.jp/ICPC/problems/domestic/d2004/

テスト入力に対する出力例が公開されていました.ということで,早速テスト...うぎゃ,問題Dをミスっているという罠.2点で1つも円が作れないときに間違えているということが分かったので,バグを修正して完了.

2004-07-30 ただ作るだけじゃだめ このエントリーを含むブックマーク

当たり前のことですけど,研究者になるからには,ただ作るだけではだめですね.新しいことをして,評価して,さあどうよってなことをしないといけん.どうやって作ろうか考えることが楽しい私には向いてないみたいです.もうだめぽ

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

2004-07-28 研究疲れ このエントリーを含むブックマーク

最近、研究で疲れてます。8月の論文締め切り(あと正味2週間)に向けて、がんばって論文を書いている途中です。論文を書いて思ったことは、改めて文章化しようとすると、肝心なところが自分の中であやふやなままだったことに気づきました。いま、あわてて理屈付けしているところです。こんなんで良いのかなあ。

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

2004-07-18 なんかイライラする

wemaの改造

| wemaの改造を含むブックマーク

ちょっと変えればいけるだろうと踏んでたら、思ったよりもめんどくさそう。とりあえず、やらなきゃいけないのは、

ぐらいか。長そう…ゆっくりやるか。

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

2004-07-17 飲み会 このエントリーを含むブックマーク

飲み会から帰還しました。体調が悪いという理由で途中離脱。なんか、疲れてる。

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

2004-07-15 今夜も徹夜でつ

wema

| wemaを含むブックマーク

http://www.mikihoshi.com/wema/

つい先日、インストールしてみました。最初、どうやっても動かなかったんだけど、wema.tmpl*1を弄って何とか動かすことに成功しました。正直、疲れた。

で、使い始めて数日間の、ちょっとした戯言です。

まず、JavaScriptだけでここまでできるのかという感動と*2、自分が使いやすいように改造したいという欲望がふつふつと沸き起こってきました。プログラミングを10年近く行ってますけど、こんな感覚は久しぶりです。昔、この手のインターフェイスのプログラムを自分で作ったことがあるので*3、実はインターフェイスに微妙に不満があるというのも改造したいという欲望に結びついていたりします。

さて使用目的ですが、私は個人的なメモ帳として使用しています。気になったWEBへのリンクを保存しておいたり、研究論文のアイディアを散りばめておいたり、TODOリストを置いておいたり、本当に自分だけのホワイトボードとして使っています*4。どうしてもその時々によって使用するPCが異なり、しかも不精な私にとって、どこからでもアクセス・変更できるというのは、すごいメリットです*5。あと、ブラウザベースアプリケーションには独特の使い心地というのがあって、その使い心地が好きなのも使っている理由の一つです。

で、はっきり言って、私の使用目的では普通のwikiよりも使いやすいです。その理由は、「Wikiでは情報の配置が一次元なのに対し、wemaでは二次元なので、情報がコンパクトにまとめられる」の一言にまとめられます。すなわち、wikiは「リンクによる情報の構造化」という特徴があり*6、「2次元視覚化による情報の構造化」という特徴が追加されているということ。

さて、もし改造するとすればのアイディアです。wemaが付箋を基本オブジェクトとしたとき、各ページは付箋の集合になったと思います。このとき、付箋の集合は、ただの集合でしかないので、1つの付箋が複数の集合に所属できないだろうかと考えています*7。すなわち、ページは付箋の分類と、視覚化の場所でしかないということです。この機能を追加すると、wemaが本来持っている機能である「2次元視覚化による情報の構造化」と、「リンクによる情報の構造化」に加え、「分類(クラス)による情報の構造化」という機能が追加され、さらに情報の価値が上がるのではないでしょうか。さらに突き詰めると、「付箋を基本オブジェクトとしたとき、分類もまた付箋で表現された基本オブジェクトの一種である」というようなセマンティクスを与えると、CSを専攻している身としてはかなり楽しい世界が展開するなぁ、と考えています。

てか、そんなマニアックな注文があるんなら自分で作ればって感じなので、時間の都合がつけば土日を使って改造したいと思います。さて、眠いけど明日に向けて研究がんばるぞ!!

*1:だっけ?HTMLのテンプレが収まってるやつ

*2:いままでJavaScriptの解釈系(インタプリタとかコンパイラ)にしか興味がなかったので

*3マックを愛用してたころにHyperCardで作った・ソース紛失を理由に非公開

*4:この日記メモ帳としての役割を果たしてないし。名前を変えないとなあ

*5:本当にプライベートでばれちゃいけないもの以外は、実はWebブラウザ経由で誰でもどこからでもアクセスできるような、だめだめな情報管理をしていたりする

*6WWW一般に言えることだが、wikiはその特徴を凝縮していると思う

*7:これは、他の一般のソフトウェアに対して共通に持っている不満でもあります

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

2004-07-14 アルゴリズムコンテストきたー!!

アルゴリズムコンテスト

| アルゴリズムコンテストを含むブックマーク

http://www.aso.ecei.tohoku.ac.jp/alcon2004/

複数の写真から、パノラマ写真を作るアルゴリズムを競い合うコンテストらしいです。面白そうなので、今日、参加する決意をしました。

2枚の写真をx、yだけ移動させて重ね合わせるもの、回転も考慮するもの、拡大縮小も考慮するものと、問題の難易度は3つ用意されています。しかも、制限時間は300秒。複雑なアルゴリズムを用いれば良いというわけではないみたいですね。

とりあえず、一発勝負ネタでレベル1のちょー速いプログラムでも書いてみますか。

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

2004-07-11 中間発表…やる気が

FindBugsを使う

| FindBugsを使うを含むブックマーク

http://findbugs.sourceforge.net/index.html

にある、FindBugsというツールを使ってみました。そしたら、summaryのトップで、

Type Checked   Count  Bugs  Percentage
Outer Classes  118    131   111.02%
Inner Classes  34     24    70.59%
Interfaces     31     0     0.00%
Total          183    155   84.70%
16 Packages Analyzed

という結果が出ました...orz

で、納得がいかないので、結果を解析してみると、123個のバグは、クラス定数をパッケージprotectedにすべきというものでした。これは仕様なのでこのままで大丈夫。とりあえず、一安心。

で、他のバグを挙げてみると、

  • メソッドの引数や戻り値を配列するな(ごもっともです)
  • static な内部クラスになるべき(ごもっともです)
  • waitがループの中にない(見逃してください)

となっていました。まあ、致命的なバグはなさそうなので、とりあえずは一安心。

それにしても、日本語メッセージが表示されるのがすばらしいね。

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

2004-07-10 研究まにあわない

実装してみた

| 実装してみたを含むブックマーク

とりあえず、実装してみました。が、検証はしてません。使用した言語Javaで、掛かった時間は問題A、Bでそれぞれ10分、問題Cで30分、問題Dで1時間ほどです。あらかじめ方針を考えていたので、その分の時間を足せば、本番だったらこれで時間切れでしょう。国内予選の結果を見ると、4問解ければ予選突破か… 結局、勝負に勝った試合に負けた感じか?(年齢制限に引っかって出場権がない)。

問題AとBは、C言語を使えば、もっと短縮できたかもしれません。データの入力部のコーディングで無駄に時間を使いました(1〜2分のロス)。やはり、scanfの力は偉大です。J2SE1.5に移行するかな。問題Cは、楽しいアルゴリズムを考えるのが面倒になったので、全探索での解法を実装しました。実装だけなら10分ほどです。問題Dは、円の中心の座標を求める方法を考えるのにバカみたいに時間が掛かりました(バカみたいに2変数の連立2次方程式を解いてた。三角関数で一発だよ…orz)。

で、研究発表をするための許可を頂くための中間報告?をしなきゃならないので、問題EとFは後回しです。もっとも、今の進捗状況で許可が下りるとは思えんがな。

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

2004-07-09 微妙な負け方が悔しい

愛媛大会WEB予選

| 愛媛大会WEB予選を含むブックマーク

http://ccserv.adm.ehime-u.ac.jp/ICPC/jp/

いつの間にか、予選が開催されていたんですね。コーチとして名前を貸していたチームは、残念ながら負けてしまったそうです。残念。M1が一人いたので、来年があるとは言えませんでした。

で、いまさっき問題を眺めていました。

問題Aから問題Fまでの、日本語版のリストです。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/A.jp/A.html

問題A「花札シャッフル」は、カードシャッフルの問題ですね。これは、反転・反転・大反転(文字列のカット&ペーストと同じアルゴリズムで、数珠のプログラミングという本に載ってる)を行えば、配列の要素を反転させる関数1つで実現できるでしょう。サービス問題ってやつですね。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/B.jp/B.html

問題B「赤と黒」は、どれくらい広く領域を歩けるかの問題です。スタート地点を中心に、幅優先か深さ優先探索をしかけることで、あっという間に実現できるでしょう。(再帰のほうがかんたかな)

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/C.jp/C.html

問題C「単位分数の分割」は、ある分数が何通りの単位分数(分子が1の分数)の和で表現できるかという問題です。なんか、インド人が得意そう。正直、いまぱっと考えたけど、スマートアルゴリズムが思いつきません。おそらく、単位分数の和を求める分割ルールが存在して、それを適用しながら単位分数の和の集合を現す木構造の探索をすれば良いのではないかと思われます。まあ、分割ルールは単純に分数を再帰的にどんどんと分けていくってやつでいいんでないかな。で、分母の積が与えられた数を超えたらハイ終了、みたいな。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/D.jp/D.html

問題D「円と点」は、平面上に散らばってる点に、半径1のわっかを投げたときに一番多くの点を囲むには、どこにわっかを投げればよいかという問題です。精度は0.0001。適当な2点を通る円を作って(半径固定のため、円は2個に限定される)、それが囲むことができる点の数を求める。で、これを全部の可能な2点について調べつくせば、おのずとどの円が最強かを知ることができるのではないでしょうか。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/E.jp/E.html

問題E「水槽」は、区切りで分割された水槽の中に、各区切りごとに蛇口から水を適当に流したときの水の流れをシミュレートしろという問題。問題が長すぎてあまり詳しく読んでないんで、題意を外してたらすまん。で、シミュレーションしろとのことなので、私だったらイベントドリブンみたいな感じで解きますか。各区切りの容量と、入り込む水量はわかってるから、そこから何分後に溢れるってのも計算できる。で、その時間をプライオリティキューに乗せて、ひたすら時間順にイベントシミュレーションしていく。で、イベント発生時に各水槽の高さを計算できるようにしておき、終了時刻を最初っからキューに載せておけば自動的に求まる。そんなところでどうでしょう。でも、解析的に解けるべ、これ。

http://www.logos.ic.i.u-tokyo.ac.jp/acm-icpc/F.jp/F.html

問題F「交差点の名前」は、制約問題を解く問題。詳しくは自分で問題を読んで。データセットから、道をノードとするような半順序関係を生成して、問題として与えられた二つのノード間に順序が存在するかを調べればいいかと。あとは、道の方角を東西で塗り分けるだけっしょ。面倒ならば、線形計画問題に持ち込んで、解が存在するかしないかに問題を落としこんで、アルゴリズム辞典のサンプルソースを写すだけで解ける。(普通の再帰で十分対応できるから、オーバースペック気味で微妙。)

とりあえず、後で実際にプログラムを書いてみるか。目標は、ABCDが一問20分、EFが一問50分の計3時間。無理そう。

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

2004-07-07 暑い このエントリーを含むブックマーク

何が暑いって、住んでいる家の塗装のせいで、窓が開かないんですよ、この暑い中。それで、すごく暑いから、LANケーブル引っ張りまわして、玄関外まで出て涼みながら日記を書いてます。すげー涼しい。

同居人が写真撮影しながら、コエーを連発しています。それにしても暑い

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

2004-07-05 よるねはだめぽ

Javaの性能調査・その1

| Javaの性能調査・その1を含むブックマーク

100万頂点、200万ラインセグメントを扱うにはどれくらいのメモリ量が必要か調べる。Point2D.Doubleを使って、100万頂点は30Mbyte、Line2D.Doubleを使って、200万ラインセグメントは90Mbyteなので、トータルで110Mbyteほど必要…(なお、オブジェクトは配列に保存。配列の大きさも込)

で、もう少し調べると、Point2D.Doubleが1オブジェクトあたり22byte(8+8+6?)、Line2D.Doubleが1オブジェクトあたり38byte(8+8+8+8+6?)。まあ、こんなもんだろう。。。

実験するために、1000万まで求めたんだけど(-Xmx1024mとかして)、それぐらいの規模になるとインスタンス生成するだけで、マシンが止まる。危険だね。

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

2004-07-04 今週は飲み会が多すぎた

昨日は講座飲み。某計画について熱く語りすぎた。とりあえず、最後の夏休みである今年、実現させたい。

デッドロック

| デッドロックを含むブックマーク

やっぱり、リファクタリングをするなら、きちんとテストコードを書いておこう。

ここ2日間ぐらいかけて、研究用ツールの作成をしていました。と言っても、プログラム内のTODOタスクを一つずつこなしていっただけです。スレッドセーフ化したり、実行時例外をきちんと投げるようにしたり、などなどです。

そのあと、今週中に実現しないといけない新機能を盛り込みました。そして、テストコードを書いて、テスト!! …失敗。ここまでは良くあることだったのですが、新機能の部分ではいくら考えてもバグはない。

と、今までのテストコードを実行していくと… 動かない。

(1時間格闘中)

何で動かないんだろう。。。

(宴会中)

あ、スレッドセーフにしたときに起こしたデッドロックかも。

(酔ったままデバッグ中にて寝落ち)

今朝になってやっとバグを取ることができました。やっぱり、リファクタリングをした直後には、きちんとテストを実施しないとだめだなと実感しました。

それにしても、酒飲んでグデングデンの状態でデバッグしても、バグって見つかるもんなんだなあ。寝落ちさえ気をつければ。

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

2004-07-02 内定者懇親会は疲れた

水曜日内定者懇親会に参加してきました。とりあえず楽しめましたが、疲れました。

ambiguousで怒られた

| ambiguousで怒られたを含むブックマーク

このエラーで初めて怒られました。

Super.method( interfaceA )

Sub.method( interfaceB )

で、引数として

C implements interfaceA, interfaceB

を渡していたのが原因っぽそうです。

クラス図がだいぶ複雑になってきているから、やはり根本的に設計を見直さないといけない時期にきているのかなあ。

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