Comments 31
> Если уважаемым читателям интересны подробности и особенности
Неужели вы и вправду полагаете, что на этом ресурсе возможен ответ «категорически нет»? :)
Неужели вы и вправду полагаете, что на этом ресурсе возможен ответ «категорически нет»? :)
Спасибо. Конечно было бы совсем хорошо, если бы вы добавили несколько схем и ссылок в пост.
Как продолжение статьи хотелось бы узнать о возможности делать diff исходных файлов определённого языка на основании AbstracSyntaxTree, это моя мечта прям:)
Спасибо!
Спасибо!
Можете привести пример программы/утилиты/инструмента, которая при сравнении пользуется именно распарсенным представлением исходного кода? Мне кажется, такой подход к сравнению не очень прагматичен (я бы даже сказал, он слишком теоретизирован), т.к. на практике сравниваемые файлы могут быть не полными, содержать ошибки, препятствующие построению «корректного» дерева. Часто правится whitespace или комментарии, что как мне кажется, вообще не отражается на дереве. Также бывает нужно сравнить просто текстовые файлы или файлы, написанные на разных языках, либо на разных диалектах одного языка. Хотя, конечно, тупое сопоставление по «begin»..«end» (или по { }) в TortoiseDiff, действительно, оставляет желать лучшего…
в том и дело, таковых примеров нет, а очень хотелось бы, хотя бы на уровне интеграции в IDE.
Я уже давно разрабатываю концепцию такую, плюс возможность вместе с коммитом так же заливать историю рефакторинга. Представьте, Вы используете в проекте чужую либу, и обновляете её. Обычно, приходится вручную потом править по changelog-у изменённые классы и прочее. А тут, мы бы имели специальный рефакторинг-diff, применив который, у нас поправятся все подписи методов и прочее. Это очень круто, и очень надеюсь, что кто-нибудь по типу JetBrains сделают такое
Я уже давно разрабатываю концепцию такую, плюс возможность вместе с коммитом так же заливать историю рефакторинга. Представьте, Вы используете в проекте чужую либу, и обновляете её. Обычно, приходится вручную потом править по changelog-у изменённые классы и прочее. А тут, мы бы имели специальный рефакторинг-diff, применив который, у нас поправятся все подписи методов и прочее. Это очень круто, и очень надеюсь, что кто-нибудь по типу JetBrains сделают такое
Посмотрите в Eclipse меню Refactoring -> Create Script / Apply Script. Это как раз про историю рефакторинга.
Вместе с jar файлом тоже можно экспортировать: bugs.eclipse.org/bugs/show_bug.cgi?id=139741
Вместе с jar файлом тоже можно экспортировать: bugs.eclipse.org/bugs/show_bug.cgi?id=139741
Похоже на
git pull --rebase remote/master
git fetch & git rebase
xml, например
Конечно, напишите продолжение.
>> да, нам действительно придется загрузить оба сравниваемых документа целиком в память
Это еще зачем?
Для построения списка индексируемых хешей можно файл читать последовательно, блоками небольшого размера, и в памяти держать только текущий и предыдущий блоки.
Это еще зачем?
Для построения списка индексируемых хешей можно файл читать последовательно, блоками небольшого размера, и в памяти держать только текущий и предыдущий блоки.
При поиске наибольшей общей подпоследовательности на основе хэшей происходит попарное сравнение хэшей всех абзацев первого и второго файла. Если хэши совпадают, приходится сравнивать сами абзацы, т.к. не бывает хэшей без коллизий. Конечно, можно разрешить эти коллизии заблаговременно (еще на этапе хэширования), т.е. вычислить своеобразные «безколлизионные» хэши, но для этого также понадобится нахождение всех абзацев в памяти (хотя бы на этапе хэширования).
Вобщем-то, переживать из-за наличия сравниваемых файлов в памяти сильно не стоит, т.к. в контексте обсуждаемой темы мы выполняем сравнение, чтобы показать различия в файлах. Соответственно загружать файлы целиком в память все равно придется, чтобы показать вычисленные изменения :)
Вобщем-то, переживать из-за наличия сравниваемых файлов в памяти сильно не стоит, т.к. в контексте обсуждаемой темы мы выполняем сравнение, чтобы показать различия в файлах. Соответственно загружать файлы целиком в память все равно придется, чтобы показать вычисленные изменения :)
Что-то Вы конкретно гоните (относительно неизбежности загрузки обоих файлов в память):
Чтобы Вам проще было понять свою ошибку, представьте, что Вы сравниваете 2 огромных SQL-дампа базы данных (размерами по 2 Гига каждый).
1) если Вы хотите показать вычисленные изменения, то, разумеется нет смысла грузить (причем одновременно) оба файла (целиком О_о) в память.
2) если желаете, могу еще штук двадцать причин перечислить, почему так точно не стоит делать.
Чтобы Вам проще было понять свою ошибку, представьте, что Вы сравниваете 2 огромных SQL-дампа базы данных (размерами по 2 Гига каждый).
1) если Вы хотите показать вычисленные изменения, то, разумеется нет смысла грузить (причем одновременно) оба файла (целиком О_о) в память.
2) если желаете, могу еще штук двадцать причин перечислить, почему так точно не стоит делать.
Под словами «показать изменения», я не имел в виду не перечислить различия (например, в унифицированном diff-формате), а наглядно визуально отобразить содержимое обоих сравниваемых файлов с цветовой подсветкой различающихся фрагментов.
Насчет фраз «конкретно гоните», давайте, пожалуйста, без оскорблений. О неизбежности я не говорил, подходы к сравнению бывают различные. В рассмотренном мной подходе грузить в память все-таки придется. А что касается 2-х огромных SQL-дампов, они в память действительно с трудом влезут. Создать, к примеру, текстовый редактор, который умеет визуально отображать и редактировать файлы такого размера — уже само себе нетривиальная задача (см. AkelPad).
Насчет фраз «конкретно гоните», давайте, пожалуйста, без оскорблений. О неизбежности я не говорил, подходы к сравнению бывают различные. В рассмотренном мной подходе грузить в память все-таки придется. А что касается 2-х огромных SQL-дампов, они в память действительно с трудом влезут. Создать, к примеру, текстовый редактор, который умеет визуально отображать и редактировать файлы такого размера — уже само себе нетривиальная задача (см. AkelPad).
Блин, никак не получается без оскорблений!
Для просмотра (и даже для редактирования) файлов не требуется загружать их в память целиком!
Представляете, что было бы, если бы для просмотра любого видеофильма, медиаплейер требовал бы загрузки всего видеофайла в память!
А, с отображением текстовых файлов размером до двух гигабайт включительно отлично справляется даже встроенный просмотрщик Досовского Волков-Командера!
Для просмотра (и даже для редактирования) файлов не требуется загружать их в память целиком!
Представляете, что было бы, если бы для просмотра любого видеофильма, медиаплейер требовал бы загрузки всего видеофайла в память!
А, с отображением текстовых файлов размером до двух гигабайт включительно отлично справляется даже встроенный просмотрщик Досовского Волков-Командера!
Если уж 2 громадных файла нужно сравнить, то можно и не загружать его весь в памяти, а просто сохранять смещение обработанных абзацев, и при необходимости перечитывать их заново. Будет шуршать диск, но память будет расходоваться экономно. Для отображения это также применимо.
Это вообще очень широкая тема для рассуждений.
Считается, что дисковые операции очень дороги по времени и потому сильно завышают их цену. Далее, для упрощения, просто стремятся к минимизации дисковых операций. Такой подход довольно неплохо работает.
Однако, на больших объёмах данных выясняется, что стоимость дисковых операций не так уж и высока. И что удержать на диске и обрабатывать 1Тб данных гораздо дешевле, чем в оперативной памяти. И вот тут, вместо того, чтобы создавать алгоритмы более высокого порядка, просто начинают оптимизировать работающие схемы.
Считается, что дисковые операции очень дороги по времени и потому сильно завышают их цену. Далее, для упрощения, просто стремятся к минимизации дисковых операций. Такой подход довольно неплохо работает.
Однако, на больших объёмах данных выясняется, что стоимость дисковых операций не так уж и высока. И что удержать на диске и обрабатывать 1Тб данных гораздо дешевле, чем в оперативной памяти. И вот тут, вместо того, чтобы создавать алгоритмы более высокого порядка, просто начинают оптимизировать работающие схемы.
Вы че? сговорились что ли?
Или на Вас так весеннее солнышко действует?
Нахождение различий двух файлов — это принципиально однопроходная операция!
И не требует полной загрузки файлов в память независимо от размеров самих файлов.
Данная операция всегда эффективно выполнялась на-ура даже из-под DOS с использованием всего 640 килобайт основной памяти!
Или на Вас так весеннее солнышко действует?
Нахождение различий двух файлов — это принципиально однопроходная операция!
И не требует полной загрузки файлов в память независимо от размеров самих файлов.
Данная операция всегда эффективно выполнялась на-ура даже из-под DOS с использованием всего 640 килобайт основной памяти!
Не совсем понятно, что Вы имели в виду под словом «однопроходная». Хэширование абзацев операция действительно однопроходная, но при вычислении хэша очередного абзаца вам придется держать все предыдущие уже прохэшированные абзацы в памяти, если вы хотите иметь возможность проверить факт коллизии (для тех кто не в танке, коллизия — это когда абзацы разные, а хэш у них одинаковый). Если коллизии не проверять (притвориться, что их нет, хотя мы знаем, что это не так), тогда конечно можно в памяти держать только хэши, а по абзацам сравниваемых документов просто последовательно пробежаться, загружая их в память лишь по одному.
Но сам поиск наибольшей общей подпоследовательности (хоть на основе хэшей, хоть на основе самих абзацев) — это никак не однопроходная операция, у нее сложность O (N*M). Подробнее тут.
Я пишу об этом не по наслышке, т.к. сам лично разрабатывал систему контроля версий документов (узко специализированную, SVN не предлагать) с хранением истории изменений в виде diff'ов и наглядным визуальным сравнением.
Но сам поиск наибольшей общей подпоследовательности (хоть на основе хэшей, хоть на основе самих абзацев) — это никак не однопроходная операция, у нее сложность O (N*M). Подробнее тут.
Я пишу об этом не по наслышке, т.к. сам лично разрабатывал систему контроля версий документов (узко специализированную, SVN не предлагать) с хранением истории изменений в виде diff'ов и наглядным визуальным сравнением.
Остыньте уже, похоже что-то весеннее действует на вас.
Хотите переубедить — выкладывайте ваш «принципиально однопроходный» код. Да не на коленке сляпанный, а действительно эффективно показывающий файлы, не тормозящий при прокрутке из начала в конец.
Другие аргументы — это вон во дворе на лавочке прокатят, но не здесь.
Хотите переубедить — выкладывайте ваш «принципиально однопроходный» код. Да не на коленке сляпанный, а действительно эффективно показывающий файлы, не тормозящий при прокрутке из начала в конец.
Другие аргументы — это вон во дворе на лавочке прокатят, но не здесь.
А нельзя ли скрытую марковскую модель каким-то образом применить для сравнения файлов?
Они же успешно применяются в таких задачах, как синхронизация играемой музыки и нот, речи и текста и т.д.
Они же успешно применяются в таких задачах, как синхронизация играемой музыки и нот, речи и текста и т.д.
Спасибо за топик, действительно интересно и да — пишите еще =)
Встречный вопрос. Вы сказали, что разрабатывали систему контроля версий. Как поступали с не текстовыми файлами? Если таковые имелись, конечно…
Встречный вопрос. Вы сказали, что разрабатывали систему контроля версий. Как поступали с не текстовыми файлами? Если таковые имелись, конечно…
Система контроля версий была частью узкоспециализированной системы электронного документооборота. Контроль версий (история изменений) и визуальное сравнение работало лишь для документов определенного внутреннего формата (который можно считать подмножеством формата RTF). Для визуального сравнения данный формат парсился и осуществлялось сравнение текста по абзацам + сравнение доп. информации (например, типа выравнивания абзаца, стилей шрифта и т.п.).
Для файлов любого другого формата хранить полную историю изменений и выполнять визуальное сравнение не требовалось. Хранились лишь 2 версии: самая первая (версия файла на момент добавления его в систему) и последняя версия, содержащая наиболее актуальные правки. Если бы нужно было хранить полную историю изменений файлов произвольного формата, то либо хранились бы все версии целиком (например, тупо сжатые алгоритмом GZip), либо пришлось бы реализовать один из алгоритмов бинарного сравнения. Например, бесплатная программа ZSKSoft File Comparer одинаково хорошо сравнивает как текстовые, так и бинарные файлы, и показывает различия в них.
Для файлов любого другого формата хранить полную историю изменений и выполнять визуальное сравнение не требовалось. Хранились лишь 2 версии: самая первая (версия файла на момент добавления его в систему) и последняя версия, содержащая наиболее актуальные правки. Если бы нужно было хранить полную историю изменений файлов произвольного формата, то либо хранились бы все версии целиком (например, тупо сжатые алгоритмом GZip), либо пришлось бы реализовать один из алгоритмов бинарного сравнения. Например, бесплатная программа ZSKSoft File Comparer одинаково хорошо сравнивает как текстовые, так и бинарные файлы, и показывает различия в них.
Sign up to leave a comment.
О подходах к сравнению версий файлов