はじめてのにき

_ 末尾再帰とか

http://blog.goo.ne.jp/no_orz_no_life/e/e7110098e80d89e28082065d32e9dd6b

の fact とか sum を見てて、 あらなんで3つ式あるのかなーと一瞬思ったんだけど、 まあたぶん末尾再帰の最適化かけたいという話だと思う。

で、そういえば GCC はどのくらい無茶なものを 末尾再帰にしてくれるのかなーとか思って色々やってみたら、 どうもすごく単純な足し算掛け算くらいしかできないぽかった。

まぁそんなもんかーと GCC を見ると、

     if (act->add && !a_acc)
       a_acc = create_tailcall_accumulator ("add_acc", first,
                                            integer_zero_node);

     if (act->mult && !m_acc)
       m_acc = create_tailcall_accumulator ("mult_acc", first,
                                            integer_one_node);

とかあって、やはり足し算と掛け算だけ特殊処理されてるのかな、 って感じだった。

関数型言語系だと、末尾が cons だった場合なんかにも、 似たような処理をしてやれば ずいぶんと色々とラクになるんじゃないかなぁとか思った。

あと、足し算掛け算以外を色々考えてる間に書いた、

def factdiv(n)
  if n==1
    1.0
  else
    n/factdiv(n-1)
  end
end

というような関数は、 つまり (2*4*8*...)/(1*3*5*...) という感じの値を返すわけだけど、 この値は 1.25 sqrt(N) くらいの数字になるみたいだった。 正確には (1*3*5*7*...)/(2*4*6*...) になってる時は 0.8 sqrt(N) くらいになってるので、この二つを繰り返すというか。

さてこれってなんか今まで見たことあるっけ… どうも見たことない気がするんだけど、 なんか有名な法則とかがありそうではある。

(23:39)

_ 年越し

年越す時に書いてたコードは spoj のゴルフだと思う。 たぶん kamil 。 spoj のゴルフはなんかよくわからんくらい短いものが結構あって、 なんか答え埋め込みとかになってるやつもあるのかなぁ。

年明けてからは BF_PRIME で、正月早々 Brainfuck ってのもどうなんですかね… しかもどうも勝てる気配があまりなくてですね…

kinaba さんの書いておられた、 なんかに特化した言語作るってのはいいかもなぁと思ったので、 Brainfuck の短いコードを出力するプログラムに特化した言語というのはどうか…

去年は今一つ、色んなことに慣れすぎてて特に何も無かったなぁ…という感じがした。 そいうことを思いながらはてなとか見てみた。

• 年始の WebKit についての紹介は妙に頑張ってるなあ
• コードを愛でる話はまぁそれなりに色々まとめたなぁ
• 一方 TCC の話はひどいなぁ
• TLE/ICFPC は残念な感じだったなぁ

とかあったんですが、このへんは知ってることまとめたりとかそういうのばっかで、 今一つ新鮮なことではなくて。

というわけで自分的に一番重要だったことは wake は今年作ったんだなぁということな気がする。

あとまぁ後半は Starcraft2 やってたなぁとしか言えないんじゃないかね。

(23:57)

_ spoj

文字通り一日中ゴルフしてた…

http://www.spoj.pl/SHORTEN/ranks/

とりあえず7位まで。問題多すぎですがな… まぁ codegolf よりは軽い問題が多いのはありがたいか。

トップの人は普通の問題に強烈に強い印象で、 2位の人は bash がおかしいことになってる感じぽい。

しかしなんか bash って使えるコマンド変わってる疑惑があるのがやる気を削がれるが

(01:35)

_ るびー

http://www.atdot.net/~ko1/diary/201101.html#d4

まぁこいうのはどこでも時々起きる系なのかなあよく知らんけど

Ruby については ruby-dev は「こわい」という話を ささださんにしたらこわくないよと言われた気がする。 当時もうまく説明できなかったけど、今もよくわからない。 ささださんの書いてる fundamental な人が多いと感じがするというのは、 割とその理由の一つかもしれないけどわからない。

ドキュメントは新しい熱心な人が聞きながら作る、ってのは まぁ一般的によくある話だとなんじゃないかなぁ。 そしてそれでいいんじゃないかなぁと思う。 よくわかってる人が書いたドキュメントって往々にして 新しい人にとって全然便利じゃなかったりするよね…

(23:49)

