e.m.tatanova 13 июня 2023
Git Алгоритмы
0
3215

⚖️ 4 основных алгоритма сравнения Git Diff: когда и какой алгоритм использовать

Обзор четырех алгоритмов git diff: Майерса, минимальный, «терпения» и гистограммный. Также приводятся наглядные примеры, чтобы можно было сравнить результат применения каждого алгоритма самостоятельно.

git diff — это команда Git для отображения изменений

  • между рабочим деревом и индексом или другим деревом;
  • между индексом и деревом;
  • между двумя деревьями;
  • в результате слияния;
  • между двумя blob объектами;
  • между двумя файлами на диске.

На момент написания статьи (прим. переводчика: 10 октября 2020) последняя версия git — 2.28.0, и она поддерживает в общей сложности четыре diff-алгоритма, а именно Майерса, минимальный, «терпения» и гистограммный. В следующих разделах я выскажу свое мнение о том, когда следует использовать каждый из этих алгоритмов. В этой статье не рассказывается о том, как работает алгоритм, и/или о его сложности — вы можете загуглить.

Прежде чем углубляться в детали, одно предостережение — ваши результаты могут отличаться от приведенных в зависимости от:

  • типов сравниваемых файлов;
  • изменений в файлах;
  • пакета/версии git, который вы используете.

Одно из множества изменений может повлиять на эффективность алгоритма(-ов) сравнения. Я рекомендую рассматривать эту статью как руководство для начинающих, чтобы выяснить, какой алгоритм лучше всего соответствует вашим потребностям.

--diff-algorithm={myers|default}

Жадный алгоритм, применяемый по умолчанию, первоначально разработанный Юджином В. Майерсом в 1986 году, используется, когда указано myers, default или когда алгоритм для сравнения не указан явно. Он хорошо работает для большинства сценариев, предоставляя хорошо читаемый diff, с приемлемым затрачиваемым числом памяти и временем выполнения.

Когда использовать алгоритм Майерса:

  1. Для почти всех типов файлов и изменений, так как он хорошо работает с большинством;
  2. Если вы не уверены, какой алгоритм сравнения использовать.

--diff-algorithm={minimal}

Алгоритм Майерса использует эвристику, чтобы обеспечить достойный компромисс между временем выполнения и размером входных данных. Однако есть случаи, когда важнее иметь наименьший размер diff'а, пожертвовав для этого увеличением времени выполнения. В утилите Linux diff можно передать флаг, чтобы отключить эвристику и запустить полный набор итераций алгоритма. Следующий абзац о команде Linux diff хорошо описывает это:

Основной алгоритм описан в работе «O(ND) алгоритм поиска различий и его вариации» Юджина Майерса, Алгоритмика Том 1 № 2, 1986 г., с. 251-266; … Если не указана опция --minimal, этот код использует эвристику TOO_EXPENSIVE Пола Эггерта, чтобы ограничить стоимость до O(N**1,5 log N) ценой создания неоптимального вывода для больших входных данных с большими различиями.

Минимальный diff-алгоритм — это эквивалент в контексте Git'а.

Мы можем сравнить результаты, полученные алгоритмами Майерса и минимальным, используя достаточно большой размер входных данных. В приведенном ниже примере я сравниваю количество изменений между двумя наборами статей Википедии при использовании каждого алгоритма:

# Подготовка данных для сравнения
$ curl {article-A,article-B,article-C,article-D} > wikipediaSet1
$ curl {article-E,article-F,article-G,article-H} > wikipediaSet2

# Выполнение команды diff с алгоритмом Майерса
$ git diff --diff-algorithm=myers --shortstat wikipediaSet1 wikipediaSet2
 1 file changed, 7990 insertions(+), 4463 deletions(-)

# Выполнение команды diff с минимальным алгоритмом
~$ git diff --diff-algorithm=minimal --shortstat wikipediaSet1 wikipediaSet2
 1 file changed, 7712 insertions(+), 4185 deletions(-)

Обратите внимание, что можно использовать минимальный diff-алгоритм с небольшим размером входных данных, хотя выходные данные, вероятно, будут идентичны Майерсу, поскольку проблемное место — проитерировать полностью — находится в пределах эвристики.

