服务器评测求两版本之间的差异是一个动态规划问题
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