_ golf場 TODO

なんか IRC で話してていくつか

• 8 characters hello world 。8種類しか文字使えない hello を書けというもの。 goruby が h だけでいいのはいいかげんあれだし HELLO, WORLD! とかにしてやればいいか
• edit distance がコードサイズになってないといけない cyclic な quine 。これ書けるかまだわからんからとりあえず解いてから…
• rejudge button 。 random base な解答はちょっとアレなので、 deadline つきの新しい問題は rejudge button をつけて、それを押すと解答の check をもう一度走らせる、ってもの。 time limit が厳しい解答がかわいそうになるかもなので、 rejudge の時は time limit を増やすと良い

(05:25)

_ random seed

rejudge よりは rand seed 全部殺すのが良いんじゃないかと言われた。 そんなの無理だと思ってたんだけど、結構できそうな気もしてきた

• rm /dev/urandom; cp /dev/zero /dev/urandom
• personality(personality(0xffffffff) | ADDR_NO_RANDOMIZE) で address randomization は全滅するらしい
• rdtsc は cr4.tsd というのをセットすると殺せるらしい
• gettimeofday はフック
• getrusage あたりが rdtsc 内部的に使ってたりしないだろうか

最後の3つは色々互いに絡んでる恐れがあるかな。

話としては、

• 基本的にはコードが長くならなきゃいいわけなんで、言語実装が勝手に呼ぶ srand の seed として使われてるシステムコールさえ殺せば問題なし
• rdtsc 殺しても kernel 内部で使っててかつそのシステムコールを言語処理系が seed として使ってると終わるので、やはり使ってる system call を全部殺すのが良さげ
• 今時の gettimeofday は vsyscall とかそのへんの仕組みで userland で rdtsc 呼んでるとか無いだろうか→となると libc hook を復活させないといけなくてだるい気もする
• 言語実装が勝手に自力で rdtsc を呼んでる…ってことはさすがに無いだろうか

あとは他に乱数源ってあったかなあ… 普通に考えると /dev/urandom とか time 系だけだと思うけど…

(11:09)

_ SHORTEN

http://www.typemiss.net/2011/01/spoj-shorten.html

で書かれてる通りテストケースかなり適当なんだよなぁ。

http://twitter.com/kinaba/status/23392088473214977

まず kinaba さんが書いておられる通り出力フォーマットが適当ってのがあって、 それはまぁたぶん scanf で読んでるっぽい感じの問題が多くて、 そっちはまぁ

https://www.spoj.pl/SHORTEN/embed/rules/

あたりにも書いてあるからまぁいいとして。

問題はテストケース見せてないからなんとかなってるだけーって程度に テストケースが十分に無いやつがあるってことだよな。 例えば SUDCHECK なんてテストケースの数の bit 数があれば 解答埋め込めちゃうから、 こんなもんすごい数のテストケースが無いと ルール無用なゴルフとしては全く成立してないのだよな。

https://www.spoj.pl/SHORTEN/problems/SUDCHECK/

そんなこんなでまぁ色々やる気は起きない要因はあるんだけど、 なんか BF 使う問題とかあったりとかはちょっと面白いかとおもう。

てかこのへんの制約は ICPC のためにほげほげな SPOJ だから、って理由がほとんどだよなぁ。 あくまでゴルフ場ではないっつーか。

あと与えられてる sample inputs が異様に簡単なものばかり、ってのも ICPC 的な感じなんだろうなぁ。 問題の spec から難しいテストケースを考える、 ってのは重要な能力ではあるものの、 なんかどうもプログラムコンテストとしては余計なものに感じちゃったりもする。

まあなんだかんだ言いつつ3位。

一番面白かった問題(というか解いてないが)は INTER で ruby だと gets するだけで TLE 。 https://www.spoj.pl/SHORTEN/problems/INTER/

(08:20)

_ latency

http://d.hatena.ne.jp/kawango/20110107

