【CSDN 萨德基】说到演算法和计算机程序每一开发人员如果都很介绍。日前，专门从事 AI+ 应用软件组织工作的 Austin Z. Henley 正式发布了他的第二篇炙手可热回帖，归纳道每一开发人员都如果试著具备诱惑力的演算法和计算机程序。
书名镜像：https://austinhenley.com/blog/challengingalgorithms.html
译者 | Austin Z. Henley 翻译者 | 天山山脉木
公司出品 | CSDN（ID：CSDNnews）
在此之前，Austin Z. Henley 正式发布了三篇 ” 每一开发人员都如果试著具备诱惑力的工程项目 “。该文列举了每一开发人员都如果去试著的工程项目，主要包括文本编辑器、外太空侵略者格斗游戏、 BASIC C++、两个较大型的作业控制系统、两个表单、两个音频格斗游戏控制面板工具包、强光追踪器、数组储存 Web API 、Web 应用程序和证券交易机器。这三篇该文在互联网上走红，两个月内下载量少于 10 亿次。
继这三篇后，Austin Z. Henley 又正式发布了他的第二篇文本，在该该文列举了开发人员如果试著的有意思的演算法和计算机程序：
流形字符串
递回上升导出
Myers 脉冲响应演算法
Bloom filter
Piece table
延展树
流形字符串
流形次序单纯讲是在Haon流形字符串的有向无电路图（有向无尖点）中求得流形字符串的次序演算法。常用的情景主要包括确认构筑控制系统的各项任务次序、表单中常量的评估次序、小学生每学年大学毕业应上什么样课，和各式各样运维难题。
Austin Z. Henley 曾在 Tennessee 大学任教时使用它来重新排列图表，使其更易于阅读。
流形次序：https://en.wikipedia.org/wiki/Topological_sorting
流形次序交互式可视化：https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html
递回上升导出
这一次，就像打开了一种超能力！
如果你需要摄取递回数据格式或编写编程语言，这是最适合的工具。轻松地编出语法，并将每一语法规则映射到代码函数中。
感觉就像它自己在编码一样。
你可以在几个小时内用它制作两个单纯的C++。
Teeny Tiny C++：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）可以用于检索两个元素是否在两个集合中。它的优点是空间效率和查询时间都比一般的演算法要好的多，缺点是有一定的误识别率和删除困难。
它实际上只对大规模的难题有帮助，例如当你需要两个非常大的哈希表时，它则是对概率计算机程序的两个很好的介绍。在内存很小的情况下，它可以告诉你表中是否存在某个工程项目，否则它只能告诉该项是否存在。
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
TypeScript 中的实现：https://github.com/w8r/splay-tree
如果你还知道什么样更有意思的演算法或是数据结构，可以在评论区留言呦。
参考镜像：
https://austinhenley.com/blog/challengingalgorithms.html
https://austinhenley.com/blog/challengingprojects.html
https://austinhenley.com/blog/morechallengingprojects.html
