算法与计算机科学blog.jcoglan.com编辑精选
Myers 差分算法：第一部分
The Myers diff algorithm: part 1
2017 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 James Coglan 的系列教程第一篇，讲解 Myers diff 算法——即 git 等工具背后用于计算文本差异的经典算法。文章从最长公共子序列（LCS）问题入手，逐步推导 Myers 算法的思路。
为什么经久不衰：它把一个看似复杂的经典算法讲得清晰易懂，多年反复登上 HN 首页，至今仍是理解 diff 工具原理的最佳入门读物之一。
HN 评论精选
指出 Myers 并非唯一选择，patience diff 在某些情况下更优
还有 patience diff，在某些场景下效果更好（平时你可能看不到 Myers 算法的劣势，因为差异结果在 LCS 算法之后还会被加工处理）。
zamalek查看英文原文
There's also patience diff[1], which does a better job in some situations[2] (you might not normally see these inferior diffs because the diffs are massaged after the LCS algorithm). [1]: http://alfedenzo.livejournal.com/170301.html [2]: http://bramcohen.livejournal.com/73318.html
补充 LCS 问题的延伸学习资料
顺带一提，维基百科上关于 LCS（最长公共子序列）的页面有更多图示和伪代码：https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
jasode查看英文原文
Fyi... a related wiki page about LCS (Longest Common Subsequence) with more diagrams and pseudocode: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
呼吁基于 AST 的代码感知 diff，吐槽行级 diff 在代码评审中的痛点
我不明白为什么没有更好的、能理解代码的 diff 工具，比如基于 AST 的 diff。当我拆分一个方法或加一个 if 语句时，难道不能检测出大部分代码其实没变、只是被移动了位置吗？这是我在做和提交代码评审时最大的痛点——不得不解释“我知道这显示 5000 行改动，但我真的没改任何逻辑，只是把类移到了子类里，导致缩进变了”。
shaftway查看英文原文
I don't understand why there isn't a better code-aware diff tool available, like an AST diff. When I split a method up, or add an if statement, can't we detect that most of the code didn't change, it was just moved around? This is the biggest frustration to me when doing and sending code reviews, having to explain "I know it's a 5 thousand line change, but I really didn't change any of the logic, I just moved the class into a subclass which caused an indentation change."
说明该算法已被 Elixir 标准库收录，可见其重要性
这个算法已经是 Elixir 标准库的一部分了。
flippant查看英文原文
This is part of the Elixir standard library https://hexdocs.pm/elixir/List.html#myers_difference/2 https://github.com/elixir-lang/elixir/blob/master/lib/elixir/lib/list.ex#L772
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选