From 6cb79244105be99f3f9e24e89b9a594211b594a9 Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Mon, 7 Sep 2020 08:22:57 +1000 Subject: [PATCH] diff: trim endpoints of search more agressively. When we find a long snake, we significantly reduce the worst-case result (which is "no more snakes ever"). This allows us to trim the end-points of the search-font. If the endpoints have a best-case that is worst than the worst-case when using the new snake, there is no point pursuing them. Previously we only trimmed the ends one step for each step forward. This is unnecessarily cautious. It is better to keep trimming until the best-case at the end reaches the worst-case. This improves one test case about 20%. Signed-off-by: NeilBrown --- diff.c | 24 +++++++++++++++--------- 1 file changed, 15 insertions(+), 9 deletions(-) diff --git a/diff.c b/diff.c index d95bef6..5270682 100644 --- a/diff.c +++ b/diff.c @@ -301,23 +301,29 @@ static int find_common(struct file *a, struct file *b, /* new location if we step up from klo to klo-1*/ x = v[klo].x; y = x - (klo-1); cost = abs((ahi-x)-(bhi-y)); + klo--; if (y <= bhi && cost <= worst) { /* Looks acceptable - step up. */ - v[klo-1] = v[klo]; - klo--; - } else - klo++; + v[klo] = v[klo+1]; + } else do { + klo += 2; + x = v[klo].x; y = x - (klo-1); + cost = abs((ahi-x)-(bhi-y)); + } while (cost > worst); /* new location if we step to the right from khi to khi+1 */ x = v[khi].x+1; y = x - (khi+1); cost = abs((ahi-x)-(bhi-y)); + khi++; if (x <= ahi && cost <= worst) { /* Looks acceptable - step to the right */ - v[khi+1] = v[khi]; - v[khi+1].x++; - khi++; - } else - khi--; + v[khi] = v[khi-1]; + v[khi].x++; + } else do { + khi -= 2; + x = v[khi].x+1; y = x - (khi+1); + cost = abs((ahi-x)-(bhi-y)); + } while (cost > worst); } } -- 2.39.5