何だよこの大雨は。全くもってふざけているね。
それはともかく、今日はあまり仕事のない日だった。今のところ俺は画面証跡のキャプチャなどのテスト回りの仕事とテスト環境用のスクリプトの作成の仕事をしているのだが、そういった作業ってのは回ってこない日も結構あるものだ。つーわけで今日は今まで作ったスクリプトのパフォーマンスチューニングをしていたのだが、結構これが面倒臭かった。
最高に難儀したスクリプトでは、処理時間が 3 秒後半に対して一つのメソッドの (サブ関数抜きの) 合計実行時間が 2.8 秒と見事に 80 対 20 の法則になっていた。テストデータ作成というスクリプトの性質上、メモ化やエセ遅延評価といった手段がことごとく使えず (使えるところでは元から時間を食っていない) 、地道にコードの書き方を変えて対処することに。
俺バージョン管理ツールの差分部分は、当初は Python の difflib を使うつもりだった。が、どうもこれの出力が気に食わない。時々出てくる ? で始まる行もそうだし、出来ればもっと効率的な形式にしたい。というわけで差分アルゴリズムを考え出したのだが、実用的な差分アルゴリズムは大変面倒臭いということがわかった。
例えば abcdefg (s1 とする) と fhiabcedzmg (s2 とする) という文字列から差分を取る場合、一番嬉しい形式は
という形式だろう。つまり s1 から s2 の間で順序の相対関係を保ったまま abceg もしくは abcdg の文字列を抜き出すわけだが、これは Longest Common Subsequence というかなり有名な問題らしい。何でもゲノム方面でも使われているとかいないとか (この辺適当にしか調べてません) 。
じゃあこれをどうやって実装するのかだが、とりあえず考えられる限り最悪の実装の一つ。
def lcs_fool(s1, s2):
for x, c1 in enumerate(s1):
for y, c2 in enumerate(s2):
if c1 == c2:
for r in lcs_list(s1[x+1:], s2[y+1:]):
yield [c1] + r
else:
yield [c1]どうみても計算量がいかれてます、本当にありがとうございました。下手に要素数の多いシーケンスを与えると、いつまでたっても計算が終わらねえ。とりあえずこれを動かしたい人は数文字程度で我慢した方が幸せになれるよ。
流石にこれはバカ過ぎてお話にならないので、次の実装を考えてみる。
def lcs_table(s1, s2):
l1 = len(s1)+1
l2 = len(s2)+1
tbl = [[0 for i in range(l2)] for j in range(l1)]
for p1 in range(l1):
for p2 in range(l2):
if p1 == l1-1 or p2 == l2-1: p = 0
elif s1[p1] == s2[p2]:
p = tbl[p1-1][p2-1]+1
else:
p = max(tbl[p1-1][p2], tbl[p1][p2-1])
tbl[p1][p2] = p
return tblこれを実行すると、前述の二つの文字列に対して次のような表を生成する。
f h i a b c e d z m g
a 0 0 0 1 1 1 1 1 1 1 1
b 0 0 0 1 2 2 2 2 2 2 2
c 0 0 0 1 2 3 3 3 3 3 3
d 0 0 0 1 2 3 3 4 4 4 4
e 0 0 0 1 2 3 4 4 4 4 4
f 1 1 1 1 2 3 4 4 4 4 4
g 1 1 1 1 2 3 4 4 4 4 5実際には余分な列が付いているが、これはアルゴリズム的にターミネータのようなものが必要になったため。詳しくは Longest Common Subsequences を参照。ここから LCS となる文字列を抜き出すのは簡単なので、そのコードは省略。
それで上記のコードから 140 行程度のファイルに対して行単位で LCS を作成すると、それだけで 60 ミリ秒ほどかかってしまう。 Python 標準の difflib の SequenceMatcher では目的が全然違うとはいえ 1 ミリ秒で処理が終わる。
というわけでより高速なアルゴリズムを探索している。今ちょっと調べてみたら、 Codeville の LCS 検索と差分生成は流石にかなり速い。ここまでは望まなくとも、処理時間を 10 分の 1 程度にしなければ使いものにならないだろう。恐らく現状では O(M*N) のオーダーのはずなので、 1000 行単位のファイルに対して使うのは気が退ける。