d.y.d.

13:54 09/12/31

年末まとめ

今年何をやったことや読んだものを振り返ろうと思います。

恒例のゲーム報告から行くと、万歩と深遠HA クリアしました！その後他のダンジョンには潜ってないけど、何かまたそろそろ始めようかな…。　／　プログラミング関係は、ハッカソン的なもので何個か小ネタを仕上げただけで、ちゃんとしたものは作ってないですね。困った困った…。どっちかというと、勉強会的なイベントで発表するネタを考える方が多かった。特にFLTV での "真・自然言語プログラミング" の発表内容は割と個人的に会心の出来なのですが、多くの方に好評いただけたので嬉しいです。なんだかもう、しばらくの間は、私はそういうキャラということでいいのではないかと思い始めてきました。ものを作ることに全力をかけている人は多いけれど、「一見難しく見えることをいかに簡単に噛み砕いて見せるか」を極めることに全力をかけている人は、世界にある知識の量と比べて、余りにも少なく感じる。そういうものに私はなりたい。

読んだ本では…今年出版された本というわけでなく、あくまで、私が今年読んだ本の中でですが、『チョコレートコスモス』が一番でした。直接の言葉にはならないもの、ここでは「迫真の演技」、の迫力を言葉の波と勢いで伝えることにかけては恩田陸は天才だと思うのですが、その迫力が中盤から一切途切れず最後まで続いていて、心臓が止まるかと思った。本当に言葉の力というものを感じます。さらに驚いたのは、これだけの作品の書評をどれだけ探してもオマージュ先の『ガラスの仮面』を「越えた」という言及を一つも見かけない。今まで読んだことなかった元ネタはどれだけ凄いんだ、と思って読んでみたらそちらも強力でした。いやーもうヤバい。他に今年読んで好きだった本は『竜の挑戦』、『エバーグリーン』、『リピート』、『絞首人の一ダース』、ですね。竜の挑戦はシリーズ８作目なので気軽にお勧めするのはちょっと難しいですが、ここに出てくるアイヴァスという AI がとても格好良いといいますか、自分が作るならこう作りたい的な。こういう感覚に共感を覚えるので、そんなものをサクッと越えたところにいる AI の描写を見ると燃えてきます。エバーグリーンは、全く知らない作家さんの本を読んでみよう！と思って図書館で適当に手に取ったら大当たりでした。同じ豊島ミホの『ブルースノウ・ワルツ』なんかでもそうだったんですけど、小さかった頃の自分が熱い一心を持っていたことは痛いほどに覚えている、覚えているけれどその心自体はもう取り戻せない、っていうテーマが胸に来る。リピートと、絞首人の一ダースの中でも "優しい修道士" は、私の中ではこういうのこそがロジックだ、というお手本のようなイメージ。面白かった。

読んだ論文/研究でインパクトがあったのは…これも2009年のものというわけではなく、単に私が知ったのが今年だった、という基準ですが、形式言語──の理論にとどまらずに具体的なアルゴリズムにまで群論を持ち出してくる系のがかっこいいなー、というのを何度か感じました。行列乗算すなわち CFG の構文解析が O(n^2) で可能か？という問題をある種の群の存在に帰着する "Group-Theoretic Algorithms for Matrix Multiplication" （解説記事）や、モノイドの元の列を和が単位元になる範囲でまとめていくツリーの高さが列の長さに依存せず押さえられるという Factorization Forest というのを使って正規表現検索用のインデックスを張る話や、オートマトンの遷移関数をorではなくxorで組むことで線形代数の話に持ち込む "Compact Normal Form for Regular Languages as Xor Automata" や。勉強しなくては。

というわけで、みなさま、良いお年を。来年もよろしくお願いします。

10:44 09/12/15

slist LRUMap

shinhさんにもらった宿題ですが、やっぱりシングルリンクで十分ですね。

// ハッシュ値の衝突や再ハッシュは考えてない

function LRUSet() {
   var table  = Array(HASH_SIZE) // ハッシュ表
   var size   = 0      // 今入ってる要素数
   var oldest = {}     // slist の先頭
   var newest = oldest // slist の末尾

   return {
      get: function(e) { return table[ HASH_FUN(e) ].next.value },
      has: function(e) { return !!table[ HASH_FUN(e) ] },
      add: function(e) {
         var h    = MY_HASH_FUN(e)
         var node = table[h]
         if( node ) { // すでに入ってるヤツだったら
            if( node.next === newest ) // 最新ならなにもしない
               return
            var move = node.next // そうでなければ動かす
            table[ MY_HASH_FUN(node.next.next.value) ] = node
            node.next = node.next.next // moveノードをスキップ
            setNewest( h, move ) // newestに置く
         } else { // まだ入ってないヤツは
            setNewest( h, {value: e} ) // newestに置く
            size += 1
            checkSize() // 指定したサイズを超えてたらoldestを消す
         }
      }
   }

   function checkSize() {
      while( SIZE_LIMIT < size ) {
         table[ HASH_FUN(oldest.next.value) ] = undefined
         oldest = oldest.next
         size  -= 1
      }
   }

   function setNewest(h, node) {
      newest.next = node
      table[h]    = newest
      newest      = node
   }
}

