9月10日至22日，将举行Yandex.Blitz移动开发竞赛。 注册已经
开放 。 闪电战是到达Yandex的捷径：前五名参与者必须成功通过面试的一部分而不是标准的四部分才能获得工作机会。
在竞赛之际，我们与同事讨论了一些有趣的任务，这些任务立即适用于移动平台和算法。 今天，我们将与哈布雷的读者分享他们的故事。
人们认为，移动应用程序的开发是特殊的，与一般意义上的编程相去甚远，为Android和iOS编写的专家永远不会遇到解决算法密集型任务的工作，将自己局限于连接现成的库，排版屏幕，编写简单的业务逻辑和研究特定平台的错误。 但不是那么简单。
为移动设备创建软件总是充满局限性。 即使在高端设备中，CPU和GPU也不像现代计算机那样功能强大且内存不多。 同时，市场的主要部分是预算更低的智能手机，其硬件甚至更弱。 其所有者尤其受到资源短缺的影响。
如果不使用能够以比二次时间更快的速度处理任务的解决方案，就不可能开发出复杂的竞争项目。 如果用户不喜欢工作速度或应用程序消耗电池电量的方式，可以与竞争对手竞争。
从历史上看，Blitz争夺算法知识以及将解决方案的思想转化为代码的能力。 将于9月举行的闪电战也不例外。 我们尝试使用与Yandex移动开发人员在Android和iOS实际项目中使用的算法相似的算法来选择任务。
加快摘要浏览器的速度
首席开发人员Mikhail Efimov ：
-我做了多功能框-浏览器搜索字符串。 自动填充会在其中起作用-只需输入单词的开头，我们就会提供整个单词。 初始任务可以简化为以下内容：收到输入字符串后，从预定义集中找到所有单词，其中输入字符串作为子字符串出现。 为此，我们使用单词的所有后缀-单词结尾的所有子串。 例如，对于单词“ table”，它将是“ table”和“ tol”。 一个或两个字符的后缀-在这里我们将有“ ol”和“ l”-不考虑在内，因为通过它们，垃圾进入了Sest。
因此，我们得到一个单词，而不是一个单词。 如果它由五个字母组成，则将得到三个，依此类推。此外，例如，您可以构建一个众所周知的数据结构trie，使您可以搜索它们。 但是这种结构有一个缺点-它会占用大量内存空间。
反过来，我们保留了后缀的排序列表-后缀数组。 数组中的元素不是完整的后缀-那么结构将占用过多的内存（二次量），而只是一对指针。 它们中的第一个表示您要使用的单词或短语，第二个-单词或短语中以后缀开头的符号。 这种方法可以节省内存。 我们只有两个指针，两个八个字节的数字，而不是很长的字。
下一个问题是如何存储已经排序的列表。 它可以存储为一个简单的数组-但是很长一段时间后，新条目才会插入其中。 因此，我选择存储“增强型”二进制搜索树-增强型二进制搜索树。 作为关键字，树中的每个节点都包含特定单词的特定后缀，作为“补充”，有关优先级的信息存储在节点中。 您需要做的就是找到与输入的前缀匹配的树节点。 此外，您可以分析此节点和相邻节点，以了解哪些单词可用于发行。
在它们之中，选择具有较高优先级的那些。 从单词的开头开始，后缀的缩进长度会影响优先级。 对于缩进为零的单词，优先级更高-例如，如果用户输入“ st”，则单词“ table”的优先级将比单词“ bridge”高得多。 但原则上，您可以输入这样的字符序列，以使浏览器响应时会建议该单词出现在中间或末尾的单词。 例如，如果没有单词以该序列开头。
在移动Yandex上显示CCTV摄像机
Sergey Kuznetsov，首席开发人员 ：-我们有一种算法可以在地图上显示摄像机。 他的工作时间是二次方，不是很快。 有一个想法是可以不借助任何装饰而对其进行改进。
如果我们谈论问题的陈述，那么我们有很多相机需要显示。 在地图的高比例尺上，它们可能会相交，而且很难看-需要显示一台摄像机，而不要显示许多相交的摄像机。
如果我们将这个问题形式化，它可以归结为以下内容：在平面上，有n个相同的正方形，其边平行于坐标轴，您需要从中选择大量的正方形，以使它们在内部不相交，而所有其他正方形至少相交一个。原始设置的正方形。 最简单的求解算法（当我们选择一个正方形并将其与所有其他正方形相交时）适用于n 2 。 但是，可以使用某种算法在n * log（n）中解决该问题，在文献中将其称为“扫描线”。 如果您不了解这种方法，那么当然可以解决此问题，但是如果您知道，则可以更轻松地解决。 您立即知道该朝哪个方向思考。
移动地图上的摄像头。 如果缩小，则仅剩一个图标
从Sugest浏览器的来源之一获取数据
门户网站后端小组负责人Alexander Yashkin ：-在多功能框浏览器中键入时，会显示一些“繁重”的提示来源。 这样的来源之一就是用户的本地历史记录。 历史提示由历史提供商上传-Chromium提供了一个组件。 多功能框有什么特别之处？ 它应该非常快，在您键入时立即提示，因此源大多是同步的。 当浏览器启动时，提供商将建立过去一周的历史提示的快速索引。 在Chromium中，多功能框的历史索引使用了C ++标准库中的关联容器std :: set和std :: map。 为了将数据存储在此类容器中，通常使用红黑木。
我们的任务是加快多功能框中的历史记录搜索。 从用户的直方图中，我们可以看到历史搜索花费的时间最多，而在速度较慢的计算机上，人们的确遭受了损失。 对于某些人来说，期望值是十分之一秒-当您在多功能框中快速键入字符时，它太长了，甚至会更糟。
我在Chromium的上游进行了几种方法优化。 同时对我们的代码进行了更改。 然后，任务传给了我们的开发人员Denis Yaroshevsky。 他是一位非常热情的开发人员-他对C ++，STL和算法感兴趣。 经过反复讨论后，他提议采取彻底的行动：将std :: set替换为flat_set，将std :: map替换为flat_map。 也就是说，只需更改基本结构。 std :: set和std :: map将它们的元素存储在树的节点中，而flat_set和flat_map实际上是对已排序向量的包装。 平面容器是最流行的容器之一，不属于C ++标准库。 也许在下一个标准中，它们仍然会落入其中。
起初有些不信任：建议的路径似乎太简单了，只是表面上。 为了证明其有效性，我们进行了性能测试：我们取了一位同事的个人资料，从中建立了历史索引并对其进行了流行的查询。 我们选择了10个查询并计算了时间。 Denis向我展示了结果，改进非常明显，我也相信他的想法。
发现的问题并非特定于Yandex.Browser。 它影响了所有基于Chromium的浏览器，因此首先，作为Chromium项目的参与者，我们决定进行上游开发。 但是，在Chromium中，有许多人做出了承诺，而且提出的一些想法是疯狂的。 铬开发商对于每个愿意从外部进行某些更改的人都持谨慎态度。 起初他们不想拿我们的补丁。 他们在此之前建议证明其有效性并编写一个微型设计文档，以便他们可以理解想法，受益并批评该建议。
另外，他们说：一旦需要，编写并添加平面容器的单独实现。 不要在我们的项目中添加任何新库-boost，eastl中已经存在实现。 将扁平容器添加到铬的基本组件中。 这是标准库的一个类似物，铬人们非常担心，因此没有多余的东西进入其中。
Denis Yaroshevsky完成了所有这些工作，花了一些时间写设计文档，在C ++模板中编写了flat_set实现，应用了很多模板魔术，编写了涉及容器功能的测试，创建了另一个综合性能测试-我们无法通过真实的方式发送性能测试同事的个人资料。 Denis与基本和多功能框代码的所有者进行了争论，根据审查结果对代码进行了实质性的重新设计-最终克服了这些障碍，并将代码上传到Chromium。
整个传奇历时六个月。 铬然后写道：“是的，我们的直方图确实改善了10–20％。 太好了，谢谢！” 从他们那里已经通过下游到达浏览器，然后是一个美满的结局。 实际上，在所有平台上的所有配置上，历史索引已大大提高。 在该指标中，扁平容器的优点远胜于缺点。
在上游之后，flat_set和flat_map开始被更频繁地使用-现在在代码中，您可以找到涉及它们的数百个位置。 道德-耐心和辛劳会磨砺一切，并且不仅要为您的代码仔细选择算法，还要精心选择合适的数据结构。
参见图表的左侧。 在2017年初，多功能框的加载时间急剧减少，这恰好是由于过渡到flat_set和flat_map
加快Chromium中的HashMap之一
首席开发人员Oleg Maksimenko ：“目标是在我们的一个子项目中加快常规HTML页面的存储。” 我使用了分析代码的标准方法-我查看了保存过程中哪些代码“很热”。 我遇到一个意想不到的地方。 也就是说，这不是主要逻辑，而只是对HashMap容器的搜索，该搜索应占总时间的一小部分。 相反，确实有很高的成本。
我决定替换现有的实现。 这是Chromium的内部HashMap。 我替换了他，并赢得了几次胜利。 然后我走了一点，并确保这不是Google员工的错误，这不是实现整个HashMap的问题，而是哈希函数。 这是外在的东西。 事实证明，在我们使用的代码中，它们有一个琐碎的哈希，内存中的地址被用作哈希。 也许由于某些功能（例如体积小），这种解决方案适合他们。 也许他们的HashMap并不是一个热点，但是当我们应用此结构时，它成为了我们的热点。 通过简单地用std :: hash替换幼稚和琐碎的哈希函数，我们将速度提高了3-10倍。 结果，对散列存储器的这种吸引力从热点列表中消失了，它开始占据了很小的百分比，正如最初预期的那样。 一切都变得美好而美好。