简介： 由阿里云云效主办的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的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内置数据结构的性能也是比较高的，部分参赛者使用了TreeSet进行排序，然后通过用subSet方法就能直接获取匹配的前缀字符串数据，该方式比较简单快捷，且代码量较小。
参赛者对本赛题的解法诸多，由于篇幅限制，本文章只展示四位参赛者的代码片段。
该解法通过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/tool/cosy，它作为一款AI开发插件，拥有强大的代码智能补全、代码示例搜索等功能，让开发行云流水般编码，事半功倍地完成开发工作。你可以在IntelliJ IDEA或JetBrains插件市场中搜索Alibaba Cloud AI Coding Assistant或Cosy，使用中如果有任何问题或建议都可以反馈到Github Issues中，我们会认真倾听你的声音。
大赛目前全部关卡开放体验，域名地址：https://code83.ide.aliyun.com/，欢迎你来。
我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
我正在使用ruby1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur
简而言之错误:NOTE:Gem::SourceIndex#add_specisdeprecated,useSpecification.add_spec.Itwillberemovedonorafter2011-11-01.Gem::SourceIndex#add_speccalledfrom/opt/local/lib/ruby/site_ruby/1.8/rubygems/source_index.rb:91./opt/local/lib/ruby/gems/1.8/gems/rails-2.3.8/lib/rails/gem_dependency.rb:275:in`==':und