シングルリンクのリストの上のイテレータは「一個前」を指すと便利という定番イディオムで、ちゃんと問題なく管理できるみたい。

add(1); add(2); add(3)
==>
 hash(1)        hash(2)       hash(3)
  ↓            ↓            ↓
  [_: next─]→ [1: next─]→ [2: next─]→ [3: next─]→ null
  ↑                                        ↑
 oldest                                    newest

こんなイメージ。

※追記：ハッシュに入れるのを value と next のある構造体へのポインタじゃなくて value と next のある構造体そのもの、にしようと思うとこれではまだダメだなあ。何か上手い手あるかな。

20:08 09/12/13

Boost.勉強会

ちょっとソウルに来てます。寒い。
…という都合で途中退出せざるを得なかったのですが、昨日は Boost.勉強会行ってきました。

とにかく Cryolite さんの shared_ptr についての発表が素敵でした。

　　　　　　　　　　　　　　　　　　　　　　 ヘ(^o^)ヘ いいぜ
　　　　　　　　　　　　　　　　　　　　　　　　　|∧ 　
　　　　　　　　　　　　　　　　　　　　　／　　/
　　　　　　　　　　　　　　　　 (^o^)／ てめえが「参照カウントでメモリ管理してるだけでしょ？」って
　　　　　　　　　　　　　　　 ／( 　)　　　 それだけだと思うなら
　　　　　　　(^o^) 三　　／　／ ＞
　＼　　　　 (＼＼ 三
　(／o^)　　＜　＼ 三　
　( ／
　／ く 　まずはそのふざけた
　　　　　　　幻想をぶち殺す

と @melponn さんがおっしゃってましたが、まさにそんな気分になりました。こう、ライブラリの設計思想から掘り起こして魅せられる解説はすごいなあ。 shared_ptr についてはもちろん、Boostに限らず他のライブラリに関しても、ここまでのものはなかなかない気がします。見てない人はみんな見るべし。

自分の

自分は "Boost.MultiIntrusivedex" というタイトルで発表してきました → [pptx] [pdf] [github] [ustream]。 pptx には色々フォロー入れてあるので見られる人はpptx版がおすすめです。 github のソースは本当最強に怪しいのでそのうち改善します。

会場やその他の場所で見かけた質問/疑問等々のフォロー。

get<2> のようなマジックナンバーの代わりに、 "タグ" を指定しておくと get<twitter_id_index> みたいに自由に名前をつけてインデックスを取り出せます。参照: アキラさんの記事。
modify_rollback_ は、各インデックスに対して「このノードの値勝手にmodifyしちゃったけど、無理だったらrollbackするから教えてね / 無理じゃなかったら自分のリンクをつなぎ替えといて」って時に呼ばれるものなので、インデックス側が高度なロールバック処理を実装する必要はないです。既存のインデックスの実装では、やってることは実質的に insert_ と同じでした。
と思ったんですけど、Boost.Intrusive のフックを流用する方法だと、これが難しかった。まだ未解決。「このノードの値勝手にmodifyしちゃったけど」を勝手にやられると一時的に二分木の構造を壊されるので、壊れてることを前提に処理ができないといけないんですが、 Intrusive はそういうことを想定した作りになっていないので。どうしたもんかな。
listやtreeを表現できるのは当たり前なんですが、ノード形式のコンテナで random_access を実現するのは、ちょっと面白い工夫が必要です。インデックスに node_type* の配列を持っておく → node_type はメンバとして node_type** up を持つ。up は自分が入っている配列エントリのアドレス（になるように、全部の操作をちゃんと気をつける）。という構成です。pptx に図があります。
↑これのおかげで、途中に要素を挿入してもイテレータが無効化されないランダムアクセスコンテナ、ができあがるので、これもなかなか面白い特徴ですね。
「これあれば他のコンテナ全部要らないんじゃ？」というのは微妙なところで、 set や multiset の上位互換にはなると思うんですが、基本的には set なので、つまり基本的に const オブジェクトを格納する形になっているので、非 const アクセスをするのはちょっと面倒です。set よりは改善されてますが。非 const で問題ないインデックスだけが張られているときは、自動的に非constモード…みたいな動作をしてくれると面白そうだけど、少なくとも現状はそうなってないみたい。
具体的なアルゴリズムとかインデックスを指定するんじゃなくて、「このキーとこのキーでは速くアクセスしたいけど他はどうでもいい」みたいな指定ができると面白いんでは、というのは面白そうだなあ。 multi_index<P, by<&P::twId, &P::htId>> tt; こんなのかなあ例えば。 tt.find<&P::twId>("kinaba"); getまで省略して一気にとか。

Derive Your Dreams