射撃しつつ前転 RSSフィード

2012-05-22

rubyでpythonのdefaultdictっぽいものを実現する

 Pythonのハッシュテーブル(Pythonではdictと言いますね)には、初期値が設定できる亜種としてdefaultdictというものがある。Rubyの場合、Hashクラスには初期値が設定できるが、初期値としては整数文字列シンボルぐらいしか使えない。初期値として配列とかハッシュテーブルを使えないのである

 そこで、Pythonのdefaultdictっぽいものを作ってみた。以下にコードを示す。

class DefaultHash < Hash
  def initialize(init)
    @init = init
  end

  def [](k)
    v = super k
    if v
      v
    else
      self[k] = @init.clone
    end
  end
end

a = [1,2,3,4,5,4,3]
h = DefaultHash.new(Array.new)
a.each{|k|
  h[k].push 1
}

p hash

 DefaultHash.newの部分をHash.newに変えると、嬉しい場合があまり思いつかない感じの挙動になっていることがわかると思う。

 作ってみたもなにも、[]メソッドを上書きしただけであるし、nilやfalseを値として使った時のことを全く考えていないのだが、とりあえず動くので満足している。

 このコードを書いた動機は、以下のようなコードを書きたくない、というものである。

if h.has_key? k
   h[k].push 1
else
   h[k] = [1]
end

 この例ぐらいなら場合分けを書いてもいいんだけど、ちょっと複雑な数え上げがしたくなるとハッシュがネストしたりすることがよくあって、そうなると場合分けの中に場合分けを書くことになって、やりたいことの割にコードが長いというか大仰になってしまってなんだか悲しい、ということがよくあるのだ。

 デフォルトのHashでもHash.new(0)みたいに初期値を設定できるのだけど、前述の通り、Array.newみたいなのを引数に渡すとうまくいかないのである。これは同じオブジェクトを使う(ここでの同じ、という言葉メモリアドレスが同じという意味だと考えてもらいたい。値が同じ、とかではなく、同じ物を指しているのである)のが原因である。

 なぜデフォルトの挙動では初期値として同じオブジェクトを使っているのかというと、が呼ばれる度に新しいオブジェクトを作っていたのでは、存在しないキーに対してを呼ぶ度に新しいオブジェクトを作ることになるからだ。これでは、場合によってはリークに近い挙動を示すことになってしまう。という訳で、Hashクラスでは初期値(デフォルトオブジェクトと言い換えたほうがわかりやすいかな)は共有されるのである。

 valueが初期値であるようなkeyGCみたいな感じで定期的にdeleteすればいいのかなーと思うが、面倒なのでそこまでは実装してない。10000回ぐらい[]が呼ばれたらスイープする、みたいな実装だったらパフォーマンス的にも我慢できるぐらいになるんではなかろうかと思うんだけど。

2012-05-17

なぜNetflixはNetflix Prizeで優勝したアルゴリズムを実用化していないのか?

ダヌシカさんのツイート経由で、以下のURLから

 超簡単に要約しておく。詳しく知りたい人は上記のリンク先を読んで下さい。

  • Netflix Prizeの優勝アルゴリズムでは多くのアルゴリズムが混合されていた。そのうちSVDとRBMは今でも使ってる。
    • 100万件のデータに使えるものであっても、1億件で利用可能なようにスケールさせるのは大変だった。
    • スケールさせるのが大変なので、Grand Prizeで用いられた数百のアルゴリズムの混合は、Netflixでは使ってない。
  • Netflix Prizeの成果を使ってない理由としては、技術進化によってビジネススタイルが変換したため、という点もある。

 後半は力尽きてほとんど読んでないが、どんな軸でどんなオススメをするかとか、多様性カバー率)が重要だよ、みたいな話が書いてあるような気がする。

 Netflix Tech Blogは他にもIntroducing Exhibitor - A Supervisor System for Apache ZooKeeperとか、面白げな記事が散見されるのでチェックしておくと良さそう。

2012-05-06

最近のX.orgにおける2Dアクセラレーションの改善について

 ゴールデンウィークなのでちょっと息抜きを。

 Intelドライバは最近はSNAという新しいアーキテクチャを実装していて、まだデフォルトでは有効になっていないのだが、だいぶ高速なようだ。

 この他、Glamorというのが出てきた。これはOpenGLを使ってX Winddow Systemのアクセラレーションを行うライブラリである。各種ドライバの内部で使われることを意図しているそうだ。Gallium3DのX.org state trackerとやってることは近い。Galliumの場合はOpenGLではなくGallium用の中間形式に変換するところ、アクセラレーション対象が広い(GalliumはXのアクセラレーションだけじゃなく、OpenGLとかOpenCLとかも扱う)ところがGlamorとの違いになる。SNAと比べるとまだ遅いみたいだけど、今後どうなるかちょっと期待している。ただ、OpenGLをまともにアクセラレートしてくれるドライバが少ないわけで、そこんところがちょっと微妙かなぁ。

 Cairo自体も1.12でかなり高速化されているのだが、これは一部のドライバのバグを踏むということで、まだ各ディストリビューションには導入されていない。

 こちらの記事では最近のドライバについていくつか実験をして、簡単な2Dアクセラレーション(単なるアルファブレンディングとか)であればCPUを使った方がGPUを使うより速い、なぜならGPUにデータ転送するのは結構時間がかかるから、という結論に達している。Cairoみたいな描画モデルだと描画関数それぞれに対してまともにGPUにデータ転送しちゃうので遅くなりやすいよね、シーングラフみたいに描画命令列を一旦メモリ上に保持して後で効率良く実行できるといいのかもね、ともある。

 最近のマルチコアCPUだと、2DアクセラレーションぐらいならCPUにやらせた方がいいのかもね、というのはその通りかもしれないが、なんのためにGPUがついてるのかわからなくなるなぁ…。

