【CSDN 编者按】说到算法和数据结构每个程序员应该都很了解。近日，从事 AI+ 开发工具工作的 Austin Z. Henley发布了他的第三篇热门帖子，总结道每个程序员都应该尝试具有挑战性的算法和数据结构。

原文链接：https://austinhenley.com/blog/challengingalgorithms.html

作者 | Austin Z. Henley译者 | 禾木木

(资料图)

出品 | CSDN（ID：CSDNnews）

此前，Austin Z. Henley 发布了两篇“每个程序员都应该尝试具有挑战性的项目”。文中列出了每个程序员都应该去尝试的项目，包括文本编辑器、太空入侵者游戏、 BASIC 编译器、一个小型的操作系统、一个电子表格、一个视频游戏控制台模拟器、光线追踪器、键值存储 Web API 、Web 浏览器和股票交易机器人。这两篇文章在网络上爆红，一个月内浏览量超过 10 万次。

继这两篇后，Austin Z. Henley 又发布了他的第三篇内容，在文章中列出了程序员应该尝试的有趣的算法和数据结构：

拓扑序列 递归下降解析 Myers 差分算法 Bloom filter Piece table 伸展树

拓扑序列

拓扑排序简单讲就是在可求拓扑序列的有向无回路图（有向无环图）中求取拓扑序列的排序算法。常见的场景包括确定构建系统的任务顺序、电子表格中单元格的评估顺序、学生每学期毕业应上哪些课，以及各种调度问题。

Austin Z. Henley 曾在 Tennessee 大学任教时使用它来重新排列图表，使其更易于阅读。

拓扑排序：https://en.wikipedia.org/wiki/Topological_sorting 拓扑排序交互式可视化：https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html

递归下降解析

这一次，就像打开了一种超能力！

如果你需要摄取递归数据格式或编写编程语言，这是最适合的工具。轻松地编出语法，并将每个语法规则映射到代码函数中。

感觉就像它自己在编码一样。

你可以在几个小时内用它制作一个简单的编译器。

Teeny Tiny 编译器：https://austinhenley.com/blog/teenytinycompiler2.html 制作翻译：https://amzn.to/3HT015y 递归下降解析器：https://en.wikipedia.org/wiki/Recursive_descent_parser

Myers 差分算法

处理字符串通常是一项非常常见的编程任务，但作者通常是通过暴力强制来解决需要计算的任何问题。程序员们都学过 Levenshtein 距离，但是如果需要以一种合理的方式显示两个字符串之间的差异呢？

其中，Git 用于显示差分的默认算法是 Myers 差分算法。

Myers 差分算法：https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ 代码和交互式可视化：https://blog.robertelder.org/diff-algorithm/

Bloom filter

它实际上只对大规模的问题有帮助，例如当你需要一个非常大的哈希表时，它则是对概率数据结构的一个很好的介绍。在内存很小的情况下，它可以告诉你表中是否存在某个项目，否则它只能告诉该项是否存在。

Bloom filter：https://en.wikipedia.org/wiki/Bloom_filter 操作 Bloom filter：https://onatm.dev/2020/08/10/let-s-implement-a-bloom-filter/ 示例：https://llimllib.github.io/bloomfilter-tutorial/

Piece table

当 Austin Z. Henley 第一次尝试制作文本编辑器时，便将所有文本存储在一个数组中。但这会导致性能问题（例如，当用户在任何地方插入文本而不是结尾时）。几年后，在一次实习面试中被问到如何实现一个高性能文本缓冲区。

他也会考虑该使用什么。有一些不同的方案需要权衡：rope, gap buffer, 或是 piece table。使用 piece table，可以跟踪对文本执行的编辑，而仅仅不是只保留生成的文本。它使许多其他功能变得很简单（例如，撤销支持和增量保存）。

不过，piece table 只对文本编辑器有用。只要有可以任意修改的大数据缓冲区时，就可以使用它。

Piece table：https://en.wikipedia.org/wiki/Piece_table

VS Code 的文本缓冲区：https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation

Piece table：https://darrenburns.net/posts/piece-table/

伸展树

那么自我优化的数据结构怎么样呢？

伸展树是一种二叉树，它倾向于将最近访问的元素靠近根，并且这样做不需要维护任何额外的元数据。每次访问一个元素时，它都会被移动到根目录。

这是一个带有内置缓存的树，实现起来非常简单！

伸展树互动可视化：https://www.cs.usfca.edu/~galles/visualization/SplayTree.html 伸展树：https://en.wikipedia.org/wiki/Splay_tree Type 中的实现：https://github.com/w8r/splay-tree

如果你还知道哪些更有趣的算法或是数据结构，可以在评论区留言呦。

参考链接：

https://austinhenley.com/blog/challengingalgorithms.html

https://austinhenley.com/blog/challengingprojects.html

https://austinhenley.com/blog/morechallengingprojects.html

《2022-2023 中国开发者大调查》重磅启动，欢迎扫描下方二维码，参与问卷调研，更有 iPad 等精美大礼等你拿！

☞ “鸿蒙之父”王成录重申：鸿蒙系统不是安卓套壳；苹果多款产品电池修理费将涨价；Debian移除Python 2|极客头条

☞ Python 最受后端欢迎、中国开发者最爱 Star，揭晓 GitHub 2022 的趋势和见解！

☞年薪 10 万的虚拟人，网友直呼“破防”：工资比我都高啊？

责任编辑：