Я использую функцию Python 2.7 difflib.HtmlDiff.make_table() для генерации различий между ожидаемыми и фактическими файлами для внутреннего бегуна тестового набора. Они заканчиваются в отчете по тестированию HTML.
До сих пор это работало нормально - пока я не добавил тестовый пример с большими файлами (~ 400 КиБ), большим количеством различий, часто без разрывов строк. Почти все мои тесты выполнены менее чем за 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 () уже обработал это). Могу ли я сказать, чтобы он прерывался раньше, сдавался и помечал весь раздел как «другой»?
Я понимаю, что существует множество разных алгоритмов генерации различий. В этом случае мне не нужно делать очень глубокий анализ и пытаться ресинхронизироваться везде. Мне просто нужно, чтобы примерно сказать мне, с какой позиции в файле отличается, а затем завершить в разумные сроки.
В качестве альтернативы, существуют ли другие библиотеки Python diff, генерирующие HTML, у которых нет этой проблемы в худшем случае?