objective-c - git DAG 的增量线性化

我是 GitX 的作者。 GitX 的特性之一是分支的可视化，如 here 所示。

这种可视化目前是通过读取以正确顺序从 git 发出的提交来完成的。对于每次提交， parent 都是已知的，因此以正确的方式建立 channel 相当容易。

我想通过使用我自己的提交池并自己线性化提交来加速这个过程。这允许我重用现有的已加载提交并允许 git 更快地发出提交，因为它不必以正确的顺序发出它们。

但是，我不确定使用什么算法来实现这一点。构建是增量的很重要，因为提交的加载可能需要很长时间(对于 100,000 次提交，> 5 秒，应该全部显示)。

Gitk 也是这样，有一个补丁 here 显示了它是如何实现的，但是我的 TCL 技能很弱，补丁没有很彻底的评论，有点难以理解。

我还希望这个算法高效，因为它必须处理数十万次提交。它也必须显示在表格中，因此快速访问特定行很重要。

我将描述到目前为止的输入、我想要的输出和一些观察结果。

输入:

我有一个哈希表形式的当前提交池，它将提交 ID 映射到提交对象。这个池不必是完整的(有所有必要的提交)

我在来自 git 的新提交中有一个单独的线程加载，每次加载新提交时都可以调用回调。没有保证提交的顺序，但在大多数情况下，下一个提交是前一个提交的父提交。

一个提交对象有它自己的修订 id 及其所有父级的修订 id

我有一个应该列出的分支负责人列表。也就是说，不应该显示 DAG 的单个“顶部”。也不必有单个图根。

输出:

我需要按拓扑顺序线性化这些提交。也就是说，在列出其父项之后不能列出提交。

我还需要可以在上面的屏幕截图中看到的“分支线”。这些可能需要预先计算，因为它们中的大多数取决于他们的 child 。

几点说明:

有必要重新定位提交列表。例如，我们可能不得不提交不相关的(分支头)，直到出现一个使一个头成为另一个头的祖先的提交。

必须显示多个分支提示

这个过程是增量的很重要，以便在数据仍在加载时至少可以使用部分 View 。这意味着必须中途插入新数据并且必须重新调整支线。

最佳答案

标准的 topological sort 是 O(n)(OK，O(V+E))，也就是说，您应该能够在几分之一秒内对内存中的一百万次提交进行排序。不需要像 Tcl 那样的增量 hack。

顺便说一句，我每天都使用 GitX(在 OS X 上看起来比 Gitk 好得多)并且没有任何问题(可能是因为我的存储库中没有那些疯狂的 merge ):)

关于objective-c - git DAG 的增量线性化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/701439/