Quel effet l'option «-d» a-t-elle avec diff?

24

L' diffimplémentation sur OpenBSD a une -doption non standard avec la documentation suivante:

-d

Essayez très fort de produire un diff aussi petit que possible. Cela peut consommer beaucoup de puissance de traitement et de mémoire lors du traitement de fichiers volumineux avec de nombreuses modifications.

L' diffimplémentation GNU a la même option avec la documentation plus courte

-d, --minimal

essayez de trouver un plus petit ensemble de changements

De temps en temps, j'ai utilisé cette option juste pour voir si elle génère une sortie qui est sous une forme ou une forme différente de la même diffcommande sans l'option, mais je n'ai jamais vu de différence (sans jeu de mots).

Quelqu'un pourrait-il fournir ou pointer vers un exemple où cette option produit en fait un résultat différent à partir de la même commande sans -d? Alternativement, si quelqu'un pouvait expliquer les circonstances requises pour que cette option entre en jeu. Je ne sais pas non plus si "minimal" signifie "moins de lignes de sortie" ou "moins de mecs".

Une supposition non éduquée est que cela a à voir avec de très gros mecs.

diff Kusalananda
la source
1
unix.stackexchange.com/questions/472528 a piqué votre curiosité, n'est-ce pas? (-:
JdeBP
@JdeBP Oui en effet. Cela m'a rappelé ce drapeau et le fait que je ne sais tout simplement pas ce qu'il fait puisque je ne l'ai jamais vu faire quoi que ce soit.
Kusalananda
1
info diff performancel'explique IIRC
Stéphane Chazelas
1
Clairement lié . Malheureusement, aucun exemple de myers -> résultats minimes.
Isaac
1
J'aimerais vraiment obtenir un exemple qui créerait une sortie différente avec gdiff -dpour vérifier si les ajouts à OpenBSD sont utiles. D'après mes tests, je n'ai pu obtenir aucune différence, mais il est évident que le code OpenBSD ralentit les performances, ce qui semble avoir un impact significatif, car l'algorithme diff de Douglas McIlroy est plus rapide que gdiff tant que vous utilisez des tailles de fichier normales.
schily

Réponses:

15

Dans GNU diff, également utilisé sur FreeBSD, le --minimaldrapeau déclenche une variation d'algorithme de Paul Eggert qui l'amène à "limiter le coût O(N**1.5 log N)au prix de produire une sortie sous-optimale pour de grandes entrées avec des différences". Plus précisément, il l' amène à ne pas appliquer plusieurs heuristiques qui traitent à trouver simplement près des solutions optimales et à jeter « confusion » lignes que les différences supplémentaires.

Dans OpenBSD diff, qui utilise l'ancien diffalgorithme Unix des années 1970, l'algorithme utilisé est attribué à Harold Stone, et l' --minimalindicateur déclenche une recherche qui est (effectivement non) limitée par la valeur maximale d'un entier non signé plutôt que par la racine carrée de la taille de la gamme de lignes à comparer (ou 256 si elle est supérieure).

Lectures complémentaires

JdeBP
la source
1
Lorsque j'ai créé un meilleur diff à partir des sources UNIX, j'ai vérifié cette amélioration d'OpenBSD et je n'ai pas pu trouver de meilleurs résultats. Notez que la fonction d'origine stone () utilise: `} while ((y = b [++ j])> 0);` et BTW: pour les tailles de fichiers normales, mon diff UNIX amélioré est plus rapide que diff GNU.
schily