1

因此，根据关于版本控制合并的维基百科页面，Darcs 使用补丁交换，Git 在它变基时也是如此。

我很想知道为什么 Git rebase 在某些情况下不像 Darcs 那样花费指数时间？

此页面列出了 Darcs 何时可能发生的一系列案例以及如何尝试解决它们。

4

2 回答 2

2

您可以在我从某处回忆的示例中看到发生了什么：从六行 ABCDEF 开始，在一个分支上在前面插入三行 GGG，然后在前面再插入六行 ABCDEF；在另一个分支上（从第一个补丁/提交）将 C 更改为 C4。现在合并两个分支。

Git 将产生 AB C4 DEFGGGABCDEF；darcs 将更改第二个 C，前提是它的身份跟踪比 Git 的上下文和位置跟踪产生更好的结果。如果“4”是块的初始化代码，Git 的结果是错误的；如果是函数或文件的初始化代码，darcs 是错误的。

正是这种身份跟踪占用了时间。

于 2019-06-08T20:14:58.163 回答
2

我没有使用过 darcs 并且可能在这里偏离了基础，但是通过浏览 Wikipedia 文章，我发现它在这里的声明具有误导性：

补丁交换在 Darcs 中用于合并更改，并且也在 git 中实现（但称为“rebase”）。补丁交换合并意味着改变补丁的顺序（即改变的描述），使它们形成一个线性历史。实际上，当在共同情况的上下文中制作两个补丁时，在合并时，其中一个会被重写，以便看起来是在另一个的上下文中完成的。

Git 既不存储补丁，也不重新排序它们。1 如果愿意，您可以手动重新排序补丁。当您使用将提交（即快照）转换为变更集时，转换本身以最坏情况 O(nd)git rebase的简单方式完成，其中 n 是行数，d 是编辑脚本的长度。（这是作为补丁处理还是作为合并的樱桃选择处理，取决于您选择的变基算法；合并情况往往会使用更多的 CPU 时间，因为它还会查找树范围的重命名操作。）

因此，如果您有 C 总提交，则 a 的最坏情况git rebase -i大约是 O(Cnd)。2 Git 不会为提交尝试任何其他顺序：是否进行任何重新排序取决于您。如果你的 rebase 失败，你可以尝试所有可能的重新排序，这将是提交次数的阶乘函数，但 Git 不会为你这样做。

1如果你git rebase对一组内部有一个或多个合并的提交执行 a，Git 会“展平”它们并消除合并——但它不会尝试很多命令，它只是对整个事情进行一次拓扑遍历。没有人试图变得聪明，这通常会导致可怕的合并冲突，也就是说，这通常是一个坏主意。如果您使用新--rebase-merges标志，Git 将尝试保留合并，但通过重新执行它们来实现。它只是构建了一个相同的拓扑，使用一种迷你脚本语言，然后让您可以根据需要手动编辑它。

2如果涉及重命名检测，则可以检测到重命名的文件数量为 O(n 2 )。Git 尝试通过多种方式限制这一点，包括设置重命名队列的最大长度，当前默认为 4000 个文件。

于 2019-06-08T00:55:57.560 回答