|
|
|
|
|
||
|
||
| << | 2012/02 | >> | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | |||
| サイト本体 | 昔の更新履歴兼雑記 | タイトル一覧 |
分類は アーカイブ任せにした方がいいのかも。
題材が面白そうだったので、久々にマラソンに参加してみた。それなりにマジメにやったけど11位。個人的には ambrose というのに勝ったので良し。
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15023
たぶん、 DNA のシーケンサが読んだ情報を保存するファイルフォーマットのファイルがあって、それをなるだけ圧縮しろ、ただし遅いとペナルティ、って話だった。入ってる情報は DNA の配列がたくさん (50k個とかくらい) 、って感じ。具体的には、
あんまこのフォーマットについて…とかぐぐっても今一つよくわからなかったので、基本的に数秘術的にカンでそれぞれの値の意味を想像していった感じだった。結果としてわかったのは、
base は自明だけど1個保存するのに 2bit しかいらない。 range coder や lz な圧縮するとやや小さくなるけど、速度的に元が取れないのでやめた。
flowgram 一個一個に特定の配列 TGAGCATCGA... みたいなのが固定で割り当てられてて、値が大きい部分が base としてあらわれる。数値が 50 から 150 なら1個、 150 から 250 なら 2個、という具合に。 例えば配列 TGAG に対して 130, 20, 90, 211 とかだと、 T が1個あって、 20 は小さいから G はなくて、 次の A が1個あって、次の G は2個あって、という具合なので、 base は TAGG とかになる。
というような感じなので、 flowgram の値が 0-50 であるか、 50-150 であるか、 150-250 であるか…みたいなのは、 base からわかるので、その部分は保存しなくていい。
flow_index はえらい base と相関の高いデータだなぁと思ってたけど、 flowgram と base の位置を関連づけるものなので、上記の特定の配列がわかれば base から演繹できるので保存する必要なし。
quality は後ろの値に近い値が出やすい。 8bit のデータなので、後ろの値ごとに range coder を準備する感じで圧縮した。連続してる時はさらに連続する傾向があるみたいだったので、後ろ2つが同じだった場合はまた別の range coder 作る感じにした。
flowgram の細かい部分は、前の quality とやや相関があるみたいだったので、 quality のおおざっぱな値ごとに range coder を作った。
エントロピー符号は、最初は huffman 使ってたんだけど、 range coder の方が少しだけ小さくなって、かつある程度速くしたら huffman とそんなに変わらなかったので、 range coder にした。上位の方の人は速くしたら huffman の方がいいって言ってるんで、 huffman 側をあんま高速化しなかったせいかな…と思う。実際上位の人達より遅いみたいだ。
フォーラムを見た感じ、一番大きい敗因は quality の値をエンコードする時に flowgram の値をコンテキストとして使わなかったことなのかな、と思った。
あとは base の最初が削れる(これは当然気付いてたけど順位変えるくらいデカいわけじゃないのでやらなかった)のと、あと最後の方もなんか削れたらしいぽいのがわかってなかった。それとヘッダは明らかにもうちょい削れたけど、これも見積った感じあんま順位に関係ないのでやらなかった。
最後の方は quality か flowgram のどっちかが削れるんだろうなーと思って、いろいろと試したもののあんまりうまくいかなくて、ひょっとして LZ とか遅いけど案外小さくなるのかなーと試してみて全然ダメだと確認したところで諦めた感じだった。
今回途中経過のスコアとかを google docs で管理してみた。まあ役に立った気がする。別に面白くないけど、 submission 11 から 13 の間で flow_index 全く保存する必要ないことに気付いたんだなぁ…とか。
https://docs.google.com/spreadsheet/ccc?key=0AolcvzoWgN21dHA3LVhodjhra3hWaXBqeXdqTC1VZlE
正直最近マラソン飽きまくってて、どの問題見てもやる気が微塵も起きなくなってきていたんだけど、今回はかなり楽しかった。
あ、 range coder についてはこの記事
http://codezine.jp/article/detail/443
LZ と圧縮全般については、このサイト
http://www.geocities.jp/m_hiroi/light/index.html#python_algo
をそれぞれかなり参考にさせてもらいました。ありがたかった。
range coder は今まで「なんか小難しそうな物体」ってイメージで、たぶん原理は聞いたこともあった気がするんだけど全く覚えてなかった。でも今回で割と簡単で良いものだと学べたのは良かったと思う。
Mach-O バイナリをコード見ながら逆アセンブルする方法が無いってのがずっと困っていました。つまり linux でよくやっている objdump -S みたいなことがやりたかったんですが、 objdump -S は Mach-O に対しては動かないし、 otool -tvV もソースコードは見せてくれないし、っていう。でまぁ一念発起して binutils というか libbfd をいじってみたのでした。
今回はじめて FSF なソフトに patch 投げてみて、まぁ特に著作権の処理とかどのくらい時間かかるもんなのかよくわからなくて、こちらのかた以外にあまり体験談的なのが見つからなかったので、なんか書いていみようかと。
とりあえず適当にパッチ書き。経験上デカいパッチいきなり投げるヤツはうざがられるので、なんか小さめな目標で…ってことで objdump -S を .o に対してだけ動くようなものを書きました。というのは Mac の実行ファイルや動的ライブラリって、 dSYM っていう別なバンドルに保存されてるんで。参考: http://wiki.dwarfstd.org/index.php?title=Apple’s_%22Lazy%22_DWARF_Scheme
で、パッチ書けたので ML に入った。過去ログとか見るのめんどうだったので、深く考えずパッチ投げた。どうも ML にパッチを本文の末尾にくっつけて投げるスタイルが多いように見えたので適当にマネしました。添付ファイルと違ってコメントつけやすいから、こういう文化なんだろうな…と予想。
11月26日土曜にパッチ投げて月曜に返事をもらえました。要はみんな仕事でやってる感じぽい。適当にフィードバックを受けた部分を修正して再投稿。 OK とのこと。 Mach-O メンテナに Mach-O の部分見てもらって、 dwarf2.c とかちょっといじったのはグローバルメンテナの人が見てくれました。
で、 FSF に書面で著作権譲渡をしないといかんよ、と言われました。あれこれ探してみると、
http://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/
が見つかって、これの request-assign.future を assign _at_ gnu.org に送る感じでいいの? って聞いたところ、それでいいよ、とのこと。というわけでメールを送る。11月29日。
8日後、12月7日におへんじもらえて、この PDF 印刷してサインして送れ、とのこと。この日のうちに手紙送って、一応送ったよ、とメール。そのメールへの返事は12月9日。
12月9日に配達完了、とのこと。で、12月13日に手続き終わったぜーというメールをもらったので、コミットしてもらいました。
ざっくり2週間くらいで、まぁちょうどそんなもんかなーと思っていた程度でした。その間に他のパッチをしょぼしょぼ書いてたので、1つずつ送っていきました。一気に送るとややこしいですし、慣れてないうちはパッチAで指摘してもらったことが、パッチBにも必要、ってことが結構ありますし、まぁ全く急いでないし、っていう感じでした。
でまぁ昨日になってやっと私のほしかった dSYM 使って逆アセンブルにソース重ねる機能がつきました、と。
思ったのは、グーグルやら Chrome/WebKit にパッチ投げる時のグッドプラクティスがだいたいそのまんま使えるなぁ…というような。具体的には
まぁあんまプロジェクトによらないテクニックですな。
今さらだけど1年をふりかえる。
去年半分と今年は仕事で好き勝手なことやってたので楽しくて良かったと思う。感想は ukai さんは神というか足向けて寝れんレベルというか。
なんかまぁここ数年思ってる気がするけど、 sayさんの書いておられる、「昔とやっていることがあまり変らないので自分のやっている事に対して心動かされることがなくなってきている」って表現がそのまんまだなぁとか。やったことないことでも、どう考えてもできそうだなーって前もってわかってることには気合いが入らなかったりとか。あとなんか、最近「ほどほどにやりたいこと」が常に大量にある感じで、「すごいやりたいこと」があんま無いかなーとか。
今さらだけど1年をふりかえる。
去年半分と今年は仕事で好き勝手なことやってたので楽しくて良かったと思う。感想は ukai さんは神というか足向けて寝れんレベルというか。
なんかまぁここ数年思ってる気がするけど、 sayさんの書いておられる、「昔とやっていることがあまり変らないので自分のやっている事に対して心動かされることがなくなってきている」って表現がそのまんまだなぁとか。やったことないことでも、どう考えてもできそうだなーって前もってわかってることには気合いが入らなかったりとか。あとなんか、最近「ほどほどにやりたいこと」が常に大量にある感じで、「すごいやりたいこと」があんま無いかなーとか。
wake と sed のセパレータがちょっと違う場所があったのを適当に修正。
\%!; until (/;/) { #|fizzbuzz: l1,1 #%! { : }
\%!; $\=$/; #\(\) #|k(.);.*\1(.).*:"$2" #%! s/$/;0123456789;/
\%!; s/$/;0123456789;/; #|j(.):k$+;0123456789 #%! s/9;\(.*;\)/;\10/
\%!; s/9;(.*;)/;${+}0/; #|i:"1" #%! s/\(^\|#\);/\10;/
\%!; s/(^|#);/${+}0;/; #|i(.*)9:i$+ "0" #%! s/\(.\);[^;]*\1/;/
\%!; s@\(\)|(.);[^;]*\1| #|i(.*)(.):"$2" j$3 #%! s/;\(.\).*;/\1/
\%!; @;@; #|o.*[50]:"Buzz\n" #%! s/^/#/
\%!; s/;(.).*;/$1/; #|o(.*): "$+\n" #%! h
\%!; s/^/#/; #|f.*[50]:"FizzBuzz\n" #%! x
\%!; $n=$_; #|f.*:"Fizz\n" #%! s/^\(###\)*/Fizz/
\%!; s/^(###)*/Fizz/; #|n(.*),(.):l$(i$2),$3 #%! s/.*#//
\%!; s/.*#//; #|l101,\d: #%! s/[0-9;]*[05]$/Buzz/
\%!; s@[0-9;]*[05]$| #|l(.*),0:f$+ n$+,1 #%! s/z[0-9]*$/z/
\%!; @Buzz@; #|l(.*),1:o$+ n$+,2 #%! p
\%!; s/z[0-9]*$/z/; #|l(.*),2:o$+ n$+,0 #%! x
\%!; print; #|#: #%! { /;/!b }
\%!; $_=$n; #|#: #%! d
\%!; } # (C) 2011 #|#: Shinichiro Hamaji #%i All Rights Reserved
忘れる前にこのコードについてメモ。
http://d.hatena.ne.jp/shinichiro_h/20111210#1323525496
正規表現なら、ってことで Perl, wake, sed あたりがいいだろうと最初に思いました。 wake を混ぜると改行が無いコードは書けないし、まぁそれなら縦に並べるかと思いました。プログラムの規模としては FizzBuzz くらいなら端末の縦幅におさまるし、正規表現しばりで適当に書けば、3言語でだいたい似たサイズになるかなぁと。
となると3つの言語をどう分割するか考えないといけない。 Polyglot ってのは、たいていは言語Aでは普通の式だけど、言語Bでは文字列リテラルに突入する、みたいな方法を考えることになります。例えば Ruby & Python だと、 '''' とかが、 Ruby では空文字列をあらわす式で、 Python では複数行文字列リテラルに突入なので、
'''' puts "Hello, ruby!" #'''; print "Hello, python!"
のようにして分離できたりします。
で、 Perl, wake, sed だと、これがさくっと思いつきませんでした。こいつらリテラルとか無さすぎ。
wake はパターンの部分は : 以外は割となんでも入るからなんとかなるだろうとして、 Perl & sed を考えてました。 sed のリテラルって言うと // だよなぁしかしコレ Perl でもリテラルで困ったなぁと思ってたところ、そういえば sed は \%% (ただし % は同じ文字ならなんでもいい) も正規表現リテラルなんでした、ってことでこれを使うことに。
バックスラッシュってたしか Perl だと参照取るとかだよねーということで、
% perl -le '\%!; print "hello"'
とかやってみて動くことを確認。これで sed が脱落してるので、この中で % を使わずに Perl と wake を書くといいか、と。 wake はどうせパターンの部分なんで、 : を使ってなくて、正規表現として invalid でない限りは何書いてもよいので、先に Perl をかたして、次 wake、最後にリテラルから復帰して sed 、って順序にしました。 wake は sed の右っかわに置くことはできなくて、これは sed が : を使うから。
でできたのが、
\%!; print "Hello, perl!\n" #|hello: "Hello, wake!\n" #%! iHello, sed!
という形。 wake の手前の #| は、 # で Perl はこれ以降完全にコメントになって、 | で wake は今までの文字列を無視します。無視っていうか、一応左っかわが正規表現として valid でないといけないけど、適当な Perl コードがマッチするわけないので、 | の右っかわだけが本質的な正規表現になる感じです。
wake と sed の境界の #%! は、 # で wake をコメントに突入させて、 % で sed の正規表現リテラルを脱出、ここまでの Perl プログラムと wake プログラムが正規表現としてマッチするわけないので、 ! をつけて、マッチしなければ以下の文を実行、って感じでやってます。
あとは実際のコードで例外的な部分。
2行目の
\%!; $\=$/; #\(\) #|k(.);.*\1(.).*:"$2" #%! s/$/;0123456789;/
の Perl のコードの末尾に奇妙な #\(\) がありますが、これは wake の \1 に対応する後方参照が無いと wake がさわぐので、 Perl のとこに隙間を用意して特に意味のない後方参照を追加してあります。
6,7行目
\%!; s@\(\)|(.);[^;]*\1| #|i(.*)(.):"$2" j$3 #%! s/;\(.\).*;/\1/ \%!; @;@; #|o.*[50]:"Buzz\n" #%! s/^/#/
wake の後方参照が、本来は $1 $2 のはずが $2 $3 になってます。これは Perl の方のコードに () が一度使われてるため。というわけで wake のコードだけひっこぬいてもここを変えないと動かない感じになってます。同じことが 11 行目でも起きています。
Perl の正規表現は2行に渡ってるので、 / を使うと sed が勝手に閉じちゃうので、 @ を使っています。2行に渡った正規表現はゴミが大量についてるので、 | で分離してます。 13,14行目も同じです。 \1 を使ってるから意味のない \(\) がついてるってのは2行目と同じです。
コード自体は、 sed は複数行に渡る正規表現が書けないから、横幅 20 文字制限が結構きびしくて、色々分割したりしました。で、これが割と Perl でもそのまま動くし横幅も小さいし、ってことで、最初書いてた Perl コードは捨てて、 Perl はほとんど sed と同じロジックになってます。
wake は配布パッケージに入れてあった test/fizz.wake を横幅ゴルフしたもので、 l がメインループ、 n がメインループを次に進める関数、 f が 3 の倍数時の出力処理、 o が 3 の倍数でない時の出力、 i がインクリメントで j が 1 文字だけのインクリメント、 k はそのヘルパです。
最後のコピーライトは、 Perl はコメント、 wake は実行されない命令、 sed は実行されない命令 i の引数、って感じです。
Esolang Advent Calendar の10日目になんとなく参加みたいな話です。自己紹介を書いておくと、好きな esolang は見た目よりむしろ中身重視というか、行なわれる処理や処理のしかたがユニークなものを好む傾向があるみたいです。あと先日 世界一の Befunge コーダーであることが判明しました(誇張)。
なにしようかなぁ考えたのですが、私の好きな言語のひとつに sed っていうか正規表現があるので、それについて。どの程度好きかというと、ほとんど 正規表現しか無いような wake という esoteric language を作ってみたことがある程度には好きな感じです。
正規表現ってヤツは普通文字列のマッチングに使うやつで、もちろんループとかは書けないわけですけど、しかしまぁちょっとした計算くらいなら割とできたりします。ループや出力の部分だけ、元の言語の機能から借りてやれば、割と色んなプログラムが書けます。例えば FizzBuzz
\%!; until (/;/) { #|fizzbuzz: l1,1 #%q; :
\%!; $\=$/; #\(\) #|k(.);.*\1(.).*:"$2" #%! s/$/;0123456789;/
\%!; s/$/;0123456789;/; #|j(.):k$+;0123456789 #%! s/9;\(.*;\)/;\10/
\%!; s/9;(.*;)/;${+}0/; #|i:"1" #%! s/\(^\|#\);/\10;/
\%!; s/(^|#);/${+}0;/; #|i(.*)9:i$+ "0" #%! s/\(.\);[^;]*\1/;/
\%!; s@\(\)|(.);[^;]*\1| #|i(.*)(.):"$2" j$3 #%! s/;\(.\).*;/\1/
\%!; @;@; #|o.*[50]:"Buzz\n" #%! s/^/#/
\%!; s/;(.).*;/$1/; #|o(.*): "$+\n" #%! h
\%!; s/^/#/; #|f.*[50]:"FizzBuzz\n" #%! x
\%!; $n=$_; #|f.*:"Fizz\n" #%! s/^\(###\)*/Fizz/
\%!; s/^(###)*/Fizz/; #|n(.*),(.):l$(i$2),$3 #%! s/.*#//
\%!; s/.*#//; #|l101,\d: #%! s/[0-9;]*[05]$/Buzz/
\%!; s@[0-9;]*[05]$| #|l(.*),0:f$+ n$+,1 #%! s/z[0-9]*$/z/
\%!; @Buzz@; #|l(.*),1:o$+ n$+,2 #%! p
\%!; s/z[0-9]*$/z/; #|l(.*),2:o$+ n$+,0 #%! x
\%!; print; #|#: #%q; /;/!b
\%!; $_=$n; #|#: #%! d
\%!; } # (C) 2011 #|#: Shinichiro Hamaji #%i All Rights Reserved
上のプログラムは (なるべく正規表現以外使わないようにしてある)Perl, wake, sed の polyglot になってます。つまりその3つの処理系どれでも FizzBuzz として実行できます。わかりやすいように左から Perl, wake, sed と、だいたい別れている構造になっています。それぞれ横幅20文字でおさえるかな…と思ったので、主にそのへんで苦労した気がします。
あとはまぁ適当にカウンタを作る説明など。
Perl なんかにある、正規表現ってヤツですが、後方参照があって、正規表現でマッチして置換、みたいなことができる言語だと、結構計算ができたりします。 0,1,2,..,8,9 を 1,2,3,...,9,0 に変換するような関数は、 Perl だと
sub inc { $_ = pop; s/$/;01234567890/; s/(.);.*\1(.).*/$2/; $_; } print inc(0), "\n"; print inc(4), "\n"; print inc(8), "\n";
という感じに書けます。 inc の真ん中2行がインクリメントをしている部分です。まず最初の、
s/$/;01234567890/;
というコレは、入力 X を、 X;01234567890 として、後ろにヘンな文字列をくっつけてるだけです。例えば入力が 4 の時は 4;01234567890 になります。で、次の、
s/(.);.*\1(.).*/$2/;
が本質です。最初の (.) は入力 X にマッチします。入力が 4 なら 4 ですね。その後 ;.* でセパレータと何文字が読み飛ばして、次に来るのが後方参照 \1 です。これは以前の括弧の中にマッチしているので、入力が 4 なら 4 です。つまりここまでで、 ;.* が ;0123 にマッチして、次の 4 まで読んだ状態、つまり残ってる文字列は 567890 です。後は簡単で、 (.).* で、最初の文字を2つ目の後方参照に保持した後、残りを読み捨てます。で、置換後文字列の $2 は 2つ目の後方参照 (.) なので、これは 567890 の先頭の文字であるところの 5 です。これで 4 が 5 に変換できてることが確認できました。
ここまでをまとめると、
(.) - 4 ;.* - ;0123 \1 - 4 (.) - 5 .* - 67890
というふうにマッチしています。
あとはまぁ頑張れば繰上がりを含むカウンタ、任意精度の加算、乗算などなんでもできます。結構頑張れば。
興味がある人は、加算についてはこのへん に書いたり、あと このあたりにもうちょっと具体的な問題を解いてた時のコメントがあったりします。
Perl は見るだけで吐き気とかを催す人がいるかもしれないので、拡張正規表現があれば基本一緒だよ、ということで他の言語でも適当に書き散らかしてみます。
def inc(x) x.to_s.sub(/$/, ';01234567890').sub(/(.);.*\1(.).*/, '\2').to_i end puts inc(0) puts inc(4) puts inc(8)
import re def inc(x): x = re.sub(r'$', ';01234567890', str(x)) x = re.sub(r'(.);.*\1(.).*', lambda m: m.group(2), x) return int(x) print inc(0) print inc(4) print inc(8)
JavaScript
function inc(x) { x = String(x).replace(/$/, ';01234567890'); return x.replace(/(.);.*\1(.).*/, "$2"); } console.log(inc(0)); console.log(inc(4)); console.log(inc(8));
とかなんとか。
今年から社会人みたいです。