<tl;dr>
在源代码版本控制 diff 补丁生成中，是否值得<optimizations>在我的 diff 的 Ruby 实现中使用本文最底部列出的优化（参见 参考资料）来制作 diff 补丁？
</tl;dr>
<introduction>
我正在编程我以前从未做过的事情，并且可能已经有工具可以做我正在编程的确切事情，但在这一点上，我有太多的乐趣在乎，所以我仍然会从头开始做，即使有一个工具可以做到这一点。
所以无论如何，我正在开发一个 Ruby on Rails 应用程序并且需要一个特定的功能。基本上，我希望我的表中的每个条目，例如一个视频游戏表，都有一个存储的文本块，代表该表条目的评论或类似的东西。但是，我希望任何注册用户都可以编辑此文本，并在版本控制系统中跟踪不同的提交。我能想到的最简单的解决方案就是实现一个解决方案，将文本主体和不同版本文本主体的差异补丁历史记录为 Ruby 中的对象，然后将其序列化，最好以人类可读的形式（所以我会最有可能为此使用 YAML）进行编辑，如果由于软件错误损坏或管理员在进行某些版本编辑时出错而需要进行编辑。
所以一开始我只是试着深入研究这个特性，发现生成差异补丁的问题比我认为要有效地完成要困难得多。所以我做了一些研究，并遇到了一些想法。有些我已经实现了，有些我还没有。然而，这几乎都是围绕最长公共子序列问题展开的，因为您已经知道您是否已经使用 diff 或类似 diff 的特征做了任何事情，并优化了解决它的函数。
目前我有它，所以它会从头到尾截断文本正文的比较版本，直到找到不匹配的行。然后它使用比较矩阵解决了这个问题，但是当它找到匹配行时，它不会像在我见过的大多数最长常见子序列算法的例子中那样增加存储在单元格中的值，而是在我有一条不匹配的行时增加，所以至于计算编辑距离而不是最长公共子序列。尽管据我所知，这两种方法本质上是同一枚硬币的两个面，因此任何一种都可以用来得出答案。然后，它通过比较矩阵回溯并记录何时有增量以及在哪个相邻单元格（西部、西北或北部）中确定该行的差异条目，并假设所有其他行保持不变。
通常我会把它留在那里，但由于这是进入 Rails 环境而不仅仅是一些独立的 Ruby 脚本，我开始担心需要至少进行足够的优化，所以如果垃圾邮件发送者以某种方式知道我是如何实现该版本的控制系统，并且知道我最坏的情况条目仍然无法击中服务器那么糟糕。通过互联网搜索和阅读研究论文和文章后，我遇到了一些看起来不错但似乎各有利弊的文章，我很难决定在这种情况下如何平衡利弊出去。那么这里列出的那些值得吗？我列出了它们已知的优缺点。
</introduction>
<optimizations>
通过将未更改的行拆分，然后在每个部分的开头和末尾截断未更改的行的每个部分，将比较的序列切成多个子序列。然后求解每个子序列的编辑距离。
优点：随着变化区域的增大，时间增加从二次增加变为更类似于线性增加。
缺点：弄清楚在哪里分割似乎你必须解决编辑距离，但现在你不在乎它是如何改变的。如果这可以通过更接近于解决汉明距离的过程来解决，那会很好，但是单次插入就会把它扔掉。
使用加密哈希函数将所有序列元素转换为整数并确保唯一性。然后解决比较哈希整数而不是序列元素本身的编辑距离。
优点：比较两个整数的操作比比较两个字符串的操作要快，因此每次比较后都会获得轻微的性能提升，总体上可以很多。
缺点：使用加密哈希函数需要时间来转换所有序列元素，并且最终可能会花费更多时间来进行从整数比较中获得的转换。您可以对字符串使用内置的哈希函数，但这不能保证唯一性。
使用惰性求值只计算比较矩阵最中心的三个对角线，然后只根据需要计算额外的对角线。然后也使用这种方法可能消除一些比较的需要，以比较所有三个相邻的单元格，如此处所述。
优点：可以转动一个总是花费 O(n * m) 时间的算法，并使其只有最坏的情况是那个时间，最好的情况实际上是线性的，而平均情况介于两者之间。
缺点：这是一种我只见过用函数式编程语言实现的算法，我很难理解如何根据上面链接的站点上的描述将其转换为 Ruby。
制作一个 C 模块并在 C 的本机级别完成艰苦的工作，然后为它制作一个 Ruby 包装器，以便 Ruby 可以对其进行所有需要的调用。
Pro：我不得不想象评估这样的事情可能会快很多。
缺点：我不知道 Rails 如何处理带有 C 扩展的 ruby 代码的应用程序，这会损害应用程序的可移植性。
这是解决编辑距离后的优化，但想法是存储额外的组合差异与每个版本产生的差异，以制作一个增量树数据结构，其中最近制作的差异作为树的根节点，因此得到到任何版本都需要 O(log n) 而不是 O(n) 的最坏情况时间。
优点：会更快地回到旧版本。
缺点：这意味着每次新的提交，delta-tree 都会获得一个新的根节点，这将花费时间来重新组织 delta-tree 以执行比返回一个版本更频繁的操作，更不用说不太可能是旧版本。
</optimizations>
那么这些东西值得努力吗？