Наихудшее поведение Python's HtmlDiff.make_table () - PullRequest
1 голос
/ 10 августа 2011

Я использую функцию 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, у которых нет этой проблемы в худшем случае?

1 Ответ

0 голосов
/ 23 февраля 2013

CPython проблемы, связанные с этим:

...