最近休日は昼近くまで寝てることが多い。よっぽど普段の睡眠時間が足りてないのか? いやそんなはずはない、平日でも 5 時間ぐらいは寝ている。
どうでもいいけど、上司に休日もプログラム書いてますと言ったら良い意味で大笑いされた。多分、あまりにも予想通りの解答だったのだろう。
Codeville の diff 関連の部分のソースを読んだり実行したりしてみたのだが、どうもパフォーマンスを出すために正確さをある程度犠牲にしている模様。 diff コマンドの出力と比べると一目瞭然。まあ差分なんて間違いがなくてあまりにアホ過ぎなければ何だっていいのかもしれないけど。
でまあ LCS の位置を高速に探すアルゴリズムを考えたら、次の奴を思い付いた。とりあえずこの前の奴よりは 3 倍以上速い。
def lcs_search(s1, s2):
tbl = [[0 for x in s1] for y in s2]
l1 = len(s1)
l2 = len(s2)
r1 = range(l1)
r2 = range(l2)
cache = set()
def _fill(x, y):
while x < l1 and y < l2 and s1[x] == s2[y]:
tbl[y][x] = 1
cache.add(y)
x += 1
y += 1
for p1 in r1:
for p2 in r2:
if p2 in cache: continue
if s1[p1] == s2[p2]:
if tbl[p2][p1] != 0: break
_fill(p1, p2)
break
return tbl
def lcs_point(s1, s2):
tbl = lcs_search(s1, s2)
stack = 0
r1 = range(len(s1))
r2 = range(len(s1))
for x in r1:
for y in r2:
if y < stack: continue
if tbl[y][x] == 1:
yield (x, y)
stack = y
breakでも LCS となる文字列の位置を返すだけなら、正確さが多少あれでも Codeville の方が数十倍速いんだよな。
次の奴は本当あってるかどうかわからんけど、 Codeville よりも正確で、 Codeville の 3 倍程度しか時間がかからない。
def lcs_find(s1, s2):
index = {}
l1 = len(s1)
for i in range(l1):
c = s1[i]
index[c] = index.get(c, [])
index[c].append(i)
r = []
for i, v in enumerate(s2):
if v in index:
l = index[v]
if l:
x = l.pop(0)
if not [p for p in r if p[0] > x]:
r.append((x, i))
return rというか段々目的が「Codeville よりも速くて正確な差分アルゴリズムの探索」になっている気がする。いい感じに脱線してきた、これでこそいつもの俺だ。