Fossil SCM

Improvements to the longest-common-subsequence (LCS) function inside the diff engine.

drh 2013-05-25 01:27 UTC annotate
Commit 477d1150cf95744223fd3cfe33fbbe996bfba486
Parent 1fcc6bda2fd9490…
1 file changed +9 -8
~ src/diff.c
M src/diff.c
+9 -8
--- src/diff.c
+++ src/diff.c
@@ -1653,23 +1653,26 @@
16531653
 int iS1, int iE1, /* Range of lines in p->aFrom[] */
16541654
 int iS2, int iE2, /* Range of lines in p->aTo[] */
16551655
 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
16561656
 int *piSY, int *piEY /* Write p->aTo[] common segment here */
16571657
 ){
1658
- double bestScore = -1e30; /* Best score seen so far */
16591658
 int i, j, k; /* Loop counters */
16601659
 int n; /* Loop limit */
16611660
 DLine *pA, *pB; /* Pointers to lines */
16621661
 int iSX, iSY, iEX, iEY; /* Current match */
1663
- double score; /* Current score */
1664
- int skew; /* How lopsided is the match */
1665
- int dist; /* Distance of match from center */
1662
+ int skew = 0; /* How lopsided is the match */
1663
+ int dist = 0; /* Distance of match from center */
16661664
 int mid; /* Center of the span */
16671665
 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
16681666
 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
1669
-
1667
+ sqlite3_int64 bestScore; /* Best score so far */
1668
+ sqlite3_int64 score; /* Score for current candidate LCS */
1669
+ int span; /* combined width of the input sequences */
16701670
1671
+ span = (iE1 - iS1) + (iE2 - iS2);
1672
+ bestScore = -10000;
1673
+ score = 0;
16711674
 iSXb = iSXp = iS1;
16721675
 iEXb = iEXp = iS1;
16731676
 iSYb = iSYp = iS2;
16741677
 iEYb = iEYp = iS2;
16751678
 mid = (iE1 + iS1)/2;
@@ -1707,11 +1710,11 @@
17071710
 iEY += k;
17081711
 skew = (iSX-iS1) - (iSY-iS2);
17091712
 if( skew<0 ) skew = -skew;
17101713
 dist = (iSX+iEX)/2 - mid;
17111714
 if( dist<0 ) dist = -dist;
1712
- score = (iEX - iSX) - 0.05*skew - 0.05*dist;
1715
+ score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
17131716
 if( score>bestScore ){
17141717
 bestScore = score;
17151718
 iSXb = iSX;
17161719
 iSYb = iSY;
17171720
 iEXb = iEX;
@@ -1731,12 +1734,10 @@
17311734
 *piSX = iSXb;
17321735
 *piSY = iSYb;
17331736
 *piEX = iEXb;
17341737
 *piEY = iEYb;
17351738
 }
1736
- /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n",
1737
- iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */
17381739
 }
17391740
17401741
 /*
17411742
 ** Expand the size of aEdit[] array to hold at least nEdit elements.
17421743
 */
17431744
--- src/diff.c
+++ src/diff.c
@@ -1653,23 +1653,26 @@
1653 int iS1, int iE1, /* Range of lines in p->aFrom[] */
1654 int iS2, int iE2, /* Range of lines in p->aTo[] */
1655 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
1656 int *piSY, int *piEY /* Write p->aTo[] common segment here */
1657 ){
1658 double bestScore = -1e30; /* Best score seen so far */
1659 int i, j, k; /* Loop counters */
1660 int n; /* Loop limit */
1661 DLine *pA, *pB; /* Pointers to lines */
1662 int iSX, iSY, iEX, iEY; /* Current match */
1663 double score; /* Current score */
1664 int skew; /* How lopsided is the match */
1665 int dist; /* Distance of match from center */
1666 int mid; /* Center of the span */
1667 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
1668 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
1669
 
 
1670
 
 
 
1671 iSXb = iSXp = iS1;
1672 iEXb = iEXp = iS1;
1673 iSYb = iSYp = iS2;
1674 iEYb = iEYp = iS2;
1675 mid = (iE1 + iS1)/2;
@@ -1707,11 +1710,11 @@
1707 iEY += k;
1708 skew = (iSX-iS1) - (iSY-iS2);
1709 if( skew<0 ) skew = -skew;
1710 dist = (iSX+iEX)/2 - mid;
1711 if( dist<0 ) dist = -dist;
1712 score = (iEX - iSX) - 0.05*skew - 0.05*dist;
1713 if( score>bestScore ){
1714 bestScore = score;
1715 iSXb = iSX;
1716 iSYb = iSY;
1717 iEXb = iEX;
@@ -1731,12 +1734,10 @@
1731 *piSX = iSXb;
1732 *piSY = iSYb;
1733 *piEX = iEXb;
1734 *piEY = iEYb;
1735 }
1736 /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n",
1737 iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */
1738 }
1739
1740 /*
1741 ** Expand the size of aEdit[] array to hold at least nEdit elements.
1742 */
1743
--- src/diff.c
+++ src/diff.c
@@ -1653,23 +1653,26 @@
1653 int iS1, int iE1, /* Range of lines in p->aFrom[] */
1654 int iS2, int iE2, /* Range of lines in p->aTo[] */
1655 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
1656 int *piSY, int *piEY /* Write p->aTo[] common segment here */
1657 ){
 
1658 int i, j, k; /* Loop counters */
1659 int n; /* Loop limit */
1660 DLine *pA, *pB; /* Pointers to lines */
1661 int iSX, iSY, iEX, iEY; /* Current match */
1662 int skew = 0; /* How lopsided is the match */
1663 int dist = 0; /* Distance of match from center */
 
1664 int mid; /* Center of the span */
1665 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
1666 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
1667 sqlite3_int64 bestScore; /* Best score so far */
1668 sqlite3_int64 score; /* Score for current candidate LCS */
1669 int span; /* combined width of the input sequences */
1670
1671 span = (iE1 - iS1) + (iE2 - iS2);
1672 bestScore = -10000;
1673 score = 0;
1674 iSXb = iSXp = iS1;
1675 iEXb = iEXp = iS1;
1676 iSYb = iSYp = iS2;
1677 iEYb = iEYp = iS2;
1678 mid = (iE1 + iS1)/2;
@@ -1707,11 +1710,11 @@
1710 iEY += k;
1711 skew = (iSX-iS1) - (iSY-iS2);
1712 if( skew<0 ) skew = -skew;
1713 dist = (iSX+iEX)/2 - mid;
1714 if( dist<0 ) dist = -dist;
1715 score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
1716 if( score>bestScore ){
1717 bestScore = score;
1718 iSXb = iSX;
1719 iSYb = iSY;
1720 iEXb = iEX;
@@ -1731,12 +1734,10 @@
1734 *piSX = iSXb;
1735 *piSY = iSYb;
1736 *piEX = iEXb;
1737 *piEY = iEYb;
1738 }
 
 
1739 }
1740
1741 /*
1742 ** Expand the size of aEdit[] array to hold at least nEdit elements.
1743 */
1744

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button