Welchen Effekt hat die Option "-d" mit diff?

24

Die diffImplementierung unter OpenBSD bietet eine -dSonderoption mit der folgenden Dokumentation:

-d

Versuchen Sie sehr, ein möglichst kleines Diff zu erzeugen. Dies kann bei der Verarbeitung großer Dateien mit vielen Änderungen viel Rechenleistung und Speicherplatz verbrauchen.

Die GNU- diffImplementierung hat dieselbe Option wie die kürzere Dokumentation

-d, --minimal

bemühen Sie sich, eine kleinere Reihe von Änderungen zu finden

Von Zeit zu Zeit habe ich diese Option verwendet , nur um zu sehen , ob es eine Ausgabe generiert , die in irgendeiner Form anders aus derselben ist diffohne die Option Befehl, aber ich habe nie einen Unterschied (kein Wortspiel beabsichtigt) gesehen.

Könnte jemand ein Beispiel angeben oder auf ein Beispiel verweisen, bei dem diese Option tatsächlich ein anderes Ergebnis als derselbe Befehl erzeugt, ohne das dies der Fall ist -d? Alternativ, wenn jemand die Umstände erläutern könnte, die für das Aktivieren dieser Option erforderlich sind. Ich bin mir auch nicht sicher, ob "minimal" "weniger Ausgabezeilen" oder "weniger Hunks" bedeutet.

Eine ungebildete Vermutung ist, dass es sich um sehr große Kerle handelt.

diff Kusalananda
quelle
1
unix.stackexchange.com/questions/472528 hat Ihre Neugier geweckt, oder? (-:
JdeBP
@JdeBP Ja in der Tat. Es erinnerte mich an diese Flagge und an die Tatsache, dass ich einfach nicht weiß, was sie macht, da ich noch nie gesehen habe, dass sie etwas bewirkt.
Kusalananda
1
info diff performanceerklärt es IIRC
Stéphane Chazelas
1
Klar verwandt . Leider kein Beispiel für myers -> minimale Ergebnisse.
Isaac
1
Ich hätte wirklich gerne ein Beispiel, mit dem ich eine andere Ausgabe erstellen würde, gdiff -dum zu prüfen, ob die Ergänzungen zu OpenBSD nützlich sind. Bei meinen Tests konnte ich keine Unterschiede feststellen, aber es ist offensichtlich, dass der OpenBSD-Code die Leistung verlangsamt, was sich erheblich auswirkt, da der diff-Algorithmus von Douglas McIlroy schneller ist als gdiff, solange Sie normale Dateigrößen verwenden.
Schily

Antworten:

15

In GNU diff, das auch unter FreeBSD verwendet wird, --minimallöst das Flag eine Algorithmusvariante von Paul Eggert aus, die "die Kosten O(N**1.5 log N)auf den Preis für die Erzeugung einer suboptimalen Ausgabe für große Eingaben mit Unterschieden beschränkt". Insbesondere werden dadurch nicht mehrere Heuristiken angewendet, bei denen es darum geht , nur annähernd optimale Lösungen zu finden und "verwirrende" Zeilen als zusätzliche Unterschiede auszublenden.

In OpenBSD diff, das den älteren Unix- diffAlgorithmus aus den 1970er Jahren verwendet, wird der verwendete Algorithmus Harold Stone gutgeschrieben, und das --minimalFlag löst eine Suche aus, die (praktisch) nicht durch die Quadratwurzel, sondern durch den Maximalwert einer vorzeichenlosen Ganzzahl begrenzt ist der Größe des zu vergleichenden Zeilenbereichs (oder 256, falls dieser größer ist).

Weitere Lektüre

JdeBP
quelle
1
Als ich ein besseres Diff aus den UNIX-Quellen erstellt habe, habe ich die OpenBSD-Erweiterung überprüft und konnte keine besseren Ergebnisse finden. Beachten Sie, dass die ursprüngliche stone () -Funktion verwendet: `} while ((y = b [++ j])> 0);` und BTW: Für normale Dateigrößen ist mein erweiterter UNIX-Diff schneller als GNU-Diff.
Schily