Python 的 HtmlDiff.make_table() 最坏情况表现

Question

我正在使用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

根据我的理解，make_table()内部使用的difflib.ndiff()似乎没有这个问题：

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

看起来很合理，也就是说，文件大小增加四倍，所需时间也增加四倍。

我不知道接下来该怎么办。我猜测HTML生成器在处理差异时会进行很多回溯（虽然你会认为ndiff()已经处理过这些了）。我能否让它提前终止，放弃并将整个部分标记为“不同”？

我知道生成差异的算法有很多种。在这种情况下，我不需要它进行非常深入的分析并尝试在每个地方重新同步。我只需要它大致告诉我文件的哪个位置不同，然后在合理的时间内结束。

另外，是否有其他生成HTML的Python差异库，没有这种最坏情况的问题？

性能优化数据结构 HTML生成文件处理测试报告算法复杂度回溯算法差异比较

Python 的 HtmlDiff.make_table() 最坏情况表现

1 个回答

撰写回答