Когда использовать минимальный алгоритм:

  1. Сравнение большого числа изменений между большими файлами.
  2. Вы не против потратить больше времени на создание меньшего набора различий/изменений.

--diff-algorithm={patience}

Алгоритм «терпения» был изобретен Брэмом Коэном (создателем BitTorrent), и ключевое отличие состоит в том, что он по-разному сопоставляет одинаковые строки между двумя файлами. Этот абзац из поста Джеймса Коглана прекрасно резюмирует это:

Первое, что нужно отметить, это то, что diff-алгоритм «терпения» сам по себе не является diff-алгоритмом. На самом деле это метод сопоставления строк в двух версиях документа, чтобы разбить их на более мелкие части, прежде чем использовать фактический diff-алгоритм, как Майерса, для этих частей.

Чтобы продемонстрировать, как алгоритм «терпения» может создавать более качественные diff'ы, чем Майерс, давайте сначала посмотрим на diff, созданный Майерсом на основе двух Java-файлов с псевдокодом (исходные файлы можно посмотреть в приложении к этой статье):

git diff --diff-algorithm=myers File1 File2

diff --git a/File1 b/File2
index 38ee31b..2624ba3 100644
--- a/File1
+++ b/File2
@@ -1,20 +1,24 @@
 public class File1 {
 
-  public int add (int a, int b)
+  public int sub (int a, int b)
   {
+    // TODO: JIRA1234
+    if ( isNull(a, b) )
+    {
+        return null
+    }
     log();
-    return a + b;
+    return a - b;
   }
 
-  public int sub (int a, int b)
+  public int mul (int a, int b)
   {
-    if (a == b)
+    if ( isNull(a, b) )
     {
-        return 0;
+        return null;
     }
     log();
-    return a - b;
-    // TODO: JIRA1234
+    return a * b;
   }
  }

Мы можем заметить, что в результате работы алгоритма Майерса:

  • найдены совпадающие строки, в которых лишь скобки, между двумя файлами (бесполезно для понимания изменений);
  • добавлен и удален метод sub() в одном и том же файле (на самом деле он был просто перенесен в другое место этого файла).

Такой список изменений понять непросто, так как почти каждая строчка — это изменение. Ревьюер может легко пропустить крайние случаи и/или ошибки в логике.

Давайте теперь посмотрим на diff, полученный алгоритмом «терпения»:

$ git diff --diff-algorithm=patience File1 File2

diff --git a/File1 b/File2
index 38ee31b..2624ba3 100644
--- a/File1
+++ b/File2
@@ -1,20 +1,24 @@
 public class File1 {
 

-  public int add (int a, int b)
-  {
-    log();
-    return a + b;
-  }
-

   public int sub (int a, int b)
   {

-    if (a == b)
-    {
-        return 0;
-    }
-    log();
-    return a - b;

     // TODO: JIRA1234

+    if ( isNull(a, b) )
+    {
+        return null
+    }
+    log();
+    return a - b;
+  }
+
+  public int mul (int a, int b)
+  {
+    if ( isNull(a, b) )
+    {
+        return null;
+    }
+    log();
+    return a * b;

   }
 
 }

С этим diff, созданным алгоритмом «терпения», намного легче наблюдать за изменениями:

  • метод add() был удален;
  • добавлен метод mul();
  • метод sub() имеет некоторые изменения в логике.

Когда использовать алгоритм «терпения»:

  1. Переупорядочивание кода/контента.
  2. Diff Майерса считает совпадающими тривиальные строки.
  3. Одни и те же строки добавляются и удаляются в одном и том же файле.

--diff-algorithm={histogram}

Гистограммный diff-алгоритм — это улучшение алгоритма «терпения», который произошел от jgit. Этот вопрос stackoverflow хорошо объясняет разницу и ссылается на класс jgit HistogramDiff, который содержит подробное объяснение:

