飲み物だから太らない


Y.Sawaの日記と言うか、雑記と言うか。
(ちょっと)まじめなページ
この日記の内容は私及び第三者の意志に関わらず、私の所属するいかなる組織の意見・知識とは無関係です。

2010-06-06

生存報告と、その他もろもろ 00:55

一応生きているってことで。

Google CodeJam参加

今年もRound2で敗退。俺・・・本当に過去にWorld Final行けたんだよね?今回の敗退の主要因は、Aにはまってしまったこと。A-smallに1時間半かけるとか。しかもA-largeでミスするとか!白状すると、実はA-smallもバグ有りコードで提出しているので、smallも本当は通ってません。

関数の最小値を求める

GCJミスした部分について、せっかくなので書く。

あるイテレータブルな何か(配列リストコンテナ等)があって、各要素を受理する関数があったとしましょう。このとき、関数の返り値の最小値を求めたい。手続き型っぽく書くとこんな感じ。

int function(T t);
Container<T> container;
int min = Integer.MAX_VALUE;
for(T t: container){
  value = func(t)
  if(min < value)
    min = value;
}

あるいは、関数型っぽく書くとこんな感じ。

min (map func container);

問題は、上の手続き型のソースの中の、Integer.MAX_VALUEってのが曲者で、左辺がintだからInteger.MAX_VALUEだけど、longだとLong.MAX_VALUEになるし、BigIntegerだとどうにもならなかったりする。

今回の場合、大きめの値をminに代入してたものの、もっと大きくしておかなきゃいけなかったらしく大失敗。

解決案1 最初の項目を特別扱いする

containerの第一要素の結果をminに格納することで、変なminの値にならないようにする。

int min = func(container.get(0));
for(T t: container){
  value = func(t)
  if(min < value)
    min = value;
}

問題点: 第一要素が取り出しにくいときには書きにくい。


解決案2

minを特別な値-1にする。

int min = -1;
for(T t: container){
  value = func(t)
  if(min == -1 || min < value)
    min = value;
}

問題点: ifの中が読みにくくなってよろしくない。

解決案3

特殊なデータ構造作成する。

class MinimumObject<V>{
  boolean set_min;
  public V min;
  public MinimumObject(){}
  public int set(V v){
    if(!set_min || min.compare(v) > 0)
       min = v;
  }
}
MinimumObject<Integer> min = new MinimumObject<Integer>();
for(T t: container){
  min.set(value = func(t));

問題点: これしきのことで長くないっすか?

ということで、いまだに有効な改善策が見つかっておりません。



PC環境とか

ところで世間ではiPadとやらが発売され大人気な様ですが、みんなが何を期待してあれを買っているのか、いまだにわからないです。世間がほしがるものを作る職務についているのに、世間の需要がわからないのはよくないことなのだと思いますが、自分の生活があのデバイスによって変わることが全く想像できません。

Googleマップを持ち運べる点についてはいいと思うんですが、それってノートPCでもできるよなあと。使ってる人を見ても、パラダイムシフトが発生する気がしなくて。それにあれ、プログラミングしにくそうじゃない?

ということで、I(dea)Padを買いました。http://ascii.jp/elem/000/000/499/499886/

重さは、1.5kgとiPadの倍くらいですが、それなりに動くみたいです。これを買おうと決断したきっかけは、「NetBookVisual Studioって普通に動くし使えるよ」という先輩の一言でした。

CPU的には、10年前のPentium 4初期といろんな意味で同程度ですが、HDDはふんだんに使えるし、メモリも1Gあるのでそんなに困らない感じです。メイン開発マシンにはならないだろうけど。

pぁpぁ 2010/06/07 02:56 2は「未初期化を表す特別な値」が「-1」だから読みづらいのであって、nullにできる型を使えばもう少し読みやすくなるきが。
if (min == null || min > value)

おrzおrz 2010/06/07 02:59 グーグル株式会社に懐柔されないの?

succeedsucceed 2010/06/11 00:34 >pぁ
BigIntegerみたいなのだと、nullにすることになると思うのだけど、あるいはMaybeモナドを使うという手もあると思うのだけど、結局それって同じことでは?
未初期化である可能性がある、というのが不満で、例えばdo{}while()みたいな書き方ができればいいと思うのだけど。
うまくIteratorぶん回せばdo whileに落とせるっちゃあ落とせるけど・・・・
ということで、誰かクックレシピ的なのを希望。

pぁpぁ 2010/06/14 23:30 nullにすれば-1と違って、まちがって未初期化のまま扱おうとしたら「ちゃんと」実行時エラーになってくれるのは利点だと思うよ。あと、空のシーケンスを渡したとき自然にnullが返るというのもあるので、「Java使うなら」結構まともな落としどころだと思うけど。
それで不満ならパターンマッチが網羅してるか静的チェックしてくれる言語を使うのかな、いやJavaでもできるかもしれないけどclassでエンコードするのは「これしきのことで長く」なるに決まってる(偏見

succeedsucceed 2010/06/15 00:27 うーん。そうかもなあ。
ただ、長くなるのはJavaに限った話ではなくて、「設計をちゃんとすればするほど、たいていの言語は長くなる」と思う。(仕様が増えるからね・・・)。
これを解決する手法って、ライブラリくらいしか思いつかないのだけど、他にあるのかなあ。

pぁpぁ 2010/06/15 01:27 無名関数がインラインに簡単に記述できる言語なら、このパターンを抽象化した高階関数作って、更新関数を渡すように使えば結構短くできる予感。というかfoldとMaybeでいける気がする。
あとはマクロなら(ry

pぁpぁ 2010/06/15 01:30 というのは全部ライブラリってことになるか。高階関数ライブラリ、もしくはマクロライブラリ。とはいえminの代わりにmax使いたくなるたびにライブラリを増やさなきゃいけないとかいうことがないのは圧倒的な強み

pぁpぁ 2010/06/15 01:45 設計をちゃんとするほど長くなってしまうかどうかは、問題によると思う。数年ぶりのOcaml
# let option_fold updater ls =
List.fold_left (fun ox y -> match ox with None -> Some y | Some x -> Some (updater x y)) None ls;;
val option_fold : ('a -> 'a -> 'a) -> 'a list -> 'a option = <fun>
# option_fold max [];;
- : 'a option = None
# option_fold max [1; 3; 2];;
- : int option = Some 3