我正在使用 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
这看起来很合理，即它是成比例的。四倍的大小需要四倍的时间。
不知道从这里去哪里。我猜当存在差异时，HTML 生成器会进行大量回溯（尽管您会认为 ndiff() 已经处理了该问题）。我可以告诉它提前中止，放弃并将整个部分标记为“不同”吗？
我知道有很多不同的算法可以生成差异。在这种情况下，我不需要它进行非常深入的分析并尝试在任何地方重新同步。我只需要它大致告诉我文件上的哪个位置不同，然后在合理的时间范围内终止。
或者，是否有其他生成 HTML 的 Python 差异库没有这种最坏情况的问题？