日々の流転

λ. Persistent Data Structures

MIT の Advanced Algorithms, Fall 2005 の第二回の資料 Persistent Data Structures を読んだ。

変更を行うとそれ以前のデータにアクセス出来なくなる ephemeral なデータ構造に対して、変更を行う以前のデータに自由にアクセス出来るデータ構造が persistent なデータ構造。過去のデータを自由に読むことは出来るけど、変更は最新のデータにしか出来ないのは partialy persistent なデータ構造。

ポインタを使ったデータ構造をpersistentにするための一般的な手法として fat nodes と path copying があるが、どちらも追加的コストが比較的大きい。それに対して、Sleator と Tarjan の modification box を使う手法は両者の優れた点を組み合わせた手法で、O(1) の追加的コストでいけるそうだ。

λ. 靖国神社：元軍人らの遺族、合祀取り消し求め初提訴へ

またしょーもない訴訟を……というのが正直な印象。この手の話は自衛官合祀訴訟の最高裁判決で一応の結論は出ていると思う*1のだが……。遺族の方には申し訳ないが、具体的利益のためにではなく、みずからの政治的主張のために裁判所を利用しているように見えて仕方が無い。

λ. 万能数値表現法 URR

Matzにっき(2006-07-26)より。面白い表現法だな。ただ、-∞ を表現しつつ +∞ や無限小は表現できないというのは少し気持ちが悪い。何故そうなっているかというと、以下のように区間分割を進めていき、その区間の最小値という形で表現されるため。

• [-∞,∞)
  • [0, ∞)
    • [0,1)
      • [0.5, 1)
        • [0.25, 0.5)
        • [0.5, 1)
      • [0, 0.5)
        • [0, 0.25)
        • [0.25, 0.5)
    • [1, ∞)
      • [1, 2)
        • [1, 1.5)
        • [1.5, 2)
      • [2, ∞)
        • [2, 4)
        • [4, ∞)
  • [-∞, 0)
    • [-1, 0)
      • [-0.5, 0)
        • [-0.25, 0)
        • [-0.5, -0.25)
      • [-1, -0.5)
        • [-0.75, -0.5)
        • [-1, -0.75)
    • [-∞, -1)
      • [-2, -1)
        • [-1.5, -1)
        • [-2, -1.5)
      • [-∞, -2)
        • [-4, -2)
        • [-∞, -4)

λ. 『GOTH—リストカット事件』 乙一

を読んだ。 先に漫画の方を読んでいたからか、話の持っていきかたや描写が冗長に思えて仕方が無い。内容は普通に面白かったが。