原文：https://matklad.github.io/2023/08/13/role-of-algorithms.html
作者：Alex Kladov
译者：ChatGPT 4 Turbo
这是作为文章的 lobste.rs 评论，所以比平时的编辑质量更差。
让我详细说明一下我在会议中提到的内容： https://matklad.github.io/2023/08/06/fantastic-learning-resources.html
帖子：
“算法”是一项有用的技能，并不是因为你每天都在工作中使用它，而是因为它们训练你在软件工程的特定方面变得更加出色。
具体来说：
首先， 算法训练了无错误编码的技能。算法难且令人沮丧！细微的 off-by-one 在简单测试中可能不重要，但会破坏边界情况。但如果你练习算法，你会在编写正确的小程序这一特定技能上变得更好，我认为这可能是通用的。
为了给出一系列类比：
- 人们进行有氧运动或力量训练，并不是因为他们在现实生活中需要举重。恰恰相反 —— 我们日常生活中的体力活动太少，所以我们需要额外的锻炼来让身体获得全面的健康（这在日常生活中是有帮助的）。
- 你不是通过简单重复来练习复杂技能的。你首先要将其分解成可训练的原子子技能，并在非现实条件下分别钻研每个子技能。编写正确的算法代码是软件工程的一个子技能。
- 当你优化系统时，你不仅仅是反复运行端到端测试直到事情变快。你首先要识别出问题区域，然后编写一个针对性的微基准测试来隔离这个特定的效应，接着你使用更短的事件循环来进行优化。
我仍然记得多年前开始学习算法时学到的两个具体教训：
1、调试复杂代码很难，首先简化，然后再调试。
最初，当我遇到测试失败时，我有点尝试给我的程序添加更多代码来让它通过。后来我意识到这样做毫无进展，然后我改变了我的工作流程，首先尽可能地删除代码，然后再去调查有问题的测试用例（随着时间的推移，这变成了一种技能，即一开始就不写不必要的代码）。
2、单一数据源是好的。
我早期的很多错误都是因为我在两个地方复制了相同的信息，然后它们不同步了。将这个问题内化为单一真理来源解决了这些问题。
如果你已经知道这些，我的课程就没有用了。如果你还不知道它们，它们仍然是无用的，而且很可能会对你产生反弹。这是默会知识——它非常难以用言语传达，通过亲自去做来学习这些东西会更有效。
有点相关，我注意到小规模编程技能和大规模编程技能之间有一个令人惊讶的相关性。你可以用五行代码解决一个问题，或者，如果你努力尝试，用十行代码解决。如果你在小规模问题上始终能提出简洁的解决方案，那么大规模设计很可能也会简单。
我不知道这有多真实，因为我从未尝试去查看一项正式的研究，但从我所见，这看起来非常合理。如果这是真的，那么下一个有趣的问题是：“如果你训练小规模编程技能，它们能转移到大规模编程吗？”。同样，我不知道，但我愿意接受这个帕斯卡的赌注。作为这一点的一个不完美且自利的例证，考虑到两者 https://matklad.github.io/2023/12/21/retry-loop.html 和 https://users.rust-lang.org/t/soft-question-scaling-codebase-50k-loc-500k-loc/104129/10 都是在一个早晨的时间跨度内写成的。
其次， 算法教授关于属性和不变量的知识。一些幸运的人从严格的数学背景中获得这些技能，但算法是一种更容易接触的学习方式，因为一切都非常直观，可以立即测试，并且具有非常短而清晰的反馈循环。
属性和不变量是大多数大型成功系统的基础。大约 90% 的代码只是无关紧要的填充和粘合，如果你有能力看到那 10% 在架构上显著的属性，你可以更快地理解系统。
第三， 算法偶尔在工作中也是有用的！就在上周我们的设计走读会上，我们在头脑风暴一个特定的问题时，我就像
等等，所以这里的问题是我们的解决方案是 O(1) 均摊，但实际上这意味着偶尔会出现 O(N)，这就造成了问题。我想知道我们是否能将均摊工作转移到我们进行实际工作的时候，有点像并发编程中的辅助线程。哦，这实际上听起来像是范围查询问题！是的，我认为那个在俄语中被称为“дерево отрезков”的神秘技巧，在英语中没有模因名称（“monoid tree”是一个好名字，但不为人知）可能会有帮助。是的，这确实解决了均摊问题，这将是 O(log N) 非均摊。
我们可能不会采用那个解决方案，因为对于最终只是一个边角案例来说，那个算法过于复杂了，但在我们选择解决方案之前，详细理解问题空间是很重要的。
请注意算法词汇是如何帮助我思考问题的。在数学（包括算法）中，只有少数几个想法会一次又一次地以不同的形式被应用。当然你需要一定的洞察力，但是，对于大多数简单问题，你实际上需要的只是识别你已经在某处见过的结构的能力。
第四， 与前面的内容相连，这些想法确实形成了一个相互关联的网络，在深层次上支撑了很多东西。因此，如果你在学习编程时确实有非零的纯粹好奇心，算法深深地切入了基础。让我重复上一篇文章中的列表，但是要明确指出与其他事物的联系：
线性搜索
大多数旧的函数式语言中的 assoc 列表就是那样工作的。
二分查找
它实际上无处不在。另外，二分查找虽然有个可爱的名字，但实际上它并不是原始操作。原始操作是
partition_point，一种二分查找的谓词版本。这是你应该作为原语添加到你的语言的标准库中的，而且要以此为基础构建其他一切。此外，这是我们知道复杂度下界的少数情况之一。如果一个算法进行了 k 次二进制比较，它最多只能给出 2 k 个不同的答案。因此，要在 n 个项目中找到插入点，你至少需要 k 个这样的问题：2 k > n。
二次排序
我们在工作中使用它！一些集合通过一个小常数静态绑定，对它们进行二次排序只需要更少的机器代码。我们也有点担心，生产排序算法非常复杂，可能会有微妙的错误，尤其是在较新的语言中。
归并排序
这就是你如何在磁盘上排序数据。这也是 LSM 树的工作原理，LSM 树是你在学校里没有学到的最实用重要的数据结构！而且 k 路归并偶尔也很有用（这是三周前的工作内容）。
堆排序
嗯，这个实际上只对堆有用，但我想内核在需要原地排序，不使用额外内存，并且保证 O(N log N) 时间复杂度时可能会用到它？
二叉堆
二叉堆无处不在！值得注意的是，简单的计时器就是按照到期顺序排列的二叉堆。这也是 Dijkstra 算法和 k 路归并的一部分。
可增长数组
这是所有集合中使用最广泛的一个！你知道吗，增长因子 2 存在一个问题，即在
n次重新分配后的大小比所有之前大小的总和还要大，因此分配器无法重用这部分空间？据说，出于这个原因，增长因子小于 2 更为可取。
双向链表
rust-analyzer 的核心是一个二维双向链表。
二叉查找树
再次强调，rust-analyzer 中的绿树是使用偏移量作为隐式键的二叉搜索树。幺半群树也是二叉搜索树。
AVL 树
好的，这个我实际上不知道有直接的应用！但我记得有两个在小规模编程中 AVL 可能教给我的课程，但它没有。实现所有的“小左旋”、“小右旋”、“大左旋”、“大右旋”时，我挣扎了很多。几年后，我学到了你不应该
left: Tree,
right: Tree,
这会导致代码重复。相反，你应该这样做，然后你可以使用
child_index和child_index ^ 1来抽象左右。几年后，我在维基百科上读到，大旋转实际上是两个小旋转的复合。
实际上，我撒了谎，说我不知道这里的联系。你使用相同的旋转操作来处理伸展树。
红黑树
红黑树是一种 2-3 树，也是一种 B 树。你可能还使用了 jemalloc，它通过 C 宏实现了红黑树。左倾红黑树是一种有趣的变体，有人声称它更简单，但也有人认为它实际上并不简单，因为它不对称，而且破坏了 children 技巧。
B 树
如果你使用 Rust，你可能会用到 B-tree。同样，如果你使用数据库，它存储数据要么在 LSM 中，要么在 B-tree 中。这两种情况都是因为 B-tree 能很好地配合内存层次结构。
伸展树
值得一看，纯粹为了好笑 https://www.link.cs.cmu.edu/splay/tree5.jpg
哈希表
字面上来说，无论是链式版本还是开放寻址版本都被广泛使用。
深度优先搜索
这是我经常需要编码的东西，无论是显式还是隐式。每当你有一个有向无环图（DAG）时，当事物依赖于其他事物时，你总会在某处用到深度优先搜索（DFS）。在 rust-analyzer 中，至少有几个地方用到了 —— 一个在借用检查器中用于某些东西（不知道那是做什么的，只是用
fn dfs搜索了一下）和一个在 crate 图中用来检测循环。
宽度优先搜索
同样，任何类型的探索问题通常用 bfs 来解决。例如，rust-analyzer 使用
bfs进行目录遍历。哪个更好，
bfs还是dfs？为什么不两个都要？看看 rust-analyzer 中的 bdfs： https://github.com/rust-lang/rust-analyzer/blob/2fbe69d117ff8e3ffb9b21c4a564f835158eb67b/crates/hir-expand/src/ast\_id\_map.rs#L195-L222
拓扑排序
再次出现了，每当你处理相互依赖的事物时就会发生。rust-analyzer 有
crates_in_topological_order。
强连通分量
这在每次事物相互依赖时都是必需的，但你也允许循环依赖。我认为我在现实生活中并不需要这个。但是，考虑到 SCC 是你在多项式时间内解决 2-SAT 的方法，似乎了解 3-SAT 中的 3 很重要。
最小生成树
好的，这里真的一片空白！与排序、不相交集合并查集（在类型检查器中用于统一）以及二叉堆有关。看起来是一个实际上很重要的算法！啊，最小生成树（MST）我认为也为平面旅行推销员问题提供了一个近似解，这是困难和简单问题之间的另一个分界线。
Dijkstra
Dijkstra 是我想象中的柏拉图式算法，虽然我不认为我实际使用过它？与堆有关。
你知道我们为什么使用
i、j、k作为循环索引吗？因为D ijk stra！
弗洛伊德-沃舍尔
这个很酷！大家都知道为什么任何正则表达式都可以编译成等价的有限状态机。很少有人知道反过来为什么每个自动机都有一个等价的正则表达式（很多人知道这个事实，但很少有人理解为什么）。嗯，因为弗洛伊德-沃尔萨尔！要将自动机转换为正则表达式，使用你用来在图中找到成对距离的同一个算法。
此外，这是动态规划的最终 Boss。如果你理解了这个算法为什么有效，你就理解了动态规划。尽管理解起来有点棘手，但实现起来非常简单！我在尝试实现一个不同的、错误的方法时，偶然遇到了 Floyd-Warshall，我制造了一个错误，这个错误将我错误的算法变成了一个正确的 Floyd-Warshall。
Bellman-Ford
再次强调，这里没有太多实际应用，但理论联系紧密。所有最短路径算法实际上都是固定点迭代！但是在 Bellman-Ford 算法中，它的显式边松弛操作最为明显。下次当你翻开静态分析教材，学习固定点迭代时，试着将其映射到寻找最短路径的问题上！
二次子字符串搜索
这就是你的语言标准库所做的。
Rabin-Karp
一个出色的哈希应用。同一个想法，
hash(composite) = compbine(hash(component)*), 用于在 rust-analyzer 中对语法树进行内部化处理。
Boyer-Moore
这是一个既美观又实用的算法，它可能处理了大部分现实世界中的搜索需求（也就是说，它可能是普通人使用
ripgrep时最热门的部分）。令人高兴的是，这个算法的速度比理论上的可能还要快 —— 它甚至不需要查看每一个输入数据的字节！
Knuth-Morris-Pratt
又一个“这是你如何在现实世界中进行字符串搜索”的算法。它也是有限状态机的柏拉图理想形态，几乎所有东西都是 FSM。它也是 Aho-Corasick。
Aho-Corasick
这与 Knuth-Morris-Pratt 相同，但也教你了解 trie。同样，对于字符串搜索非常有用。由于它是一个 FSM，而正则表达式也是一个 FSM，并且有一个构建两个 FSM 乘积的通用构造，你可以使用它来实现模糊搜索。rust-analyzer 中的“工作区符号”功能就是这样工作的。以下是实现的一部分。
编辑距离
在生物信息学的各个地方（不是实际的编辑距离，而是这个问题的形状）。这个博客的第一篇文章就是关于这个问题：
https://matklad.github.io/2017/03/12/min-of-three.html
它与算法无关，而是关于 CPU 级别的并行性。