<tl;dr>
При генерации diff-патчей для управления версиями исходного кода стоило бы использовать оптимизации, перечисленные в самом низу этой статьи (см. <optimizations>) в моей реализации diff для Ruby, для создания патчей diff?
</tl;dr>
<introduction>
Я программирую то, чего никогда не делал раньше, и, возможно, уже есть инструменты, чтобы делать именно то, что я программирую, но на данный момент мне очень весело заботиться, поэтому я все еще собираюсь делать это с нуля, даже если для этого есть инструмент.
Так или иначе, я работаю над приложением Ruby on Rails и мне нужна определенная функция. По сути, я хочу, чтобы каждая запись в моей таблице, например, в таблице видеоигр, имела сохраненный фрагмент текста, представляющий обзор или что-то в этом роде для этой записи таблицы. Тем не менее, я хочу, чтобы этот текст мог редактировать любой зарегистрированный пользователь, а также отслеживать различные представления в системе контроля версий. Самое простое решение, о котором я могу подумать, - это просто реализовать решение, которое отслеживает текстовое тело и историю изменений патчей различных версий текстового тела как объекты в Ruby, а затем сериализует его, предпочтительно в удобочитаемой для человека форме (поэтому я буду скорее всего, для этого используйте YAML) для редактирования, если это необходимо из-за повреждения программной ошибкой или из-за ошибки администратора, выполняющего редактирование какой-либо версии.
Итак, сначала я просто попытался сначала погрузиться в эту функцию, чтобы обнаружить, что проблема создания diff-патча сложнее, чем я думал, чтобы сделать это эффективно. Поэтому я провел небольшое исследование и натолкнулся на некоторые идеи. Некоторые из них я уже реализовал, а некоторые нет. Тем не менее, все это в значительной степени вращается вокруг самой длинной общей проблемы подпоследовательности, поскольку вы уже знаете, если вы уже сделали что-нибудь с diff или похожими на diff функциями и оптимизируете функцию, которая ее решает.
В настоящее время он у меня есть, поэтому он обрезает сравниваемые версии основного текста с начала и до конца, пока не будут найдены несовпадающие строки. Затем он решает проблему с использованием матрицы сравнения, но вместо того, чтобы увеличивать значение, хранящееся в ячейке, когда он находит совпадающую строку, как в большинстве самых длинных общих алгоритмов подпоследовательности, которые я видел в примерах, я увеличиваю, когда у меня есть несоответствующая строка, так как вычислить расстояние редактирования вместо самой длинной общей подпоследовательности. Хотя, насколько я могу судить между двумя подходами, они, по сути, являются двумя сторонами одной медали, поэтому любой из них может быть использован для получения ответа. Затем он отслеживает обратную трассировку через матрицу сравнения и отмечает, когда произошло увеличение и в какой соседней ячейке (запад, северо-запад или север), чтобы определить запись различий в этой строке, и предполагает, что все остальные строки не изменились.
Обычно я бы так и оставил, но поскольку это относится к среде Rails, а не к какому-то автономному скрипту на Ruby, я начал беспокоиться о необходимости хотя бы достаточной оптимизации, так что если спамер каким-то образом знал, как я реализовал систему контроля версий и знал, что мой сценарий наихудшего сценария по-прежнему не сможет так сильно ударить по серверу. После некоторого поиска и чтения исследовательских работ и статей через Интернет я наткнулся на несколько, которые кажутся приличными, но у всех, похоже, есть свои плюсы и минусы, и мне трудно решить, насколько хорошо в этой ситуации сбалансированы плюсы и минусы из. Так стоят ли те, что здесь перечислены, того стоит? Я перечислил их с известными плюсами и минусами.
</introduction>
<optimizations>
Разбейте сравниваемые последовательности на несколько подпоследовательностей , разделив строки без изменений, а затем обрезав каждую секцию неизмененных строк в начале и конце каждой секции. Затем решите расстояние редактирования каждой подпоследовательности.
Pro : Изменяет увеличение времени по мере того, как измененная область становится больше от квадратичной
увеличить до чего-то более похожего на линейное увеличение.
Con : вычисление места разделения уже похоже на то, что вам нужно решить расстояние редактирования
только теперь тебе все равно, как это изменилось. Было бы хорошо, если бы это было решено
процесс ближе к решению расстояния Хэмминга, но одна вставка бросит это
выкл.
Используйте криптографическую хэш-функцию для преобразования всех элементов последовательности в целые числа и обеспечения уникальности. Затем определите расстояние редактирования, сравнивая целые хэш-значения вместо самих элементов последовательности.
Pro : операция сравнения двух целых чисел выполняется быстрее, чем операция сравнения
две строки, поэтому после каждого сравнения получается небольшой прирост производительности, который
может быть много в целом.
Con : использование криптографической хэш-функции требует времени для преобразования всей последовательности
элементы и может в конечном итоге стоить больше времени, чтобы сделать преобразование, которое вы получаете от
целочисленные сравнения. Вы можете использовать встроенную хэш-функцию для строки, но
это не гарантирует уникальность.
Используйте ленивый анализ , чтобы рассчитать только три центральные диагонали матрицы сравнения, а затем только дополнительные диагонали по мере необходимости. И затем также использовать этот подход, чтобы, возможно, устранить необходимость в некоторых сравнениях для сравнения всех трех соседних ячеек, как описано здесь .
Pro : может включить алгоритм, который всегда занимает O (n * m) времени, и сделать его таким худшим
Сценарий случая таков, что время, лучший случай становится практически линейным, а средний случай
где-то между двумя.
Con : Это алгоритм, который я видел только в функциональных языках программирования
и мне трудно понять, как преобразовать это в Ruby на основе
как это описано на сайте, указанном выше.
Создайте модуль C и выполняйте тяжелую работу на родном уровне в C и просто создайте для него оболочку Ruby, чтобы Ruby мог выполнять все необходимые ему вызовы.
Pro : Я должен представить, что оценка чего-то подобного может быть ОЧЕНЬ быстрее.
Con : я понятия не имею, как Rails обрабатывает приложения с кодом ruby, имеющим расширения C, и
Вредит мобильности приложения.
Это оптимизация после определения расстояния редактирования, но идея состоит в том, чтобы сохранить дополнительные комбинированные различия с данными, созданными в каждой версии, для сделать структуру данных дельта-дерева с наибольшим недавно сделал diff корневым узлом дерева, поэтому переход к любой версии занимает наихудшее время O (log n) вместо O (n).
Pro : возврат к старой версии намного быстрее.
Con : Это будет означать, что каждый новый коммит, дельта-дерево получит новый корневой узел, который
будет стоить времени на реорганизацию дельта-дерева для операции, которая будет выполняться
гораздо чаще, чем вернуться к версии, не говоря уже о вероятности, что это будет
старая версия.
</optimizations>
Значит, эти вещи стоят усилий?