江苏龙网

  1. 首页 > 人文 > >

「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要

作者：GergelyOrosz
机器之心编译
参与：小舟、杜伟
数据结构和基础算法作为计算机科学的必学课程 ， 近几年却关注度越来越少 。 但程序员真的不再需要这两门基础知识了吗？一位在Uber等科技公司工作过的开发者分享了他的一手经验 ， 告诉你实际工作中会用到哪些数据结构和算法 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
日常工作中 ， 你经常使用算法和数据结构吗？曾就职于Uber等科技公司的工程师GergelyOrosz提出了这样一个问题 。 此外 ， 他也注意到 ， 越来越多的人觉得算法是无用的 ， 并认为它们只是科技公司提出的一种强制性措施罢了 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
本文作者GergelyOrosz 。
不仅如此 ， 也有更多的人抱怨称算法只是纯粹的学术练习 。 在Homebrew作者MaxHowell发表他的谷歌面试经历之后 ， 这样的想法被进一步普及 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
虽然GergelyOrosz自己也从来不需要使用二叉树翻转（binarytreeinversion） ， 但是他在Skype、Microsoft、Skyscanner以及Uber工作时 ， 每天都会遇到使用数据结构和算法的情况 。
此外 ， 他有时也需要基于这些概念编写代码和做出决策 。 最后 ， GergelyOrosz借助这些知识来理解有些事物如何和为何构建 ， 以及如何使用或修改它们 。
由此可见 ， 数据结构和算法并不是如人们所言用处不大 。 在本文中 ， GergelyOrosz列举了一系列现实世界的实例 ， 包含生产中会用到的树、图等数据结构和各种算法 。
值得肯定的 ， 所有这些都出自他的第一手经验 ， 借此希望表达他的观点 ， 即通用数据结构和算法知识并不只是「为了面试」 ， 而是你在快速成长的创新型科技公司工作时 ， 可能会经常遇到的东西 。
GergelyOrosz表示自己曾经用过非常小的算法子集 ， 但几乎包含了所有的数据结构 。 毫不奇怪 ， 他不喜欢繁琐的算法以及包含红黑树或AVL树等不常见数据类型的不切实际的面试问题 。
【「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要】接下来具体来看作者列举出来的实例 ， 以第一人称的口吻进行讲述 。
树和树遍历：Skype、Uber和UI框架
在微软时 ， 当我们构建XboxOne游戏机（由微软发布）的Skype软件时 ， 我们使用的是内置操作系统XboxOS ， 但缺少关键库 。 我们当时正在该平台上构建首个成熟的应用程序之一 ， 所以需要一个能够结合触摸手势和语音命令的导航解决方案 。
我们在微软WinJS库上构建了一个通用的导航框架 。 为了做到这一点 ， 我们需要维护一个类似于DOM（文档对象模型）的图来跟踪可操作的元素 。 为了找出这些元素 ， 我们执行了DOM遍历 ， 基本上是现有DOM上的B-树遍历（B-treetraversal） 。 这便是BFS（广度优先搜索）或者DFS（深度优先搜索）的经典示例 。
在Uber时 ， 团队构建了很多实现节点、依赖关系以及它们之间连接可视化的工具 。 有一个例子就是RIB节点的可视化工具 。 该可视化工具需要维护一棵树 ， 将它可视化为可缩放矢量图形（SVG） ， 然后更新这棵树 ， 同时移动设备上的RIB树也发生变化 。 RIB自己也会为状态管理维护一个逻辑树结构（logicaltreestructure） ， 但这个树结构与呈现对象不同 ， 这就是他们设计背后的关键所在 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
RIB树可视化：一个使用树来表示数据并将其可视化的经典示例 。
权重图和最短路径：Skyscanner
Skyscanner会找到最佳机票 。 为此 ， 它扫描了全球所有的航线 ， 并将它们汇聚在一起 。 由于航空公司需要考虑中转站的选择 ， 所以问题的本质更多地体现在爬虫 ， 而不是缓存 。 多城市规划选项（multi-cityplanningoption）成为了最短路径问题 。
多城市是Skyscanner花费大量时间来构建的功能之一 。 公平地说 ， 产品方面的困难是最多的 。 最佳的多城市航线选择就是使用Dijkstra或者A*这样的最短路径算法计算的 。
航线用一张有向图来表示 ， 每条边都有一个表示票价的权重 ， 算出两个城市之间票价最便宜的航线就是通过每条航线的改进版的A*搜索算法实现的 。
但是使用Skyscanner ， 实际算法就不那么重要了 。 缓存、爬虫和处理各种网站负载比解决问题本身要难得多 。 即便如此 ， 最短路径问题的变体还是在许多基于组合优化价格的旅行公司中使用 。
排序：Skype
对于排序这种算法 ， 我很少需要自己实现或深入使用 。 理解不同类型的排序方法是件很有趣的事 ， 包括冒泡排序、插入排序、归并排序、选择排序以及最复杂的快速排序 。 但是 ， 我还是很少需要自己手动实现这些算法 ， 甚至从来没有把排序函数作为库的一部分来编写 。
在微软Skype时 ， 我练习了这方面的知识 。 另有一位工程师决定为联系人列表实现插入排序算法 。 2013年 ， Skype实现了联网 ， 网络用户呈爆炸式增长 ， 而且用户数还在持续增长 。 因此这位工程师认为用插入排序按照用户姓名来构建联系人列表 ， 性能会更佳 。
关于为什么不单单使用默认排序算法这一问题 ， 我们也经过了反复讨论 。 最后结论是 ， 使用默认排序算法需要对实现进行适当的测试和相应基准测试 ， 这可能需要更多的工作 。 我个人认为这样做没有多大意义 ， 并且当时我们正处在项目阶段 ， 有很多时间 ， 所以采用了基于联系人列表的插入排序算法 。
在现实世界中 ， 一定有一些情况 ， 使用高效的排序算法非常重要 ， 并且基于数据选择使用的排序算法会更加有效 。 在执行大规模实时数据流并且为这些数据源构建实时可视化时 ， 插入排序很有用 。
如果涉及到存储在不同节点上的大量数据 ， 那么「分而治之」的归并排序算法比较合适 。 我自己没有使用过这些算法 ， 因此了解这几种不同的算法之外 ， 我仍然会标记一些自己没有用过的排序算法 。
哈希表和哈希：随处常见
我最常用到的数据结构就是哈希表以及哈希函数了 。 从计数、重复检测、缓存到分片（sharding）之类的分布式系统用例 ， 都会用到这种很方便的工具 。
除了数组之外 ， 在很多情况下用哈希表和哈希函数都是非常合适的 。 几乎每种语言都会用到这种数据结构 ， 而且它的实现很简单 。
栈和队列：偶尔用到
任何调试过具有堆栈追踪的语言的人都非常熟悉这种数据结构 。 我在使用这种数据结构时遇到了一些问题 ， 但调试和性能分析让我慢慢熟悉了它 。
我很少在自己的代码中使用队列这种数据结构 ， 但却在代码库、代码pop和push中遇到过很多次 。 对于分析和配置builds的安装瓶颈检测器工具而言 ， 我会使用Python堆队列（heapqueue）算法来读优先队列优化后的代码 。
加密算法：Uber
Uber很早就使用了几种语言和技术 ， 并且加密（cryptography）并不能实现我们需要的稳定性 。 典型的示例就是iOS和安卓 。 来自客户端用户输入的敏感信息在通过网络发送之前需要加密 ， 同时仅针对特定服务进行解密 。
在某些情况下 ， 我们必须自己构建加密/解密实现 。 但在缺少支持框架或没有可用审核库的情况下 ， 我们需要对其进行正式的验证和审核 。
构建加密算法总是充满乐趣 。 在实现加密算法上存在许多挑战：你想不出一种实现加密技术的新算法 。 取而代之的是 ， 你将采用适合案例的现有的已成文的标准 ， 然后验证并一遍又一遍地审核它 。
这种情况就是在实现AES标准 。 这是一个有趣的挑战 。 我们已经构建了一些移动端和网页端的加密实现 ， 其中我自己深入学习了高级加密标准（AEP）、哈希消息身份验证码（HMAC）以及RSA公钥加密的详细知识 。
研究攻击媒介（如消息篡改或拒绝服务的影响）是审核解决方案的一部分 。 验证一系列加密步骤是否可以证明是安全的 ， 这
也是一件有趣的事 。
只要证明Encrypt-and-MAC（EaM）、MAC-then-Encrypt（MtE）和Encrypt-then-MAC（Etm）三者有一个是安全的即可 ， 但这并不意味着其他的是不安全的 。
概率论与预测：Uber的SubmitQueue
2016年 ， 我加入了Uber 。 移动端最大的痛点是构建以及合并更改需要花费的时间 。 从构建和所有测试（单元、集成和端到端）开始 ， 构建一个完整的运行大约需要40分钟 。 我们在开发中投入了大约300个开发者 。 所有的更改必须在落地之前搭建完成 。
我旁边的开发者体验团队想解决以下问题 ， 他们从两个角度做到了 。 首先 ， 他们加快了构建和测试过程 ， 耗时不超过30分钟；其次 ， 他们的目标是每个人的变更应该花费30分钟 ， 现有时间的95% 。
但是合并冲突呢？让我们对其进行预测 ， 并相应地建立队列 。 这就是他们通过创建冲突和推测图所做的事情 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
带有层次化索引的六边形网格：Uber
这是我没有参与的最后一个项目 ， 但是我发现并使用了基于它的工具 。 在这里 ， 我了解了一种新的数据结构：带有层次化索引的六边形网格 。
Uber要解决的最困难和最有趣的问题之一就是优化行程价格以及合作伙伴的调度 。 价格是动态的 ， 驱动程序也在不断变化 。 H3是Uber工程师构建的网格系统 ， 旨在以越来越细化的水平可视化和分析整个城市的数据 。 数据可视化结构就是带有层次化索引的六边形网格 。
「走过」微软、优步，老工程师告诉你哪些数据结构和算法最重要
文章图片
总结
这些是我多年来在多家公司中实际使用的算法和数据结构的重点 。
要在一家高科技公司工作 ， 你不需要了解流行算法或是外来数据结构的工作原理 。 你应该了解算法是什么 ， 并且能够自己提出一些简单的算法 ， 例如贪婪算法 。 你还应该了解更多常见的基本数据结构 ， 例如哈希表、队列、栈等等 。 但是你不需要记住Dijkstra或者A*这样特殊的算法 。
你可以将它们作为参考 ， 就像我实现加密算法时一样 。 对待红黑树或AVL树等一些不常见的数据结构也应如此 。 我从未用过这些数据结构 。 即使我用过 ， 也不会反复查看它们 。 我也从来没有问过需要使用这些知识才能解决的问题 ， 将来也不会 。
我一直在寻求一些实际的编码例子 ， 因为实际的例子中会有很多好的解决方案 ， 比如暴力枚举、贪心算法或其他一些更复杂的算法 。 比如 ， 有些问题 ， 你只需要一个数组和一些if/else语句就可以解决问题 ， 而无需任何复杂的数据结构 。
现实情况是 ， 许多团队和公司都面临算法的挑战 。 应该看到 ， 算法问题具有很大的吸引力 ， 它们能够在45分钟或者更短的时间内给出信号 ， 并且轻松地转换问题 。 因此问题泄漏带来的影响并不会很严重 。
招聘也比较容易 。 因为你可以拥有100多个问题的问题库 ， 任何面试官都可以评估其中的任何一个 。 特别是在硅谷 ， 听到动态编程和特殊数据结构问题的情况越来越多 。 这些问题将有助于聘请强大的工程师 ， 但同时也会导致将那些本不需了解一些复杂算法但却非常优秀的人拒之门外 。
原文链接：https://blog.pragmaticengineer.com/data-structures-and-algorithms-i-actually-used-day-to-day/


    推荐阅读


    上一篇：中国新闻网|《法制日报》更名为《法治日报》

    下一篇：吴硕情感|从燕国角度，看王道对国家影响，伐齐不灭齐，梦回天下共主时代