Qual o efeito da opção "-d" no diff?

24

A diffimplementação no OpenBSD possui uma -dopção não padrão com a seguinte documentação:

-d

Tente muito produzir um diff o menor possível. Isso pode consumir muito poder de processamento e memória ao processar arquivos grandes com muitas alterações.

A diffimplementação GNU tem a mesma opção com a documentação mais curta

-d, --minimal

tente encontrar um conjunto menor de alterações

De tempos em tempos, usei essa opção apenas para ver se ela gera uma saída de qualquer forma ou forma diferente do mesmo diffcomando sem a opção, mas nunca vi nenhuma diferença (sem trocadilhos).

Alguém poderia fornecer ou apontar para um exemplo em que essa opção realmente produz um resultado diferente do mesmo comando sem -d? Como alternativa, se alguém puder explicar as circunstâncias necessárias para essa opção entrar em ação. Também não tenho certeza se "mínimo" significa "menos linhas de saída" ou "menos trechos".

Um palpite sem instrução é que isso tem a ver com grandes pedaços.

Kusalananda
fonte
11
unix.stackexchange.com/questions/472528 despertou sua curiosidade, não é? (-:
JdeBP 01/10/1918
@JdeBP Sim, de fato. Isso me lembrou essa bandeira e o fato de que simplesmente não sei o que faz, pois nunca a vi fazer nada.
Kusalananda
11
info diff performanceexplica
IIRC
11
Claramente relacionado . Infelizmente, nenhum exemplo de myers -> resultados mínimos.
Isaac
11
Eu realmente gostaria de obter um exemplo que criaria uma saída diferente gdiff -dpara verificar se as adições ao OpenBSD são úteis. Nos meus testes, não consegui nenhuma diferença, mas é óbvio que o código do OpenBSD diminui o desempenho, o que parece ter um impacto significativo, pois o algoritmo diff de Douglas McIlroy é mais rápido que o gdiff, desde que você use tamanhos de arquivo normais.
schily

Respostas:

15

No GNU diff, também usado no FreeBSD, a --minimalflag aciona uma variação do algoritmo de Paul Eggert que faz com que "limite o custo ao O(N**1.5 log N)preço de produzir uma saída subótima para grandes entradas com diferenças". Mais especificamente, faz com que não aplique várias heurísticas que tratam de encontrar soluções meramente próximas das ótimas e de lançar linhas "confusas" como diferenças extras.

No OpenBSD diff, que usa o diffalgoritmo Unix mais antigo da década de 1970, o algoritmo empregado é creditado a Harold Stone, e a --minimalflag aciona uma pesquisa que é (efetivamente des-) limitada pelo valor máximo de um número inteiro não assinado em vez da raiz quadrada do tamanho do intervalo de linhas que está sendo comparado (ou 256, se for maior).

Leitura adicional

JdeBP
fonte
11
Quando criei um diff melhor a partir das fontes UNIX, verifiquei o aprimoramento do OpenBSD e não consegui encontrar melhores resultados. Observe que a função stone () original usa: `} while ((y = b [++ j])> 0);` e BTW: para tamanhos de arquivo normais, meu diff UNIX aprimorado é mais rápido que o diff GNU.
schily