2010年7月24日土曜日

Rubyで遅延評価

いろんなところで既にやられているけど、自分でやってみたくなったので。
遅延評価とは、計算結果が実際に必要になるまで処理を遅延すること。

a = huge_proc()
b = large_proc()
print a

この仮想コードのhuge_procの呼び出しは、3行目のprintで出力されるまで遅延される。また、bは使われていないのでlarge_procは呼び出されない。
こういった仕組みがあれば、処理に時間がかかるが戻り値を使うかどうか分からない関数をムダに実行することがなくなるので、ある種の処理は非常に早くなる。これをRubyでやりたい。

実装

今回作ったユーティリティは、lazy{ 遅延させたい処理 }のように使い、戻り値として遅延オブジェクトを返す。
使い方は例えば、a = lazy{ x }と書けば、lazy自体はすぐに遅延オブジェクトを返し、aのメソッドが呼ばれたときに初めてxが実行される。

class Lazy
  def initialize
    @proc = Proc.new
    @obj = nil end

  def method_missing(method, *args, &block)
    if @proc
      @obj = @proc.call
      @proc = nil end
    @obj.__send__(method, *args, &block) end end

def lazy(&proc)
  Lazy.new(&proc) end

method_missingは、メソッドが無かった時に呼び出されるメソッドで、このメソッドはブロックの戻り値のオブジェクトのメソッドを呼び出す。これによって、遅延オブジェクトから実行結果のオブジェクトのメソッドを透過的に呼べる。

竹内関数によるベンチマーク

試しに、竹内関数(たらい回し関数)の遅延版と通常版と最適化版を作って、どちらも同じ引数(12,6,0)を指定して、速度の差を計測してみた。

def tak(x, y, z)
  if x <= y.to_i
    y
  else
    tak(tak(x-1, y, z), tak(y-1,z,x), tak(z-1,x,y)) end end

def ltak(x, y, z)
  lazy{
    if x <= y.to_i
      y
    else
      ltak(ltak(x-1, y, z), ltak(y-1,z,x), ltak(z-1,x,y)) end } end

def btak(x, y, z)
  if x <= y.to_i
    y
  else
    btak(btak(x-1, y, z), btak(y-1,z,x), lazy{ btak(z-1,x,y) }) end end

a = Benchmark.realtime{ tak(12,6,0).to_i } # => 9.08182191848755
b = Benchmark.realtime{ ltak(12,6,0).to_i } # => 0.00162792205810547
c = Benchmark.realtime{ btak(12,6,0).to_i } # => 0.000227928161621094
a / b # => 5578.78178090217
a / c # => 39845.1066945607
b / c # => 7.14225941422594

関数ltakは、takの内容をlazyで囲っただけで、takは素直な竹内関数の実装。btakは、takの第一引数と第二引数は必ず必要になる=遅延する必要がないので第三引数だけを遅延したバージョンだ。

通常9秒かかるこの計算が、ltakだと10ミリ秒に、btakでは2ミリ秒になり、btakはtakに比べて39845倍の速度になった。

まとめ
当然だが、遅延オブジェクトの生成にもオーバヘッドがあるので、必要以上に使うことは却って速度の低下につながるので避けたい。
また、この類のコードは汎用性が高いので、もうすこし実装を詰めてもいいかもしれない。
例えば、is_a?等、Objectクラスのメソッドが適切に動くようにすれば、関数の内部の処理を考えずに遅延オブジェクトを渡したり返したり出来るだろう。

2010年7月18日日曜日

Macのターミナルの配色が絶望的なのでなんとかした

Macで標準のターミナルを使っていると、カスタマイズができなくて困ることがある。
特に、デフォルトの色はあまりにも残念で、ディスプレイと環境光によっては青が全然見えなかったりするが、これは通常編集できない。

先日、初めてフルHDのディスプレイを購入したが、昨日から梅雨が明けて太陽が出るやいなや、ruby-modeの関数名が全く見えなくなってしまった。
そこで、TerminalColoreopardをインストールして、色を変更することに。


詳しいインストール方法や使い方はリンク先に任せるが、あとは環境に合わせて見やすい色にすればよい。

そういえば、このディスプレイを買ってから、晴れた日に部屋でコードを書いていなかった。

2010年7月7日水曜日

