お天気プロコンと圧縮アルゴリズムについて - 兼雑記
https://beta.atcoder.jp/contests/wn2017_1/standings むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。 やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。 今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測
Unix v6 の C コンパイラが面白かった話 - 兼雑記
Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。 読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、 http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdf の「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。 コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。 構文木のノードの種類に対して switch してやること決める…的なものが、データドリブンな方法で書かれてます。データを保存するフォーマットは、 JSON とかではなく、時代が時代ですのでアセンブリです。こういうやつ https://github
Base64 decoder/encoder in Perl - 兼雑記
http://shinh.skr.jp/obf/b64_dec.pl dXNlIE1JTUU6OkJhc2U2NDtwcmludCBlbmNvZGVfYmFzZTY0IGpvaW4nJyw8PjsKX19FTkRfXwo+ s//v62/e+s//v60/e+s//v44/e+s//v39/e+s//v39/e+s//join/+s//v32/e+s//base64/ss+ s//v95/e+s//decode/+s//v32/e+s//print/+s//v59/e+s//Base64/+s//v58/e+s//v58/e +s//MIME/+s//v32/e+s//use/s/evalこの Base64 ぽく見える物体は Perl コードで、実行すると引数で指定したファイルに対する base64 デコーダとして機能します。 $ perl b64_dec.pl b64_dec.pl >
sedlisp.sed 00:54 - 2014-06-08 - 兼雑記
https://github.com/shinh/sedlisp Lisp インタプリタを書きました。 sed で。 https://github.com/shinh/sedlisp/blob/master/sedlisp.sed README に書いた通り、それなりにややこしいプログラムも動く気がします。具体的には eval.l として、 eval の無いところで eval を実装しました。で、その上で FizzBuzz なんかが動きます。これはつまり S 式のパースは省略した Lisp のインタプリタと言って良いので、 sed で書かれた Lisp の上で Lisp が動いて、その上で FizzBuzz が動いてることになります。ちなみにもう一段かますことはできませんでした。 Ruby で書いた実装でも動かないので、 eval.l がとりあえず循環できない作りになってしまってるみたいで
2011-08-01 - valgrind 論文読んだメモ - 兼雑記
時々 valgrind はオーパーツだとかそういう主張をしてたりします。コードとか論文とかチラ見くらいはしてたのですが、まあちゃんと眺めてみたのでメモ。 Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation http://valgrind.org/docs/valgrind2007.pdf 1. イントロ 1.1 DBA and DBI Dynamic binary analysis って種類のツールがあるんですよ、と紹介。その手のツールは Dynamic binary instrumentation で実装されてることが多いですよ、と。つまり実行時にコード埋めるって話。 DBI ってのはすげー汎用性あるんですけどイマイチ注目されてなくてよろしくない、と。 1.2 Shadow Value Tools an
正規表現の文字クラス - 兼雑記
Perl は正規表現とか " ではさまれた文字列の中にある変数とか配列を展開してくれるんですが、これは明らかに正規表現の文字クラス ([abc] とか書くヤツ) とブツかるわけです。 以下のコードは @a に 0-999 まで "x" っていう変数をつっこんでから s/$a[...]/y/; 的なことを実行して、 $_ に入ってる x を y に変えようとするコードをいくつか。 #!/usr/bin/env perl for ($i=0; $i < 999; $i++) { $a[$i] = "x"; } $_ = "x"; s/$a[12]/y/; print "12: $_\n"; $_ = "x"; s/$a[123]/y/; print "123: $_\n"; $_ = "x"; s/$a[-2]/y/; print "-2: $_\n"; $_ = "x"; s/$a[-22]
中二病と三大美徳とプロプログラマ - 2010-10-07 - 兼雑記
プログラマに取って重要な能力というか気質として、中二病というのがあるんじゃないかなーとかふと思ったのだった。 なんかちょっとしたことを達成した時に、「おおなんてこったオレすげー！！やばいオレ新世界の神だ！！！」みたいなことを思ったことがある人は結構いると思うわけです。まぁ数年、一年、一ヶ月、時には一日で実はそんなにたいしたことでもなかったことに気付いて、恥ずかしい思いをしたりするわけです。だから自分の過去の日記とか見るのは面白いわけです。 でまぁこの気質って、後で考えると恥ずかしいことだったりするんだけど、しかしこの喜びを味わった瞬間というのはなかなか快感なもんで、プログラマの人だと結構こういう経験がある人は多いんじゃないかと思います。プログラマじゃなくても研究職とかでも結構ありそうですね。 で、こういう気質が無い人って、「あっそう Hello, world! って出たね、あっそうテトリス
StringPiece というライブラリの話 - 兼雑記
例えばこう、ディレクトリの名前とその中のファイル名を / でくぎって結合する関数を書くとします。引数が std::string でも使いたいし const char* でも使いたい、ということで、たいていは void JoinFilePathStr(const string& dir, const string& base, string* out) { out->clear(); out->append(dir); out->push_back('/'); out->append(base); }なんてのを書くんじゃないかと思います。この関数で問題になるのは const char* を渡すと不要な string object が一度できることで、敬虔な C++ 屋さんだと、 void JoinFilePathStr(const string& dir, const char* base,
プログラミング言語 wake - 2010-07-09 - 兼雑記
Makefile と正規表現とパターンマッチを混ぜたような、トイ言語を作ってみました。 http://shinh.skr.jp/wake/wake.tgz Hello, world! all: "Hello, world!" wake のプログラムは Makefile のように書きます。つまり、 : で区切って左辺にターゲットを書いて、右辺にアクションを書く感じです。上記のように、 "" で修飾された文字列があると、その文字列を出力します。 Makefile のように、右辺には複数のターゲットを書けますし、文字列以外にも、他のターゲットを action として書くこともできます。 all: "Hello, " world world: "world!" 正規表現 左辺のターゲットは、正規表現で書けます。例えば、 all: hoge hige fuga .*: "yay!\n" とすれば y
2010-06-12
このプレゼンで紹介した tgmath.h の実装が素晴らしいという話なんですが、資料は口頭で説明する前提すぎて、イマイチ詳しくないので別に書いておこうかなぁと思います。これは C で型計算やってると言えると思うのでなかなかなもんなのです。 そもそも tgmath.h というヘッダが何かと言うと、 Type-generic math の略で、 C99 の PDF の 7.22 に書いてあります。ちなみにたぶん私はこの PDF を参照してます。 http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf 書いてあることは以下 4 点: tgmath.h を #include すると math.h と complex.h も #include されて type-generic なマクロを定義しまっせ sinf やら sinl みたいなのじゃ
DWARF の行情報を読む - 兼雑記
なんか行情報読むとかそいう話題が twitter にあったので、適当に作ってあったのでなんか書いてみる。 http://github.com/shinh/test/blob/master/addr2line.cc DWARF 情報つけると (今の GCC だと -g でつくと思う) アドレスからコードの名前を行番号をひけるようになるんだけど、まぁその情報をプログラムから読むという話。 まずどこに格納されてるかっていうと、 .debug_line っていうセクションに入っているので、それを探す必要がある。上のプログラムで言うと main の中。先頭にある ELF ヘッダを読んでセクションヘッダの開始位置とセクション名の格納されてる .shstrtab の位置を教えてもらって、 .shstrtab の情報を参考にして .debug_info の位置を特定する。 .debug_line の中身は
2006-11-07
記号ゴルフって英語でなんやろって聞いたら題字の返事が mark byers 氏から帰ってきました。 さて、最近の記号ゴルフについては、 http://d.hatena.ne.jp/kikx/20061030#1162308720 にまとまっていますが、とりあえず無限ループは [*""..$/] と (""..$/).min で更新できますねーと。 あとは quine も StackError も SEGV もわからないなぁといったところです。特に quine を「安直に」作る kik さんは異常だと思いました。つまり答えキボンヌと申しておるのですが。 追記なんかこれ偉そうですね。こう答えがわからないギギギというアレが。 StackError は正規表現とかなんかなぁ…あ、あと思い出したんですが 6B StackError は察しておられる通り load$0 のつもりでした。 Perl Go
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
