トップ «前の日記(2006-08-01) 最新 次の日記(2006-08-03)» 月表示 編集

日々の流転


2006-08-02 [長年日記]

λ. 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のだが……。遺族の方には申し訳ないが、具体的利益のためにではなく、みずからの政治的主張のために裁判所を利用しているように見えて仕方が無い。

Tags: 時事

*1 最近、やいざわさんの<URL:http://www.yaizawa.jp/diary/?date=20060727#p02>へのコメントにも書いた

λ. 万能数値表現法 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—リストカット事件』 乙一

GOTH―リストカット事件(乙一) を読んだ。 先に漫画の方を読んでいたからか、話の持っていきかたや描写が冗長に思えて仕方が無い。内容は普通に面白かったが。

Tags:
本日のツッコミ(全4件) [ツッコミを入れる]
ψ Keigo IMAI (2006-08-03 23:36)

お久しぶりです。<br>>万能数値表現法<br>Gray Codeに似てますね。(どちらもちゃんと理解してないんですが)<br>http://www.i.h.kyoto-u.ac.jp/~tsuiki/research/gray1.html

ψ さかい (2006-08-04 16:47)

お久しぶりです。<br>URR と Gray Code ってそんなに似てます?<br>共通してるのは区間への分割を繰り返す所くらいだと思いますが、これは実数の符号化では一般的ですし……

ψ Keigo IMAI (2006-08-05 07:28)

なるほどお…一般的なんですね。

ψ さかい (2006-08-09 15:31)

多分……<br><br>私が直接見たことのあるのだと、例えばこんな話があります。<br>Yves Bertot. CoInduction in Coq<br>http://www.cs.chalmers.se/Cs/Research/Logic/TypesSS05/Extra/bertot.pdf<br>http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20051010#p01