求两版本之间的差异是一个动态规划问题
git 能发现任何的改动,但它是怎么发现的呢?难道它监控了我们对文件的读写操作? git 才没这么鸡冻……它是通过比较新旧版本,掐指一算算出来的O(∩_∩)O。
首先假设我们只能通过以下3个操作将旧版本演化为新版本:
- copy —— 复制旧版本当前行到新版本
- insert —— 在新版本中添加一行
- delete —— 跳过旧版本当前行
那么,如下旧版本(左)到新版本(右):
1 22 333 |
1 333 |
可通过
- 方案一:copy、delete、copy
- 方案二:delete、delete、delete、insert、insert
演化而来。
旧版本可通过这3个操作演化成任意一个新版本,即使新版本已经面目全非:
假设旧版本有n行,新版本有m行。不管它们每行的内容是什么,总是可以通过 n次delete 和 m次insert 演化出新版本。
但是,由于 1个copy 能顶替 1个insert+1个delete,所以方案一比方案二少两个步骤。而且我们实际进行的操作就是步骤最少的方案一(呵呵,人类是最聪明的O(∩_∩)O)。
现在我们有目标了:怎么得到一个步骤最少的演化方案?为了更清晰地描述演化过程,我们定义两个下标: i(旧版本行号)、j(新版本行号)。演化过程中会改变这两个下标:
- copy : ++i,++j
- insert : ++j
- delete : ++i
定义 minPrice[i][j] 为从位置 (i,j) 演化到(n,m) 的最少步骤数(i,j从0开始);那么,minPrice[0][0] 就是从旧版本演化到新版本的最少步骤数。
求 minPrice 的递归式很容易得出:
如果照这个递归式写一个递归算法,那么递归算法会有很多重叠子问题,例如:
minPrice[0][0]、minPrice[0][1]、minPrice[1][0] 都需要计算 minPrice[1][1]。
因此适合采用动态规划逆向求解。下面我用 java 实现了动态规划版的 Diff:
E:\temp>java Diff src.txt dest.txt 1 1 1 2 - 22 3 2 333 E:\temp>
Diff 的全部源码如下:
import java.io.*; import java.util.*; public class Diff { protected enum Operation { COPY(1), INSERT(1), DELETE(1); /** * 操作的代价 */ private int price; private Operation(int price) { this.price = price; } public int getPrice() { return price; } } /** * 旧版本 */ protected List<String> src; /** * 新版本 */ protected List<String> dest; /** * 最小代价 */ protected int[][] minPrice; /** * 获得最小代价所采取的操作 */ protected Operation[][] ops; /** * 读文本文件为一行一行的字符串 */ protected List<String> readLines(String path) { List<String> ans = new ArrayList<String>(); try { BufferedReader in = new BufferedReader(new FileReader(path)); String line; while ((line = in.readLine()) != null) ans.add(line); in.close(); } catch (FileNotFoundException e) { ans = null; } catch (IOException e) { ans = null; } return ans; } /** * 把新旧版本读入 */ public void readFiles(String srcPath, String destPath) { src = this.readLines(srcPath); dest = this.readLines(destPath); } /** * 判断旧版本第i行和新版本第j行是否相等,<b>利用了哈希值减少不必要的字符串全比较</b> */ protected boolean lineEqual(int i, int j) { String s = src.get(i); String d = dest.get(j); if (s.hashCode() != d.hashCode()) return false; return s.equals(d); } /** * 计算最小代价修改方案(动态规划) */ public void minModifyPrice() { int n = src.size(); int m = dest.size(); int i, j;// 新旧版本下标 minPrice = new int[n + 1][m + 1]; ops = new Operation[n + 1][m + 1]; // 初始化全添加、全删除的行列 for (j = m; j >= 0; j--) { ops[n][j] = Operation.INSERT; minPrice[n][j] = (m - j) * Operation.INSERT.getPrice(); } for (i = n - 1; i >= 0; i--) { ops[i][m] = Operation.DELETE; minPrice[i][m] = (n - i) * Operation.DELETE.getPrice(); } for (i = n - 1; i >= 0; i--) for (j = m - 1; j >= 0; j--) { int insertPrice = Operation.INSERT.getPrice() + minPrice[i][j + 1]; int deletePrice = Operation.DELETE.getPrice() + minPrice[i + 1][j]; int copyPrice = Operation.COPY.getPrice() + minPrice[i + 1][j + 1]; int lower; if (insertPrice < deletePrice) { ops[i][j] = Operation.INSERT; lower = minPrice[i][j] = insertPrice; } else { ops[i][j] = Operation.DELETE; lower = minPrice[i][j] = deletePrice; } if (copyPrice < lower && this.lineEqual(i, j)) { ops[i][j] = Operation.COPY; minPrice[i][j] = copyPrice; } } } /** * 打印结果 */ public void printResult() { int n = src.size(); int m = dest.size(); int i = 0, j = 0;// 新旧版本下标 while (i != n || j != m) { switch (ops[i][j]) { case INSERT: System.out.printf(" %4d + %s\n", j + 1, dest.get(j)); j++; break; case DELETE: System.out.printf("%4d - %s\n", i + 1, src.get(i)); i++; break; case COPY: System.out.printf("%4d %4d %s\n", i + 1, j + 1, dest.get(j)); i++; j++; break; } } } /** * @param args * args[0] 是旧版本路径,<br> * args[1] 是新版本路径 */ public static void main(String[] args) { Diff d = new Diff(); d.readFiles(args[0], args[1]); d.minModifyPrice(); d.printResult(); } }
采用动态规划后,求 minPrice 的复杂度为 O(n^2),一般源文件就几百行的样子,因此,几个毫秒就能算出步骤数最少的修改方案。
git 只要把最佳修改方案中的 insert、delete 操作存储起来,做为被管理的软件大夏的一块砖。但实际上git怎么存储各个版本的,还没研究过o(╯□╰)o