Какой эффект имеет опция «-d» с diff?

24

diffРеализация на OpenBSD имеет нестандартный -dвариант со следующей документацией:

-d

Старайтесь изо всех сил, чтобы сделать diff как можно меньше. Это может потребовать много вычислительной мощности и памяти при обработке больших файлов со многими изменениями.

Реализация GNU diffимеет ту же опцию с более короткой документацией

-d, --minimal

стараться найти меньший набор изменений

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

Может ли кто-нибудь предоставить или указать на пример, где эта опция на самом деле дает другой результат, чем та же команда без -d? В качестве альтернативы, если кто-то может объяснить обстоятельства, необходимые для включения этой опции. Я также не уверен, означает ли «минимальный» «меньшее количество строк вывода» или «меньшее количество фрагментов».

Необразованное предположение состоит в том, что это связано с очень большими кусками.

diff Кусалананда
источник
1
unix.stackexchange.com/questions/472528 возбудил ваше любопытство, не так ли? (-:
JdeBP
@JdeBP Да, действительно. Это напомнило мне об этом флаге и о том, что я просто не знаю, что он делает, так как никогда не видел, чтобы он что-то делал.
Кусалананда
1
info diff performanceобъясняет это IIRC
Стефан Шазелас
1
Ясно связаны . К сожалению, нет примера Майерса -> минимальные результаты.
Исаак
1
Мне бы очень хотелось получить пример, с помощью которого можно было бы создать другой вывод gdiff -d, чтобы проверить, полезны ли дополнения к OpenBSD. Из моих тестов я не смог получить никаких отличий, но очевидно, что код OpenBSD замедляет производительность, что выглядит как существенное влияние, поскольку алгоритм сравнения от Douglas McIlroy работает быстрее, чем gdiff, если вы используете файлы нормального размера.
Щили

Ответы:

15

В GNU diff, также используемом во FreeBSD, --minimalфлаг запускает вариант алгоритма Пола Эггертта, который заставляет его «ограничить стоимость O(N**1.5 log N)ценой получения неоптимального выхода для больших входов с различиями». Более конкретно, это заставляет его не применять несколько эвристических методов, которые касаются нахождения просто близких к оптимальным решений и отбрасывания «запутанных» линий в качестве дополнительных отличий.

В OpenBSD diff, который использует старую Unix diffалгоритм с 1970 - х лет, алгоритм применяется приписывают к Harold Stone, и флаг инициирует поиск , который (эффективно un-) , ограниченный максимального значение целого числа без знака , а не на квадратном корне размера диапазона сравниваемых линий (или 256, если он больше).--minimal

дальнейшее чтение

JdeBP
источник
1
Когда я создал лучший diff из исходников UNIX, я проверил это улучшение OpenBSD и не смог найти лучших результатов. Обратите внимание, что оригинальная функция stone () использует: `} while ((y = b [++ j])> 0);` и BTW: для нормальных размеров файлов моя улучшенная разность UNIX быстрее, чем разность GNU.
1850 года