明日はgoogle code jam japan

Posted by YpsilonTAKAI On 2011年9月30日金曜日 0 コメント
明日は Google Code Jam Japan に挑戦です。

どこまで行けるかわかりませんがね。


READ MORE

Project Euler のサイトのデザインが変りましたね

Posted by YpsilonTAKAI On 2011年9月25日日曜日 0 コメント
この週末にProject Eulerのサイトのデザインが変更になりました。

Googleの変更に似た感じになっています。
最近のトレンドなんでしょうか。

僕はまだレベル2なんですけど、レベルを表わすマークも変更されてます。
僕は前の立体の方が好きでしたね、だんだん角が増えていくので、ぱっと見てどんなだかわかるようになってました。 新しいやつは、上下が良くわからなくなってます。 それが狙いなんでしょうね。

最近別件で忙しくて手をつけてませんけど、そろそろ涼しくなってきたことだし、再開しましょうかね。


READ MORE

Clojureの関数のメモ化 >> memoize 1.1 と 1.2

Posted by YpsilonTAKAI On 2011年9月9日金曜日 0 コメント
前にclojureのmemoize関数の動きがだめだっていう話を書きました。
このポストも関心のある方がいらっしゃるようなので、ちょっと追加の情報を。
べつに目新しいものではありませんけど、日本語の情報が無いみたいなので。

さて、 何がだめなのかをくりかえすと、再帰で定義されている関数をmemoizeを使ってメモ化しても、内部での 再帰呼び出しにメモ化が効かないという現象です。
実はこれ、clojureの1.2からのことで、1.1では問題なく動きます。 

これは、以下に出てくる解決策から考えると、1.2で、関数の名前の解決方法に変更があったためだと思われます。

以下ちょっと長くなります。




例によってフィボナッチ数を求める関数を再帰を使ってで定義して、1.1環境で実行してみます。
user> (clojure-version)
"1.1.0"

(defn fib [n]
(do
(println "Called with : " n)
(if (<= n 1)
n
(+ (fib (dec n)) (fib (- n 2))))))


user> (fib 5)
Called with : 5
Called with : 4
Called with : 3
Called with : 2
Called with : 1
Called with : 0
Called with : 1
Called with : 2
Called with : 1
Called with : 0
Called with : 3
Called with : 2
Called with : 1
Called with : 0
Called with : 1
5

再帰的に呼ばれているのが分ります。 これを、memoize関数でメモ化しして、同様に呼んでみます。


(def fib (memoize fib))

user> (fib 5)
Called with : 5
Called with : 4
Called with : 3
Called with : 2
Called with : 1
Called with : 0
5

1.2で実行したときに出て来ていた(fib 1),(fib 2),(fib 3) が出てきません。メモにヒットして関数が呼ばれなくなったためです。memoizeちゃんと動いています。

同じことを1.2でやると、このようにはなりません。 (前のポスト参照)

この問題について、前回僕はマクロを作って解決したわけですが、他にこんな方法もあります。 

まず、メモ化する関数の定義を変更します。

(defn fib2 [n]
(do
(println "Called with | " n)
(if (<= n 1)
n
(+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

このように再帰で呼ばれる関数名に「#'」をつけます。(なんでこうするのかについての考察は後で) そして1.1の時と同様にメモ化すればOKです。

やってみます。

user> (clojure-version)
"1.2.1"

(defn fib2 [n]
(do
(println "Called with : " n)
(if (<= n 1)
n
(+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

user> (fib2 5)
Called with : 5
Called with : 4
Called with : 3
Called with : 2
Called with : 1
Called with : 0
Called with : 1
Called with : 2
Called with : 1
Called with : 0
Called with : 3
Called with : 2
Called with : 1
Called with : 0
Called with : 1
5

(def fib2 (memoize fib2))

user> (fib2 5)
Called with : 5
Called with : 4
Called with : 3
Called with : 2
Called with : 1
Called with : 0
5

この通り 

さて、じゃあ、これはなんでうまく行くんでしょう
 以下の説明は僕の推測です。1.2の変分を見てもよくわからなくて、 なんとなくしか理解できてなくて、今一つ現象を性格に捉えられていない。 
 間違っていたら指摘ください 


 関数が再帰的に呼ばれるとき、1.1では、「関数が評価される時点でこの名前を持っている関数を呼ぶ」という仕組みだったものが、1.2では「定義時点この名前が差している関数を呼ぶ」という方式に変更になった。
そのため、1.2では、初めの関数そのものが再帰で呼ばれてしまい、memoizeがうまく動かなくなってしまった。 

この解決策でつかった「#'」はリーダーマクロで(var xxx)の略。「この名前のvarを取得する」ということを意味している。 なので、1.1の時と同じ定義をさせることができるのです。

推測ここまで


 さて、この方式はちょっと気に入らない。
だって、メモ化するつもりの関数はあらかじめ定義をそれ用に書いておけってことになってしまうわけで、 たとえば、あとから、「あ、これメモ化してほうがいいな」と思った場合、関数定義に手を入れることになってしまう。
だったら、僕の作ったマクロで再定義しちゃったほうが手間は少ない。 

ということで、僕はこの方法は却下。
勉強にはなったけどね。


READ MORE

github.gist ってembedできるんだね

Posted by YpsilonTAKAI On 2011年9月1日木曜日 0 コメント
clojure関連のサイトを見ていたら、ソースコードの表示にgist使っているような感じのものがあった。
調べてみたら、gistでそんな機能を提供してるらしい。 しらなかった。

んで、使ってみた。



どうだろ? あれ? シンタックスハイライトは無いのかな?

と思ったら、ファイル名に拡張子、この場合cljを指定してやったら、出た。

これ、いいじゃない。
ProjectEulerはこっちでやろうかな。





READ MORE