Python 2.7 のdifflib.HtmlDiff.make_table()関数を使用して、内部テスト ケース ランナーの予想されるファイルと実際のファイルの差分を生成しています。それらは最終的に HTML テスト レポートになります。
これまでのところ、これは問題なく機能しています。より大きなファイル (〜 400 KiB) を含むテスト ケースを追加するまでは、多くの場合、改行が含まれていませんでした。ほとんどすべてのテスト ケースは 2 秒未満で実行され、さらに複雑なものは 4 秒もかかります。この新しいものは、通過するときは同じくらい速いですが、失敗するまでに 13 分 (!) かかります。そのすべての時間は、レポートの生成に費やされます。それがどのように問題であるかを理解していただければ幸いです。
これを実証する試み（おそらく最善の方法ではないことはわかっています）：
s = """import os, difflib
a = [os.urandom(length)]
b = [os.urandom(length)]
difflib.HtmlDiff().make_table(a, b)"""
import timeit
print 'length 100:', timeit.timeit(s, setup='length = 100', number=1)
print 'length 1000:', timeit.timeit(s, setup='length = 1000', number=1)
print 'length 10000:', timeit.timeit(s, setup='length = 10000', number=1)
print 'length 100000:', timeit.timeit(s, setup='length = 100000', number=1)
print 'length 400000:', timeit.timeit(s, setup='length = 400000', number=1)
そして結果：
length 100: 0.022672659081
length 1000: 0.0125987213238
length 10000: 0.479898318086
length 100000: 54.9947423284
length 400000: 1451.59828412
difflib.ndiff()（make_table()私が理解している限り、これは内部で使用されています）この問題はないようです：
s = """import os, difflib
a = [os.urandom(length)]
b = [os.urandom(length)]
difflib.ndiff(a, b)"""
import timeit
print 'length 100:', timeit.timeit(s, setup='length = 100', number=100)
print 'length 1000:', timeit.timeit(s, setup='length = 1000', number=100)
print 'length 10000:', timeit.timeit(s, setup='length = 10000', number=100)
print 'length 100000:', timeit.timeit(s, setup='length = 100000', number=100)
print 'length 400000:', timeit.timeit(s, setup='length = 400000', number=100)
私にこれを与えます：
length 100: 0.0233492320197
length 1000: 0.00770079984919
length 10000: 0.0672924110913
length 100000: 0.480133018906
length 400000: 1.866792587
これは非常に合理的に見えます。つまり、比例しています。サイズが 4 倍になると、4 倍の時間がかかります。
ここからどこへ行くべきかわからない。違いがある場合、HTML ジェネレーターは多くのバックトラックを行うと思います (ただし、 ndiff() で既に処理されていると思われるかもしれません)。以前に中止し、あきらめて、セクション全体を「別」としてマークするように指示できますか?
差分を生成するためのさまざまなアルゴリズムがたくさんあることを理解しています。この場合、非常に詳細な分析を行い、あらゆる場所で再同期を試みる必要はありません。ファイル上のどの位置が異なるかを大まかに教えてから、妥当な時間枠で終了する必要があります。
あるいは、この最悪の問題を抱えていない HTML 生成 Python diff ライブラリは他にありますか?