Diary?::2006-06-10

01:32 読書記録「もずく、ウォーキング!」

もずくって俺みたい。以上。

流石にそれだけじゃあアレなんでもうちょっと書くと、「サナギさん」よりもさらに大幅にこっち寄りの作風。というか、「サナギさん」から 4 コマじゃない回をぶっこ抜いて灰汁抜きした感じ。つまり不条理分や毒々しさはあまりない。そっち方面を期待すると肩透かしを食らうだろうが、この手の作家に固定的な期待を持つのはどうかと思っている俺は結構面白く読めたかな。

いきなり何も知らない人に「酢めし疑獄」を勧めるのはノルマンディー上陸作戦よりも無茶なので、施川ユウキを布教するにはいいかもしれない。あーでもそれなら「サナギさん」でいいか?

02:53

ここ最近やる気が起きずに放置していた俺専用バージョン管理ツールの開発を再開。とりあえず Codeville よりも速くて正確な差分アルゴリズムを探していたのだが、 ViVi の作者による文書と FreeBSD の diff のソースと pukiwiki のソースとえーとあと何だっけ? とにかく色んな文献とソースコードから要素をちょっぱってパッチワーク気味に書いたのが以下のコード。

def lcs_find(s1, s2):
  l1 = len(s1)
  l2 = len(s2)
  if l1 == 0 or l2 == 0:
    return []
  if l1 < l2:
    l1, l2 = l2, l1
    s1, s2 = s1, s2
  delta = l1 -l2
  fp = [-1 for i in range(l1+l2+3)]
  path = [[] for i in range(l1+l2+3)]
  def snake(k, x, y):
    if x > y:
      _k = k-1
      _y = x
    else:
      _k = k+1
      _y = y
    _x = _y-k
    path[k] = path[_k]
    while _x < l1 and _y < l2 and s1[_x] == s2[_y]:
      path[k].append((_x, _y))
      _x += 1
      _y += 1
    return _y
  def _fix(ls):
    stack = ls.pop(0)
    for p in ls:
      if p[0] > stack[0] and p[1] > stack[1]:
        yield stack
        stack = p
    yield stack
  p = 0
  while 1:
    k = -p
    while k < delta:
      fp[k] = snake(k, fp[k-1]+1, fp[k+1])
      k += 1
    k = delta+p
    while k > delta:
      fp[k] = snake(k, fp[k-1]+1, fp[k+1])
      k -= 1
    fp[delta] = snake(delta, fp[delta-1]+1, fp[delta+1])
    if fp[delta] >= l2:
      return _fix(path[delta])
    p +=1

実行させてみたら、これが本当に速い。 LCS の位置情報しか取りだしていないが、ここまで出来れば後はどうにでもなる。

追記。書き直すのが面倒なのでこっちはそのままにしておくけど、 fp と path は辞書にするとさらに速くなる。リストの生成が結構なコストになっているはずなので、これはシーケンスのサイズが大きくなる程効いてくる。

10:13

ちょっと気になって調べてみたんだが、どうも最近の Python では実効速度は while < range < xrange の順に速いらしい。だから基本的には xrange を使った方がパフォーマンスは稼げる。おかしいな、どこかで while ループが一番速いとかいうのを読んだ覚えがあるんだが。記憶違いかな。

というわけで LCS のコードを書き直すとこうなる。

def find(s1, s2):
  l1 = len(s1)
  l2 = len(s2)
  if l1 == 0 or l2 == 0:
    return []
  if l1 < l2:
    l1, l2 = l2, l1
    s1, s2 = s1, s2
  delta = l1 -l2
  fp = {}
  path = {}
  def snake(k, x, y):
    if x > y:
      _k = k-1
      _y = x
    else:
      _k = k+1
      _y = y
    _x = _y-k
    path[k] = path.get(_k, [])
    while _x < l1 and _y < l2 and s1[_x] == s2[_y]:
      path[k].append((_x, _y))
      _x += 1
      _y += 1
    return _y
  def _fix(ls):
    if len(ls) > 0:
      stack = ls.pop(0)
      for p in ls:
        if p[0] > stack[0] and p[1] > stack[1]:
          yield stack
          stack = p
      yield stack
  p = 0
  while 1:
    for k in xrange(-p, delta):
      fp[k] = snake(k, fp.get(k-1, -1)+1, fp.get(k+1, -1))
    for k in xrange(delta+p, delta, -1):
      fp[k] = snake(k, fp.get(k-1, -1)+1, fp.get(k+1, -1))
    fp[delta] = snake(delta, fp.get(delta-1, -1)+1, fp.get(delta+1, -1))
    if fp[delta] >= l2:
      return _fix(path[delta])
    p +=1

なんだかむちゃくちゃなコードだが、今回ばかりはパフォーマンス優先ということで。

19:05

何で会社の人からのメールが spam 扱いされてるのかと思っていたが、何のことはなくて署名に♪だの★だのが出てくるからだった。

……署名の部分はぶった切った上で spam 判定してくれないかなあ、 Opera のメーラ。

19:40

カレーばかり連続で食っていると嫌になるので、工夫して変化を付けてみる。

チーズカレー

冷やご飯に冷めたカレーをかけてとろけるチーズを乗せるあとは電子レンジでチン。割りといける

目玉焼きカレー

そのまんま。かなりいける。

ベーコンエッグカレー

なるべく肉を避けてカレーを盛りつけるのがポイント

でも結局はカレーには違いないのでいかんともしがたい。ああ、明日の朝飯もカレーか……。