🔖 Знаешь ли ты, почему diff выглядят по-разному в разных инструментах?
Оказывается, это не баг, а фишка алгоритмов!
🔸Проблема
Есть две версии кода. Нужно показать разницу. Логично, что должен быть один правильный diff, верно?
❌ Неправильно! Существует множество "правильных" diff'ов.
Пример:
a
+b
-c
d
Столь же правильно:
a
-c
+b
d
Они идентичны, но выглядят совсем по-разному!
💡 Алгоритм Майерса
Большинство инструментов используют алгоритм Майерса. Он находит один из минимальных diff'ов (но не обязательно самый читаемый).
Сложность: O(ND) в обычных случаях, но может деградировать до O(N²) в наихудшем!
🔸 Почему они отличаются
1️⃣ Разная реализация — даже один алгоритм может дать разные результаты
2️⃣ Эвристики — добавляют быстродействие, но жертвуют качеством
3️⃣ Постобработка — переставляют строки, чтобы улучшить читаемость
🔸 Три режима
Есть компромисс между скоростью и качеством:
🔸 Fast — максимум скорости, минимум качества
🔸 Default — баланс (используется везде)
🔸 Minimal — идеальный diff, но медленнее
💡 Главное открытие
Читаемость diff определяется не только алгоритмом, но и его реализацией + постобработкой
Поэтому в GitHub качество выше, чем в простом
diff утилите. Они используют лучшую реализацию с постобработкой (indent heuristic). Подробнее по ссылке ниже ⬇️
📎 Статья
🎙 Новости
📝 База вопросов