Sift / a diff bench that never leaves the page
Two versions in, one difference out. Myers' algorithm, written from the paper, running in
this tab. Nothing is uploaded, nothing is stored, and closing the tab is the delete button.
Before 0 lines
After 0 lines
Keys: Ctrl+Enter re-runs, Ctrl+U toggles
unified, Ctrl+Shift+C copies the patch. Folded
stretches expand on click. D is the edit distance, the number of single line
insertions and deletions in the shortest script; LCS is how many lines the two
texts have in common, in order. The two always satisfy
D = before + after - 2 x LCS, which is how the checker grades this engine
against a completely different one.
One measured thing worth knowing, because it is the opposite of what the folklore says.
Real differs run a compaction pass afterwards to push each block of changes as low as it
will legally go, on the grounds that a shortest edit script does not care where the block
sits. This search already puts it there: over 400 generated cases and 12 hand built ones,
sliding found nothing to move. The snake eats matching lines before any edit is charged,
and the tie-break leans toward consuming the old text, and between them the block lands
as late as it can.