Всегда выбирая позицию LCS (наибольшей общей подпоследовательности) с наименьшим числом вхождений, этот алгоритм ведет себя точно так же, как diff-алгоритм «терпения» Брэма Коэна, всякий раз, когда между двумя последовательностями есть уникальный общий элемент. Если уникальных элементов не существует, вместо них выбирается элемент с наименьшим вхождением. Это предлагает более удобочитаемые различия, чем простое использование стандартного O(ND) алгоритма Майерса.

Чтобы лучше понять, почему этот подход лучше, давайте посмотрим на одно из предыдущих изменений при использовании diff-алгоритма «терпения»:

$ git diff --diff-algorithm=patience File1 File2
[...]

   public int sub (int a, int b)
   {

-    if (a == b)
-    {
-        return 0;
-    }
-    log();
-    return a - b;

     // TODO: JIRA1234

+    if ( isNull(a, b) )
+    {
+        return null
+    }
+    log();
+    return a - b;
+  }

[...]

В связи с изменением логики в методе sub() я переместил комментарий TODO с последней строки на первую. К сожалению, алгоритм «терпения», кажется, думает, что комментарий между двумя файлами остался неизменным, а исходные строки были удалены.

Хотя это представление само по себе не является неверным, но предполагает, что вся исходная логика была выброшена (включая выражения log() и return) и вставлен новый набор выражений.

Мы можем показать изменения лучше с помощью гистограммного алгоритма:

$ git diff --diff-algorithm=histogram File1 File2

[..]

   public int sub (int a, int b)
   {
-    if (a == b)
+    // TODO: JIRA1234
+    if ( isNull(a, b) )
     {
-        return 0;
+        return null
     }
     log();
     return a - b;
-    // TODO: JIRA1234
+  }
[...]

Теперь мы можем ясно видеть, что изменилось:

  • изменение положения комментария в коде;
  • новая логика проверки входных параметров.

Когда использовать гистограммный алгоритм:

  1. Этот алгоритм лучше описывает изменения кода согласно этому недавнему исследованию, проведенному Nugroho et al (2019).
  2. Когда у алгоритма «терпения» возникают проблемы с представлением некоторых сделанных изменений.
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»
Интересно, перейти к каналу

Резюме

Учитывая набор всех возможных изменений в различных типах файлов (например, source-код, YAML, документация), каждый алгоритм сравнения утилиты git diff лучше подходит для определенного подмножества. Хотя алгоритм Майерса по умолчанию работает хорошо в большинстве случаев, бывают случаи, когда изменение может быть лучше представлено с использованием другого подхода.

Я считаю, что существует набор изменений/файлов, где ни один из представленных diff-алгоритмов не будет работать идеально. В таких случаях либо используйте неоптимальный вывод diff, либо смотрите за пределами утилиты git diff.

Литература

[1] Nugroho, Y.S., Hata, H. & Matsumoto, K. How different are different diff algorithms in Git?. Empir Software Eng 25, 790–823 (2020). https://doi.org/10.1007/s10664-019-09772-z

File1
public class File1 {

  public int add (int a, int b)
  {
    log();
    return a + b;
  }

  public int sub (int a, int b)
  {
    if (a == b)
    {
        return 0;
    }
    log();
    return a - b;
    // TODO: JIRA1234
  }
}
File2
public class File1 {

  public int sub (int a, int b)
  {
    // TODO: JIRA1234
    if ( isNull(a, b) )
    {
        return null
    }
    log();
    return a - b;
  }

  public int mul (int a, int b)
  {
    if ( isNull(a, b) )
    {
        return null;
    }
    log();
    return a * b;
  }
}

Переведено: Екатериной Чехрановой


Источники

ВАКАНСИИ

Добавить вакансию
Разработчик C++
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

Библиотека программиста
18 октября 2017

Шпаргалка по Git, в которой представлены основные команды

Git сегодня - это очень популярная система контроля версий. Поэтому шпаргал...
admin
23 февраля 2017

Git за полчаса: руководство для начинающих

В последние годы популярность git демонстрирует взрывной рост. Эта система ...
admin
21 февраля 2017

Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

Данная статья содержит не только самые распространенные алгоритмы и структу...