2012-03-06

古くて新しいエディタ、Emacs

 技術評論社さんからEmacs実践入門献本いただきました。たぶん数日前に届いてたんだけど、しばらく郵便受け見てなかった…。表紙

 私が書いた日本語入力を支える技術と同じWEB+DB PRESS plusシリーズということで献本頂いたのだと思いますが、レビューしとけよという無言のアレを感じる気もするので、時宜を外さないうちにレビューを書いておきます。

 本書に寄せてって何それ羨ましい!自分も書いてもらえば良かった! というのが最初に出てくる感想なわけですが、それはさておき。

 Emacs実践入門は入門の名の通り、Emacsの使い方を説明する本です。基本的なキーバインドから便利なツールまで一通り説明している感じです。EmacsといえばEmacs Lispでガシガシと自分なりに拡張していけるところがメリットであり、同時にそれは初心者からすると何それ怖いと思わされる点でもあるわけですが、自分でelispを書くようなハードな話は出てこないので、初心者でも問題なく最後まで読み通せると思います。

 私はEmacsが最強のエディタだと思っているわけでは特に無いのですが、私にとっては手放せないエディタであることは事実です。仕事プログラムを書くときにはEmacsを使いますし、本を書いているときにもEmacsを使っていました。そんな私にとって、Emacsについての新しい書籍が出るというのはうれしい話です。まだEmacsを使っていていいんだ、と認められた気分です。

 Emacsは初心者にとってやさしいエディタではないのですが、便利なコマンド10個か20個ぐらい覚えると急に便利になってきて、「まぁこれでいいか…」という気分になってきます。そしてそのうちmigemoみたいに便利なelispに出会い、「なんかいつのまにかEmacsが便利な体になってしまった…」という気分になってくる。私にとってはそういう位置づけにいるエディタです。

 この本が3月に出たというのは意図があって、きっと4月新入社員が世にあふれて、研修でEmacsとかいうのを使わされるんだけど不便で敵わん、と思ってるような人を取り込もう、というような目論見があるのだと思います。実際、この本を読むべき人はそういう人でしょう。Emacs使って10年という人が読んではいけないわけではない(実際、10年使ってる人は却って最近のパッケージシステムの話とかは知らなかったりしそうです)ですが、どちらかというと今Emacsに不便を感じていて、でも便利に使いたい人がパッと買って便利な使い方を覚える、そういう読み方が似合う本のように思います。エディタの効率は開発の効率に直結しているので、これからEmacsを覚えるつもりならば、買ってもすぐに元は取れるでしょう。

 おまけ。この本に載ってなかった機能やelispでおすすめしておきたいのはmigemoとiswitchb-modeとdmacroぐらいでしょうか。こちらも便利ですので、興味があったら検索して調べてみて下さい。

2012-02-08

日本語入力を支える技術、本日発売

f:id:tkng:20120208014636j:image:w240:right 発売ですよ、というだけではアレなので、日本語入力と私、という題目自分語りでもしてみようかと思っていました…が、時間もないのでそれはまた今度にして、細かなトピック選択について少し触れてみようかと思います。(写真は昨日既に入荷していたジュンク堂池袋店です。右上に見えるプログラミングコンテストチャレンジブックもオススメ!)

 データ構造については、カッコウハッシュダブル配列、LOUDSを選択しました。カッコウハッシュはやや唐突な感じがしますが、本当はfujimapまで紹介してfalse positiveを許すとサイズが小さくできるねー、とかやりたかったのです。fujimapをボツにしてしまったので、結果としてカッコウハッシュはちょっと浮いてしまったかなと思います。ただ、面白いデータ構造なので知っといて損はないでしょう。ダブル配列、LOUDSあたりは選択としては特に異論もないところかと思います。しかし、LOUDSは平易に説明しようとするとものすごく大変で、かなり苦戦しました。うまく説明できたかわかりませんが、とりあえず現時点でのベストは尽くしました。

 学習系に関しては、当初は確率言語モデル→構造化SVM→CRFの順に説明を書いていたのですが、確率の説明がやっかいなことから、構造化SVM→CRF→確率的言語モデルの順番に変更しました。つまり、確率が出てくるのはできるだけ後回しにしたかったし、確率が出てきたとしてもベイズ定理とか使うのは後ろの方にしたかったのです。構造化SVMは前向き後ろ向きアルゴリズムが要らないし、オーバーフローとかアンダーフローとかあんま気にしなくても動くし、良い手法だと思っています。確率値が出せないけどね。最適化にFOBOSを使ったのは、目的関数があって劣微分定義できたら使えるので汎用性が高い点、実装が簡単である点を評価しました。他にも条件を満たす手法はきっとあるとは思いますが、要件は十分に満たせているので今回は(自分の中で)定評があるFOBOSを使いました。

 その他、隠れマルコフモデルについてはスライスサンプリングパラメーター推定を行う説明とか書いていたのですが、これ書いてたら発売が半年伸びるなと思って途中でボツにしました。

 とにかく、学生時代の自分が知りたかったことを今の能力で出来る限り噛み砕きつつ詰め込んだので、誰に読ませたいかというと、一番読ませたいのは過去の自分です。タイムマシンがあったら、一冊過去に送りたい。

 あとでレビュアの方々が書いてくれた記事にリンクを張ります。今日はもう寝ますのでおやすみなさい。

2005 | 04 | 05 | 06 |
2006 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 05 | 06 | 11 |
2013 | 01 | 05 |
Connection: close