Twitterの規制について気づいたこと

たまにはこんな話でも。クライアントやBOTを作っていて気づいたことを幾つか。

Twitterをクライアントソフトウェアを通して使っている人は多いと思うが、一時間ごとに問い合わせられる回数が決まっており(規制)、その回数制限に悩まされている人が多い。その規制の種類や、回避策、今後の変化を総合的に考察してみたい。

ここでいう規制とは、データの取得にかかる規制のことで、投稿とは関係ない。投稿は、TL取得規制がかかってもすることができるので、実は規制されてもクライアントソフトウェアでつぶやくことはできる。

まず、規制には以下の種類がある(以下に書いた名前は正式名称ではない/括弧内は1時間あたりの回数制限)
  1. OAuth規制(175)
  2. Basic認証規制(75)
  3. IPアドレス規制(150)
  4. Streaming API(∞)
OAuth認証規制
OAuthは新しい認証方式で、コンシューマ(ふぁぼったーやTweenのようないわば2次サービス)がそのユーザのパスワードを知ること無くアクセス出来る認証方式。これを使うと、規制回数がBasic認証の10倍にあたる1500回になる。・・・のだが、最近では350に引き下げられてしまった・・・と思ったら、従量制APIが導入され、Twitterの負荷によってAPIの規制回数が変動するようになった。今は175に固定されているらしい。誰もが予想したとおりの展開だった。

Basic認証規制
HTTPのBasic認証を使った認証方式。単純で実装が用意だったが、パスワードをコンシューマに教える必要があり、危険だったのでOAuthに取って変わられる。150回の制限だったが、今は75回になったらしい。もともと、6月いっぱいで終了する予定だったので、今となっては殆ど誰も使っていないのではないだろうか。

IPアドレス規制
意外と知らない人が多い制限その1。
実は、Twitterには、つぶやき検索や公開リスト、つぶやきIDを指定してつぶやきを取得など、ログインせずに見ることが出来る情報が結構ある。ログインせずに見ることが出来るのだから、OAuthやBasicの回数制限とは関係ない。
しかし、コンピュータに割り当てられる※本当は違うけど勘弁IPアドレス毎に、毎時間150回までと、ここでも規制がかかっている。OAuthやBasicとは当然別にカウントされているので、クライアントを作るときは可能ならこちらを使うようにしたほうがユーザには親切ということだ。

Streaming API
知られていないその2。
Streaming APIは、定期的にツイッターに問い合わせるのではなく、ずっとつなぎっぱなしにしておき、新しいつぶやきがあれば順次向こうから送ってくるというもの。その性質上、回数制限はない。Basic認証で認証されるため、パスワードが必要。このAPIに対応しているクライアントはあまりないし、時々取りこぼしがあるようだが、一切規制の心配がないし、つぶやきが投稿されたら数秒でそれが取得できる。

で、
Streaming APIは置いておくとして(クライアントの対応次第なので)、実はIP回数制限を、通常のタイムライン取得に使うことが出来る。
公開リストは、取得するためにログインする必要がない。つまりIPアドレス規制の範囲で取得することができる。
ということは、フォローしている人全員が入ったリストを作っておけば、OAuthやBasic認証が規制されてもクライアントソフトウェアから見ることが出来る(IPアドレス問い合わせに対応していない、リストに対応していない場合は不可能だが)。
また、似たような方法でリプライも取得することが出来る。検索もIP問い合わせで取得できるので、「@ユーザ名」で検索をかければ、自分のリプライがすべて見られる(なお、この方法を使えば、誰に対するリプライでも見ることが出来る。自分宛以外でも)。
問い合わせ方法を上手に使い分ければ、規制に悩まされることも減るのではないだろうか。

クライアントソフトウェアの対応
現在はまだテスト中らしいが、chirp user streamを使えば、規制の影響を受けずに、わずか数秒のタイムラグでつぶやきを受け取ることが出来る。しかも、フォローされたとき、誰かが自分のつぶやきをお気に入りにいれたとき(ふぁぼられた時)にも、数秒でわかる。これは今後どうなるかわからないが、Twitter使い方が大きく変わるだろうし、規制を過去の遺物にならしめることだろう。
しかし、これが一般に利用されるようになったとしたら、Twitterのサーバは大丈夫なのだろうか。少し心配だ。