共计 2749 个字符，预计需要花费 7 分钟才能阅读完成。
简介：由阿里云云效主办的 2021 年第 3 届 83 行代码挑战赛曾经收官。超 2 万人围观，近 4000 人参赛，85 个团队组团来战。大赛采纳游戏闯关玩儿法，交融元宇宙科幻和剧本杀元素，让一众开发者玩得不可开交。
其中大赛第二题，号称魔鬼算法题，拦住诸多代码好汉。
咱们请来了第二题的出题人，刘力华（阿里云云效代码平台），为大家零碎揭秘，从设计到攻略，还有优良代码解析供大家参考。
赛题设计
我设计的第二关是心愿能考查参赛者的根底算法、数据结构的能力。
设计起源
本赛题采纳的是字符串前缀匹配算法，参数者须要先通过 OSS 获取待匹配的数据集，而后参赛者须要从中找出与指定前缀字符串相匹配的字符串数据。为什么会抉择该算法呢？源于近期我在应用咱们本人的开发插件时，它可能当我在代码搜寻的输入框中输出 Java API 关键词时，能够主动提供 API 名称的补全提醒，受该功能模块启发，因而心愿设计一个题目让参赛者实现一个 Java API 名称的前缀匹配算法。
此处打个广告：咱们的插件是阿里云智能编码插件，现已上架 JetBrains 插件市场，能够在 IntelliJ IDEA 中通过搜寻 Alibaba Cloud AI Coding Assistant 下载应用。插件蕴含了代码智能补全及代码示例搜寻性能，让开发者更疾速、行云流水的实现编码。
整个赛题的设计难点在于如何让本赛题具备肯定的挑战性。但又保障肯定的通关率。该赛题在内部题库有相似的算法题，属于中等难度，所以中等难度能进步肯定的通过率。为了防止参赛者通过 Java 的 String.startsWith 及双循环就间接通过，所以增大了评测的数据量，然而为了管制赛题难度，评测的数据集分为几十万的小数据集以及几百万的大数据集，只有能较好的解决小数据集问题，就能通过该赛题。
评分零碎
本赛题的打分零碎基于函数计算设计，零碎会随机抉择一个小规模数据集和一个大规模数据集，并顺次串行运行参赛者的代码，并针对这两个数据集对参赛者编写的代码从准确性、性能开销、内存耗费维度进行评估。
赛题攻略
OSS 数据获取
本赛题的数据集存储在 OSS 中，所以须要参赛者通过 OSS 的 SDK 进行数据的获取，参赛者能够通过代码正文中的文档链接去学习 OSS SDK 如何应用，也能够通过近期公布的阿里云智能编码插件（Cosy）疾速查看 OSS SDK 的示例代码。
如上图所示，如果参赛者想晓得 OSSObject 的数据如何获取，能够在该 API 上右键点击“查看代码示例”，智能编码插件就能疾速查找出实现 OSS 数据获取相干的代码示例，参赛者只须要选择性复制并批改局部代码即可。
此外，开发者也能通过代码智能补全性能，通过抉择整行的代码补全后果，疾速的编写出获取 OSS 数据的代码，如下图所示。
算法攻略
该赛题的解题办法是比拟多样化的，参赛者采纳的办法次要分为以下几种。
第一种：本人实现算法及数据结构
赛题攻略中提到了 Trie Tree，一个较为根底的数据结构，一个较好的 Trie Tree 也可能通关本赛题。然而 Trie Tree 的性能开销及内存耗费也都是比拟大的，能够思考 Trie Tree 的诸多变种，比方 Double Array Trie，用双数组去节俭空间，比方 Radix Tree 及其诸多变种，通过缩小树的深度去压缩 Trie Tree 的内存占用。为了比照各种 Trie Tree 实现的成果，这里援用《MergedTrie: Efficient textual indexing》论文的相干评测数据。
还有很多参赛者通过缩小双层循环的次数、缩小前缀匹配的性能开销等办法，也同样取得了较高的分数。
第二种，应用 JDK 内置的数据结构
JDK 内置数据结构的性能也是比拟高的，局部参赛者应用了 TreeSet 进行排序，而后通过用 subSet 办法就能间接获取匹配的前缀字符串数据，该形式比较简单快捷，且代码量较小。
参赛代码 SHOW
参赛者对本赛题的解法诸多，因为篇幅限度，本文章只展现四位参赛者的代码片段。
参赛者代码片段一
该解法通过 String.substring 办法去截取字符串不同长度的前缀，并将截取的前缀间接从 result 的 Map 中进行查找，该办法无需像 String.startsWith 逐个进行字符的比拟，所以效率会有较大晋升，应用这种解法的参赛者比拟多，还有局部参赛者会对截取的长度进行限度，比方当时统计前缀字符串的最短及最长的长度，只需遍历生成该长度范畴内的前缀即可。
参赛者代码片段二
该解法会先排除超出前缀字符串最短及最长长度范畴的数据，而后对数据集进行排序。随后遍历待匹配的前缀字符串列表，为每个前缀字符串通过二分查找计算数据集中，与其匹配地位的数组上界及下界，而后将该范畴内的数据抽取进去即可。
参赛者代码片段三
该解法与排序办法相似，应用了 JDK 内置的 TreeSet 进行排序，而后通过 TreeSet.subSet 办法截取与前缀字符串匹配的数据。
局部参赛者为了进步挑战性，放弃应用 TreeSet，本人实现了相干的排序及查找办法
参赛者代码片段四
这是排名第一的参赛者的代码，该参赛者对 Trie 树进行了优化，应用 CharNode、ArrayNode 缩小局部存储耗费，其中 ArrayNode 中通过 shift 存储偏移量，数组的下标地位加上 shift 偏移量即为字符的 ASCII 码。
并且该参赛者在输入数据时没有将字符串存储到字符串数组中，而是定义了 ByteBuf，在输入时间接以 JSON 字符串模式存储到字节数组中。
总结
只管很多参赛者在这一关遇到了较多艰难，尤其是在解决大规模数据集时。但正因为如此，咱们也发现很多选手并不止步于通关，他们会致力尝试不同的解法、一直地优化算法，哪怕只是晋升了 0.01 分，这一点对咱们团队的触动也是很大的。赛事后咱们也反思了一些做得不够好的中央，比方 IDE 评分栏短少内存耗费、性能开销等具体数字的展现，导致局部参赛者不晓得理论的内存耗费，后续咱们会对这些细节点上进行优化，如果大家有好的想法及倡议，欢送反馈给咱们！
看完攻略如果你还想体验赛题，仍然能够返回 https://code83.ide.aliyun.com，咱们目前依然凋谢给大家进行体验。
最初，欢送大家试用智能编码插件：https://developer.aliyun.com/…，它作为一款 AI 开发插件，领有弱小的代码智能补全、代码示例搜寻等性能，让开发行云流水般编码，事倍功半地实现开发工作。你能够在 IntelliJ IDEA 或 JetBrains 插件市场中搜寻 Alibaba Cloud AI Coding Assistant 或 Cosy，应用中如果有任何问题或倡议都能够反馈到 Github Issues 中，咱们会认真聆听你的声音。
大赛目前全副关卡凋谢体验，域名地址：https://code83.ide.aliyun.com/，欢送你来。