ニコニコではこのへんが問題になるのなーという感じもあるけど、 本当にそうなんか? グーグルだとなんか色々調べたけど、 ある程度高速な回線だと結局クライアントのオーバヘッドがデカいぞ、 って話で HTML を頑張って色々やったらユーザの幸せがだいぶ増えたとかいう話があって (たしかこの本…だっけ http://www.amazon.com/High-Performance-Web-Sites-Essential/dp/0596529309)、 ニコニコも体感だと動画とか以前に、最初にページ出るまでが結構長いんだけどな。

(10:09)

_ ruby 1.9 と gets

いくらなんでも gets だけでタイムアウトしてるのはおかしいが、 測ってみると ruby1.9 の gets はマジで遅い。 これは M17N の影響だったりするんだろうか。

> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"  0.19s user 0.17s system 91% cpu 0.396 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"  1.32s user 0.19s system 94% cpu 1.591 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"
sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"  0.21s user 0.12s system 93% cpu 0.360 total

(10:46)

_ SIZECON

狂ったルールのおかげでたのしい。 ここまで来るとはなぁ。

http://www.spoj.pl/SHORTEN/ranks/SIZECON/

あと 2B は今の方針だと全然ダメ。 どうすればいいかなー

解いた問題数 60 のまんまでトップになりたいとか思いはじめてきた。

(11:39)

_ 1位

http://www.spoj.pl/SHORTEN/ranks/

になった。 60問しか解いてないまんまなので伸びしろもそれなりにあるだろうっていうか そこらじゅう伸びしろだらけだろうと思う。

どうでもいいけどこの動画をずっと聞いている。 なんでこいうの好きなのか。

http://www.nicovideo.jp/watch/sm12628181

(17:01)

_ 1位とりかえされた

のでまぁその人は64問全部解いてるし 60問縛りとか意味わからんことやめて残りも解くことに。 適当に codegolf.com のコードの流用とかしつつ romancal 解いたので 1位取り戻した。 久々に見るとローマ数字とか死んでいいな。 だいたいゴルフ的には 8 は IIX であるべきだろうに。

残り3問だけど、

• factorad はこの手の飽き飽き…解いてしまえばたぶん成績良いんだけどね…
• sqdiff はめんどくさそうというかどうせ数値誤差とかうんぬんで WA 喰らって試行錯誤するんだろうなぁ…
• spiral は oblongular number spirals の悪夢を思い起こす絵が描いてあったのでやりたくない

など、3つとも回避したい雰囲気なのであるがー

まぁ spiral はあきらかに簡単そうではあるよね…

(00:58)

_ 49.7 7.5

経験上50切るとやばいんですよ…

TODO ちゃんと喰う

(08:48)

_ facebook hacker cup

気がついたら終わっていた。 topcoder とか codejam 系だったのかな。 じゃあまあいいんだけど。

飯をたくさん喰うという努力をしたら 速攻で気持ち悪くなって元々体調悪いのとコンボでキツくなった。 なんとかならんかという貧弱さ。

dc は手で書くのがかったるいので 適当な言語から生成したいと思う。 bc がそれであるのは知ってるんだけど、 そうじゃなくて短い dc コードを出力させたいのだよね当然

なるべくレジスタ使わないで stack を… とかいう話はいくらでも研究とかありそうだが

(19:05)

_ pric

http://d.hatena.ne.jp/colun/20110110

おおおすごいなー

全く覚えてないので適当に思い出すために手元のコードについてメモ。

• pric.c: なんかすごい遅い
• pric_ref.c: なんか強烈に遅い
• primechecker.c: -m32 だと 11.9 秒くらい、これが submit してあるバージョンぽい気がする
• pric2.c: -m32 だと 10.5 秒くらい。 oxy さんのやつを実装してみようと思ったけどアルゴリズムを忘れてしまった上に自力で再構成できなくてよくわからん実験を色々していたみたいだ
• perfect: 答えはこのファイルに書いてある
• pric_check.rb: なんか check してくれるらしいが謎
• pric_gen.rb: コードを短くしてくれるらしい
• pric_test.c: 今さっき書いたいいかげんなアルゴリズムでどの程度漏れるかをチェックするために書いた

(13:43)

_ starcraft2

しばらく 1v1 はしんどいので suspend してたのだけど 今日はたくさんやってみた。

ここ2ヶ月くらいの進捗は…

• 3v3 dia になった
• 4v4 dia になった(今日)
• 1v1 と 2v2 は platinum のまま
• キャンペーン hard でクリアした。ミッション系の achievement は全取得。
• チャレンジ全部 gold にした。
• チーム戦のドサクサに紛れてどうでもいい achievement をそこはかとなく取ったり。 zerglot とか…

gateway unit + colo という展開は まぁ結構勝てたし相手の行動次第では それも相変わらずいいんだけど、 あまりにもそいう P が多すぎるのか どうも勝率が悪くなってきた気がする。

というわけで色々試したりしている…

• vZ は即 VR で 2 台程度出すと強い。 7roach とかもギリギリかえる。 VR 出し続けるんじゃなくて、すぐに colo に移行するといい感じに hydra さんを焼ける
• vP は悩ましかったのだけど、 gas core 遅らせて zealot*4+stalker*2 で殴りつつ expo という BO が teamliquid に書いてあったのでやってみた。良いかも。
• vT はよくわからん。うまい人は VR 出してたりするからマネしてみたりしたけど全く役にたたない… DT が面白いと思うんだけど、 MM rush に普通に殺されたりするからなあ…

(03:35)

_ そうそんなことより

w3m ってリリースとかするんだな…って感じだった。 とりあえずがんばって全パッチを CVS head からのアレにするか。

ていうか開発してるんだったら無難な patch は入れてもらいたいなー ということで頑張るか。 というか cookie の時間とかはオプションつけてくださってるんだなー

(04:18)

_ anti virus

無料体験な mcaffee の期限が切れるようだった。 どうせ SC2 しかやってないマシンだし セキュリチーソフトとか無くてもいいのかなぁ とか思ったけど、

• 一応ブラウザくらいはリプレイダウンロードする時とかに使う
• ゲーム系のサイトとかっていつも見てるようなサイトに比べて diversity デカいから危険度高めかも
• windows マシンはともかくこのネットワークの packet とか見られるとうざいかも。 twitter のパスワードくらいは平文で飛んでそう

とかいうこと考えて、まぁ無料のを入れておくことにした。 いい時代になったなぁ。

でまぁ無料のも色々あるみたいなんだけど、 Panda Cloud Antivirus というのにしてみた。 理由は

• 名前が面白い
• 名前に Cloud とか入ってて興味をそそる
• MS essential とかは芸が無い感じ
• 2ch によると速いらしい

あたり。 下の方は割と後付けなんで、名前重要だなぁとか思った。

SC2 の邪魔したりしなければいいなぁ。

(23:04)

_ shinh.org

どうでもいいけどいまさらながら一応ふっかつ。

kwskk.shinh.org がまだみたいだけどまぁどうでもいい…

あとは mirc とかを daemontools の管理下に置くのと、 twitter と…

それとゴルフ場は lighttpd 捨てたいな… virtual host の設定が簡単なのはいいので、 ゴルフ場だけを apache の管理下に移動すればいいのかな。 apache の fcgi ってどうなるんかね…

(02:24)

_ kernel VM advent calendar

http://atnd.org/events/10701

http://twitter.com/yuyarin/status/26664147030642688 を見て、いくつか見てみた。 読んでないのが多いので、かなり面白かったから暇な時にもっと読みたい。

(03:13)

_ dc の話

dc のなるべく短いコードを書きたいという話をして そのへんの研究とかってどういうの調べればいいんですかねえ、 と聞いていたら x87 とかと提案してもらった。

なるほどたしかに…

(23:02)

_ wait

なんか長いジョブ始めてしまってから、 これ終わったらアレを実行して欲しいよなーとか思うことがある… とかいう話をしていて自己解決した。

% sleep 10
^Z
zsh: suspended  sleep 10
% bg
[1]  + continued  sleep 10
% wait && ls
[1]  + done       sleep 10

sleep 10 が長いジョブで ls が終わったら始めたいコマンド。

(00:09)

_ gknot

今一つなんの大会なんかわからんのだけど、 なんか強烈にむつかしい問題を解かせるとかなんかな…

http://felicity.iiit.ac.in/gknot/

朝3時30分まで起きてるとかは結構だるいので 明日の朝問題どんなんだったか見るとかで良さげ…

http://shinh.skr.jp/dat_dir/planner.html#tz0=9&tz1=5.5&time0_0=2011-01-23%2003%3A30%3A00&time1_0=2011-01-23%2018&plan_0=test%20run&time0_1=2011-01-24%2003%3A30%3A00&time1_1=2011-01-24%2018&plan_1=main%20event&time0_2=&time1_2=&plan_2=&time0_3=&time1_3=&plan_3=

(20:08)

_ pbzip2

bzip2 の解凍が遅いので pbzip2 というのを試してみる。 どうも圧縮の仕方を変えて並列にできるから速いという話らしいので、 decompress は別に速くならなさそうだが…

% la primes.txt
-rw-r--r-- 1 i 52M Feb 24  2008 primes.txt
% time bzip2 primes.txt
bzip2 primes.txt  13.78s user 0.29s system 84% cpu 16.680 total
% la primes.txt.bz2
-rw-r--r-- 1 i 18M Feb 24  2008 primes.txt.bz2
% time bzip2 -d primes.txt.bz2
bzip2 -d primes.txt.bz2  5.55s user 0.34s system 97% cpu 6.036 total
% time bzip2 primes.txt
bzip2 primes.txt  13.46s user 0.21s system 98% cpu 13.894 total
% time pbzip2 -d primes.txt.bz2
pbzip2 -d primes.txt.bz2  5.45s user 0.40s system 94% cpu 6.216 total
% time pbzip2 primes.txt
pbzip2 primes.txt  13.98s user 1.08s system 173% cpu 8.699 total
% time pbzip2 -d primes.txt.bz2
pbzip2 -d primes.txt.bz2  5.54s user 0.40s system 172% cpu 3.439 total

別にはやくない。 それにしても bzip2 より遅いのかなともう一度やってみたら

% time pbzip2 -d primes.txt.bz2
pbzip2 -d primes.txt.bz2  5.51s user 0.35s system 101% cpu 5.781 total

まぁ似たようなもんってことかな

(22:22)

_ xz

ついでに。

% time xz -z primes.txt
xz -z primes.txt  81.90s user 0.61s system 98% cpu 1:23.70 total
% la primes.txt.xz
-rw-r--r-- 1 i 6.0M Feb 24  2008 primes.txt.xz
% time xz -d primes.txt.xz
xz -d primes.txt.xz  2.45s user 0.31s system 96% cpu 2.857 total

圧縮アホほど遅いが展開はすごくはやい。

圧縮率落としてみる

% time xz -z -0 primes.txt
xz -z -0 primes.txt  9.41s user 0.18s system 98% cpu 9.767 total
% la primes.txt.xz
-rw-r--r-- 1 i 9.7M Feb 24  2008 primes.txt.xz
% time xz -d primes.txt.xz
xz -d primes.txt.xz  2.72s user 0.24s system 99% cpu 2.985 total

うーんすごくいいじゃないかこれ… これがはやく流行ってくれればいいなぁ… と思ったので bzip2 のことは忘れることにするか…

(22:38)

_ ふぃずばず!

http://golf.shinh.org/p.rb?FizzBuzz#Ruby

53B!!

人間やればできると信じるとできるもんだなー

55B の時はまだ縮むんじゃないかなーと思う感じだったけど、 ここまで来るとなかなかこれ以上無さげだな…

(03:10)

_ うーんなんだこれ

別解がほぼ存在しないぞこれ。 56B も 55B もわらわらあったというのに。

なにやら結構うまくハマってるというか、 これで終了という感が本気で強いかなー。

(03:24)

_ starcraft2

dia になった。

今年入ってからの勝率は

T 9/9 50%
P 10/4 71%
Z 17/6 73%
overall 36/19 65%

とかなんで vT 本当になんとかすべき。 vP vZ は色々試してみてるけど、 vT は何を試したもんだかみたいな感じで余裕がない

(01:11)

_ ぷよぷよ

http://okajima.air-nifty.com/b/2011/01/2011-ffac.html

ruby で書き散らかして18分23秒だった。

動画撮りながらやったので時間は正確。

最近新山さんの recordwin がたいへんべんりと気付いたので、 コード書く時に動画撮ってみたりしている。

http://www.unixuser.org/~euske/vnc2swf/recordwin.html

やってみててわかるのはぶつぶつ言いながらだと、 ぬいぐるみに話しかけるのと一緒で頭整理しやすい気がするというのと、 気が散らないから他に余計なことしないというのがあって割と良い気がする。 成果物はまぁどうでもいい退屈なものなのだけど…

なんかマトモなのができたらアップロードしたりしてもいいかなぁと思うけど、 youtube だと 15 分で終わらにゃならんし、 ニコ動だと解像度の制限がキツいし、 みたいな感じで色々めんどいっぽい。 ぷよぷよ程度でも15分じゃ終わらんぽいしなー。

(14:39)