Git如何知晓文件差异

求两版本之间的差异是一个动态规划问题 git 能发现任何的改动，但它是怎么发现的呢？难道它监控了我们对文件的读写操作？ git 才没这么鸡冻……它是通过比较新旧版本，掐指一算算出来的O（∩_∩）O。首先假设我们只能通过以下3个操作将旧版本演化为新版本：copy —— 复制旧版本当前行到新版本insert —— 在新版本中添加一行delete —— 跳过旧版本当前行那么，如下旧版本（左）到新版本（右）：

122333

1333

可通过方案一：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,++jinsert : ++jdelete : ++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: emp>java Diff src.txt dest.txt
1 1 1
2 - 22
3 2 333E: emp>

GitLab 启用HTTPSGit版本管理的优点相关资讯 Git

Git 2.10 发布- Push、Worktree、（09月21日）
使用Eclipse上传/下载Git项目（05月29日）
Git 2.8.2 发布，源代码管理系统（05月03日）

Git 技能学习总结（08月05日）
Git诞生11年后，BitKeeper宣布开源（05月11日）
Git 联机版注册使用（03月30日）

本文评论查看全部评论（0）