MyException - 我的异常网
当前位置:我的异常网» 研发管理 » git怎么知晓文件差异

git怎么知晓文件差异

www.MyException.Cn  网友分享于:2013-02-20  浏览:2次
git如何知晓文件差异

  求两版本之间的差异是一个动态规划问题

  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

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有