Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2016-02-09

[] Writing Qlock

うわーすごいなーと思ったので、パクリ インスパイアされてみました。Ruby プログラムで書き時計。

                         eval(T=%(eval(%(E=27.chr;Z=32.chr;$
                    ><<E+"[2J";K=->q{(q-q*(1-3844.0/q.abs2)**0.5)
                /2};I=->f,a,b,z,t=p{(a-b).abs>(f<1?1:1-(K[a]-c=K[b]).
             abs)?I[f,c=                                     (a+b)/2,b,I
           [f,a,c,z,t],t  :''''''''''''''''''''''''''''''':  ]:f<1?(x,y=b.
         rect;d="'."[y%2  :                               :  ];c=z[y/2+5];c[
       x+=58]=t||(c[x]==  :                               :  d||Z==c[x]?d:?:))
     :(puts(E+"[H"+$/+I[  :                               :  0,c,0,I[0,b,c,z.map
    (&:b)]]*$/);t||I[0,b  :         Writing Qlock         :  ,c,z,Z];sleep(0.01))
    ;z};s=(Z*25+"eval(T=  :                               :  %("+T+"))").lines.ma
   p{|l|l.chomp.ljust(90  :     (C) Yusuke Endoh 2016     :  )};loop{z=0i-31,[-1.0
   ,Z];h=10i-30;a="5?GUV  :                               :  XIIPCM.AAN&,HY/ZZZO7[
   &,HY3'CE<5SM5.OOJ+BBT  :                               :  3LV+A&YQ.STT[MF.KUVXP
   K+&[AOOJ'&5?GU57-B5SI  :                               :  51>E<5PCMF.K,DXPD+SM7
   .77'";i=92;"Q+3_.DW'`  :          inspired by          :  HAD,A11R`NK+HILJ/D'&F
    1.CG371|BE@355?5A7@@  :                               :  ??7|3-5-".scan(/../)
    {a.gsub!("%c"%i-=1,$  :    https://t.co/NSBi45Lj77    :  &)};Time.now.strftim
     e("%H:%M").bytes{|c  :                               :  |q=h;a.split(?&)[c-
       48].scan(/([0-8])  :                               :  |./){$1?q+=(n=$1.
         hex)%3-1+(n/3-1  :                               :  )*2i:z<<[q,$&]}
           ;h+=6};z<<a=3  :...............................:  1i-31;31.time
             s{|y|s[y/2+                                     5][58]=Z};g
                =z.map{|b,h|x,y=a.rect;g&&s[y/2+5][x+58]=g;I[1,a,b,s,
                    g];a,g=b,h};sleep(61-Time.now.sec);;;}).gsub(
                         /^(.{26}):.{32}/){$1}.split*"")##))

動画。

D

追記:動画は 5 の文字の書き順が間違ってた……。上のバージョンは修正済み。

2015-12-14

[] 『API デザインケーススタディ』の紹介

著者の田中哲さん (@tanaka_akr) から献本をいただきました! *1

本(電子版)をもらったのは RubyKaigi の前日の夜。翌日に TRICK 2015 の発表を控えていましたが、読み始めると面白すぎて、発表前までに読み終えてました。ちなみに献本とは別にジュンク堂 RubyKaigi 店で一冊買いました。(サインもろた)

自分が思った、読者層ごとの勝手な紹介を書いてみます。

普通の Ruby ユーザへの紹介

プロセスを起動する Process#system 、#spawn 、open3.rb *2 あたりを使ったことがあるでしょうか? C の system 関数は使えない子として有名ですが、Ruby の Process#system たちはプロセス起動に関して「こんなことできたらいいな」と思うことが、たいていできます。しかも、簡単・ポータブルに。たとえばこの辺りの設計をしたのが、著者の akr さんです。

この本では、RubyI/Oプロセス、時刻など、いろんな API 設計事例がオムニバス方式で説明されています。あくまでケーススタディの本なので、API 設計のやり方を体系的に手取り足取り教えてくれるわけではありませんが、節ごとに教訓が短くまとめられているので、Rubyライブラリとか作るときに重要な示唆を得られるはず。汎用性の高そうな教訓の例をいくつか引用しておきます。

  • 「使いやすいというのは、実際に使う状況での使いやすさが重要ですから、実際に使う状況を調べることが重要です」(1.05節 0バイト読んだときに何を返す? - 用例を探して良い挙動を判断する)
  • プログラマが間違った方法を使ってしまうのを避け、正しい方法に誘導しています。」(2.03節 Socket.ip_address_list - 自ホストのIPアドレスを正しく簡単に得る)
  • プログラマの既に持っている知識を利用して学習しやすいものとするのが狙いです。」(5.04節 Integer#bit_lengthメソッド - 用途と前例を調べる)

他には、使いやすいライブラリ API デザイン(akr さんの RubyKaigi 2006 の発表) を読んで感銘を受けたら、読んで損はないと思います。

特に、Ruby に機能提案をしたいとか考えてる人は読むといいですよ。あわせて読みたいmatz を説得する方法(akr さんの RubyKaigi 2008 の発表)

また、「I/O」「ソケット」「プロセス」など、UNIX システムプログラミング寄りの内容が多めです。Ruby でそういうことをやりたい人にはとても参考になると思います。必読と言ってもいいかも?

歴戦の Ruby ユーザへの紹介

Ruby をよく使っている人なら何となく感じてると思うんですが、Ruby の組み込みクラスって玉石混淆なんですよね。なんというか、設計・実装の熟考度にムラがある *3 。その中で、ふと何か感心することのある部分は、たいてい akr さんが背後にいます。

そういう部分がどれほどの熟慮を重ねて設計されてきたか、この本を読めば分かります。それも、背景知識の説明を含めて、極めて理路整然とわかりやすく説明してくれます。Ruby マニアにとってこんな貴重な本はないです。

Ruby 以外のプログラミング言語ユーザへの紹介

Ruby を題材として API 設計のケーススタディを紹介する本なので、Ruby を知らない人にも読みやすいとは言いにくいですが、しかし他に類書ってあるんですかね *4 。言語やライブラリAPI 設計について考えてみたい人は読むといいんじゃないでしょうか。ついでに Ruby を使ってみたくなるかもしれません。

追記:akr さんが『APIデザインの極意 Java/NetBeansアーキテクト探究ノート』という類書を教えてくれました。こちらは互換性最優先という感じだそうです。

Ruby 以外のプログラミング言語の開発に携わっている人への紹介

あなたの言語の I/O 周り、プロセス周り、時刻周りについて、設計不備や機能不足を知ることができます。いや実際のところ、プログラミング言語のいわゆる泥臭い部分の API 設計についていろいろ書いてあるので、重宝するはず。

実用的なプログラミング言語を作りたいと思っている人への紹介

それがどれだけ遠い道のりなのかを痛感させてくれます。評価器とか GC とかだけでは実用的なプログラミング言語は作れないのです……。

プログラマではない人への紹介

世界各国の変態サマータイムについて豆知識が得られます。

Ruby 開発者への紹介

え、まだ読んでないの?

*1:自分と akr さんとは Ruby コミッタつながりです。

*2:1.8 のころの open3.rb を知っている人はネガティブな印象を持っているかもしれませんが、Ruby 1.9 で akr さんが大改修して現在は安心・安全の akr プロダクトになってます。詳しくは 3 章に書いてある。

*3:たとえば、カバレッジ API とかひどいですよね。カバレッジ測定を細かく制御できないとか、パスカバレッジへの拡張性を全く考えてないとか。

*4:強いて言えば C 言語の rationale とか?

2015-12-13

[] RubyKaigi 2015 終了

2 年ぶりの RubyKaigi 参加でした。相変わらず楽しいですね。

自分たちが審査員やらせてもらった TRICK 2015 の発表については前の記事に書いたとおりですが、ひとつ重要なことを書き忘れてました。参考文献ですね。ああいうプログラミングをもっと見たいなーと思った人は、入門編として拙著を是非読んでみてください。

あなたの知らない超絶技巧プログラミングの世界
遠藤 侑介
技術評論社
売り上げランキング: 3,000

ジュンク堂 RubyKaigi 店ではサイン会をやらせて頂いて、完売できたということでホッとしました。買ってくれたみなさん、本当にありがとうございました。なお、書籍自体はもちろんまだまだ絶賛発売中なので、まだ買ってない人ももう一冊くらい欲しい人も買ってください。どっかで会えた時にはサインくらいしますので!

会議自体は虫食い的な参加だったので、個別の感想とかはやめときます。全体通して思ったのは、謝辞付きの発表が増えたなあ、ということでした。スポンサーが増えたということで、すばらしいことですね。

超久々に懇親会出れたのはよかったなあ。いろんな人に会えた。家族の人に感謝。

ということで、スタッフのみなさんもそれ以外のみなさんもありがとうございました。来年は京都ということで、TRICK の開催が危ぶまれます(笑) あれか、ぼくらも賞金(と審査員の出張滞在費)のスポンサーを募集すべきなのか。

2015-12-11

[] TRICK 2015 結果発表

RubyKaigi 2015 で発表させていただきました。

入賞作品はこちら。

https://github.com/tric/trick2015

発表資料はこちら。

http://www.slideshare.net/mametter/trick2015-results

たくさんの投稿ありがとうございました!今回の入賞作は、発表会場でパッと見てうおおお!って言うのよりは、じっくり解析することでジワジワとスゲースゲーってなるのがたくさん入賞したので、ぜひ解析してみてください。

前回と比べて 2 倍程度の投稿があり、どれも面白いものばかりだったので、全部選べないのがとても残念でした。

他の審査員の方々もありがとうございました(ココ見てるかわかりませんが)。あと、投稿受け付けの事務局的なことからスライドのデザインまで、@hirekoke さんがやってくれました。感謝。


随時追記:観測した参加者の方々の声。後で見直すとき用のメモ。

[] TRICK 2015 落選作供養:そろばん時計

TRICK 2015 に投稿して落選したぼくのプログラムはこちら。

            $><<"\e[2J";z=
          32.chr;loop{s=(0..
        8).map{|i|[i>7??+:?|]*
      2*((i>7??-:i==2??=:z)*22)}
    j=1;Time.now.strftime("%H%M%S"
  ).bytes{|c|3.upto(9){|i|s[i%8][j+-
    j[2],3]=(i<8?c%5!=i%5:c<53!=i>
      8)?"<_>":z+?|+z};j+=4};s!=
        $s&&puts("\e[H"+s[8],*
          $s=s)}-_#TRICK2015
            #_Yusuke_Endoh

そろばんの玉のイメージです。実行すると、そろばんで時刻を教えてくれます。

+----------------------+
|<_><_>  <_> |   <_> | |
| |  |    | <_>   | <_>|
|======================|
|<_><_>  <_><_>  <_> | |
|<_> |   <_><_>   | <_>|
| | <_>   | <_>  <_><_>|
|<_><_>  <_><_>  <_><_>|
|<_><_>  <_> |   <_><_>|
+----------------------+

21:29:15 ですね。

落選理由は、正直ネタもイマイチなんですが、一番下に名前が書いてあること。ガイドラインに「自分の名前を入れんな」と書いたのに、自ら破ってしまいました。いや、なんで書いたのか全然思い出せない。

しかしまあ、名前書いてなかったとしても今回の入賞作と比べたら見劣りしますね。次回は全力を出して kinaba の 3 連覇を止めるようにがんばります。

2015-12-10

[] ハッシュは頻繁に参照する値を最後に入れると高速

明日から RubyKaigi なので、ちょっとした小ネタを一つ。

例えば、0 から 9999 までをハッシュに順に入れます。

h = {}
10000.times do |n|
  h[n] = true
end

このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。

どのくらい高速かというと、

1_000_000_000.times { h }       # 40.8 sec (ループ自体の速度)
1_000_000_000.times { h[9999] } # 57.2 sec
1_000_000_000.times { h[0] }    # 89.1 sec

h[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1


なぜこんなことが起きるのか

ハッシュの実装に起因します。Rubyハッシュは closed hashing とか separate chaining とかいうやつで、同じビンに入れることになった要素をリンクリストでつないで格納します。(Wikipedia の図解

後から入れた要素は、リストの最後に連結するのではなく、先頭に割り込ませます。つまり、最近入れた要素はリストの最初の方に来ることになります。参照の際はリストを前からたどるので、最近入れた要素ほど早く発見される。

このリンクリストは放っておくとドンドン長くなるので、ある程度長くなったら rehash します。Ruby の場合、要素の数がビンの大きさに対して 5 倍を超えたときに rehash をします。例えばビンの大きさが 2048 のとき、要素数が 10240 を超えると rehash します。

冒頭の例は要素数 10000 で、ぎりぎり rehash していない状態です *2 。そういうハッシュにおいては、リンクリストの長さの平均は 5 なので、最初に入れた 0 を発見するには、期待値としてリンクリストを 2.5 回程度たどることになります(最近挿入された要素が先頭にある可能性が高いので、実際にはもう少し多くなる)。一方、最後に入れた 9999 はほぼ確実にリンクリストの先頭にあるので、リンクリストをたどる回数は 1 です。この差が現れていると思われます。

「5 倍という閾値が高すぎる」という話はたまに聞きます。かといって安易に閾値を下げると、頻繁に rehash が起きることのオーバーヘッドやメモリの無駄遣いが起きます。ユースケースごとに最適な閾値は変わるでしょう。評価が難しい。


応用:case 文の高速化

追記:この節に書いてあることはさっそく古くなりました。この記事を受けて、内部的なハッシュを rehash するようになったようです。

Ruby の case 文は when 節を上から順にマッチするか調べていきますが、when 節が全部リテラルの場合、内部的にハッシュを作ってジャンプテーブルみたいに実行するよう最適化されます。ここにもハッシュがあるので、同じ問題が起きます。*3

例えば、以下のようなコードを考えます。

100000000.times do
  case 0
  when 0
    do_something
  when 1, 2, 3, ..., 10000
    raise
  end
end

省略してますが、実際には全部の数字を書き下しています。*4

残念ながらこのコードは遅いです。以下のように書き換えましょう。

100000000.times do
  case 0
  when 1, 2, 3, ..., 10000
    raise
  when 0
    do_something
  end
end

when 節の順番を入れ替えただけです。こうすることで、0 が最後にハッシュに格納されます。参照するのは 0 ばかりなので、高速です。測ってみると、case の処理だけ見れば 2 倍程度早かったです。まあ、Integer#times の方が遅いですが。

何かのバイトコードインタプリタみたいなのを作るとき、こういう巨大な case 文を書きたくなり、しかも実行速度が大切です *5 。そういう状況において、頻繁に実行される when 節を後ろの方に持っていく、という工夫が考えられます。

case 文の最適化を考えなければ、頻繁に実行される when 節は上の方に置いた方が効率的なので、そう思って上に置いてる人は逆に損してることになりますね。皮肉なものです。


本当に言いたかったこと

Ruby でこういう小手先の高速化とか考えるのは不毛だからやめた方がいいと思います。よかれと思ってやったことが、いつの間にか逆効果になってたり、ひどいと動かなくなったりします。(関連)

ここに書いたことも、いつ傾向が逆になってもおかしくないです。Ruby ではアルゴリズムレベルの高速化だけに集中すべき。それでどうしてもしょうがない場合には、普通に他の速い言語に移行すべきだと思います。でも、アルゴリズムレベルの最適化の余地って思ったより残ってるものですよ。

なお、不毛を不毛とわかった上で楽しんでやるのはアリかもしれない。

*1ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-linux] で確認してます。trunk は Fixnum#hash にバグが入ってたので避けた。

*2:この問題は要素数 10000 限定というわけではないです。160 、320 、640 、……をちょっと下回るあたりでも、程度の差はあるかもですが再現するはず。

*3:この問題に気付いたのは、これがきっかけでした。

*4:Range を使って when 1..10000 と書いたら、そもそも最適化がされなくなるのでダメです。

*5:そういうプログラムRuby で書くのアホじゃね?という指摘は妥当。