前端老司机与算法的四个故事

本文来自作者 Alex 在 GitChat 上分享「前端工程师应该了解的算法」，「阅读原文」查看交流实录

「文末高能」

编辑 | 小牧

之前 chat 的介绍和公众号铺垫也比较多了，本文不再讨论前端是否应该学习算法。

因为能够看到这篇文章的朋友肯定是对算法感兴趣的朋友，我会讲解四个我经历过的跟算法相关的故事，然后总结下通过这四个故事对自己有什么感触：

1. 第一份工作是做多级联动选择器

2. 终于写了个纯真 IP 库却被鄙视

3. 我常来面试别人的题目：EventBus 实现

4. 面挂经验：LRU Cache 实现

第一份工作是做多级联动选择器

第一家公司一开始是一个生活信息分类网站，干的事情就像58赶集一样，刚刚去公司是做一个四级联动选择器，包括省市县和商圈，数据都是自己抓取。对于我来说，需要面临的挑战是：

1. 我不会抓取，当时没有 node 可以用 js 来做

2. 联动选择器应该怎么组织省市县和商圈数据，没有经验

3. 公司刚刚开始做分类信息业务，数据抓取整理后，要给后台、数据库等都需要用一套

领到任务之后，任务分解了下，主要包括两点：

1. 抓取，这块需要找老司机带带路

2. 整理数据，这块主要是为了级联选择器好用

数据抓取

抓取这块我不懂用什么来做，也不知道从哪里入手。

跟导师沟通后，导师让我找抓取组的同事寻求帮助，抓取组那时候主要采用 PHP，正好 PHP 有比较容易入门。

所以抱着一本 PHP 啃了一晚，学习了抓取相关的 curl 和正则语法之后，就开始干了。

这里多说几句，抓取这个事情，使我以后受益很大，我后来还做了很多其他数据的抓取，用来做垃圾站，倒不是为了赚钱，而是我发现了一种很快速学习和实践新技术的方法：

每次有什么新技术想练手，我就拿建站这块来做，移动webapp火了出来就做个移动站点，node出来就用node重写抓取，垃圾站server换成node。

所以很多新人一般学习完新技术之后，说项目中不用很快就忘记了，可以在自己的「小项目」中多练手，遇见问题解决问题才能巩固住。

这算是我自己学习的一个方法吧。

数据整理

级联选择器需要设计数据格式，说到底其实好的数据格式自然计算量和查找量就少了，所以我开始用了下面的树形菜单结构：

id是从1开始编码的，数据是根据级联选择器层层嵌套的，满足是满足需求了，用起来还算可以。

但是太「面向需求开发」了，每次找来找去，我自己都觉得麻烦，而且数据太大，对于页面也是负担，上线之后，这种数据格式用了很长一段时间，后面发现存在下面问题：

1. 根据id查找名称很麻烦，id没有规律可寻，没法提现层级关联

2. 嵌套太深，不利于遍历，不方便局部数据使用，比如只用青岛市的数据

在一个偶然的机会中，我了解到了天气预报网站（http://www.weather.com.cn/）的城市id编排方式很有意思，拿北京来说：

观察会发现：

id中下一级带着上一级的公共部分，可以通过简单预算求出上一级的id

后来发现国家统计局发布的省市县划分代码更加完善和权威，看下：http://www.stats.gov.cn/tjsj/tjbz/xzqhdm/201703/t20170310_1471429.html
这个链接的数据。当时一下子就茅塞顿开。

于是我将id对应name存了一份数据：

类似级联选择器这种需求的衍生数据，会直接用id来存储关系，这样可以提升查找速度：

拿到 id 之后，在去 idmap 表里面拿城市名称。

这样整理后，idmap 可以也可以给后台和数据库使用，dba同学专门存入一个表，扩展个拼音和备注都很方便！

现在来看之前做的事情好简单，现在 node 也有行政区域的抓取程序和整理的数据可用了，当时对于刚刚加入工作的我来说，抓取和整理都是个很有挑战性的新鲜事情。

总结下这个事情的启发

1. 你的工作可能会超过你的能力范围，要用于尝试和挑战

2. 要通过学习和调研来不断寻找更好的解决方案

3. 数据整理这块，我当时认为就已经是很有趣的数据结构事情了

终于写了个纯真 IP 库却被鄙视

现在这个 IP 库支撑我厂一个 Super APP 的基本 IP 定位和运营商判断功能。

比如：针对某些运营商下发不同的运营位或者针对没有定位信息的用户使用IP定位省市县，都有用到这个IP库。

事情开始的时候，公司内部有文本的 IP 库，也有 IP 查询的 API 接口。

但是经过调研发现，API 调用不符合我们需求：要求高效、低延迟的查询调用，因为无法忍受一个 app 开启的时候 update 接口下发数据太慢，会影响开屏时间。

经过一番调研之后，想到玩 QQ 时候的纯真 IP 库。零几年的时候，QQ 还可以加外挂显示 IP，其中比较有名的是纯真 IP 库。

这类 IP 库是将文本格式的 IP 信息库，转成 dat 这类二进制 IP 库，而且一搜索也有对应的很多版本的解析库。

所以要做的是：

• 设计一种二进制 IP 库的数据结构，能够将信息存入其中，保证体积尽可能小

• 写一个解析程序，输入用户 IP，能够从 IP 库中返回 IP 定位和运营商数据

想通过查找纯真 IP 库的设计，来做一套类似纯真 IP 库的设计，但是发现网上没有找到 IP 库详细的设计文档，通过解析代码来看纯真 IP 库的查询并不快。于是就有了开始自己动手搞一搞的冲动。

所以这里主要讲两点：

1. 数据库的数据结构设计

2. 实现快速查找

文本IP库格式

先说下一开始拿到的文本版本的IP信息库格式：

这段 IP 示例意思是：1.193.96.0|1.193.99.255这个IP段是同一个运营商，即 ChinaNet（电信），地理位置属于：中国，河南，郑州，中牟。

这种文本的IP库，国内数据大概48M大小，大概40多万条数据。

二进制数据库设计

上面的文本文件格式很简单，一行一个IP端，但是在实际查找一个IP对应的运营商和地理信息的时候很不方便，总不能把 text 文件逐行遍历查找吧，那样性能极低，而且文本文件格式也较大。

所以需要转成类似纯真IP库的二进制格式，然后加上索引区，通过多级索引区设计，可以快速查找到IP所在的数据区的起止位置，然后利用遍历找到对应的 IP 段，这样也可以缩小IP文件大小。

简单说下数据库设计原理，这里就不涉及太多细节：

1. 文件分为索引区和数据区两部分

2. 首4个字节是索引区最后的 offset，即数据区开始的 offset

3. 索引区分超级索引和普通索引，超级索引是：前1024个字符，每四个代表一个ip大段 [0~255]

4. 普通索引区每8个字节代表一个索引，前四个是ip段，5~7是对应的ip数据所在数据区的offset，最后是数据长度

5. 数据区域就是存的数据，为了使用方便，我又将数据分为包含省市中文名字、不包含中文名包含城市ID和全球IP数据，做出了3个IP库

1. 文件头就是标示索引和数据区的分界线 offset

2. 一级索引是1024个字节（256*4），用于快速根据 ip 第一个字段查出二级索引开始的 offset

3. 二级索引存着文本 ip 一段数据的长度和索引，称之为一条数据单位，比如：

实际存储为：0~3存 IP-end，即1.193.93.255，4~6存数据区数据的offset，7存数据长度。

这里需要介绍下：ip2long这个函数。

ip2long

写过 php 的应该知道 ip 值可以通过 ip2long 方法转换成 int 值，node 当中可以直接用 buffer 模块来实现：

这样一个ip就可以转成整数存储，而二级索引内的实际是按大小排好顺序存储单元（8个字节为一个单元，0~3是存储的ip end信息）

查找IP

假如我们查找IP为1.193.92.10，对应数据为：

整个的查找过程是这样的：

1. 把 ip.split('.')，得到 ipArr = [1,193,92,0]

2. 根据ipArr[0]，可以在一级索引区域找到对应的值：ipArr[0]*4

3. 将这个值在二级索引查找开始，然后往后查找比较二级索引一条数据单位，直到找到这个结束位置ip-end

4. 取出二级索引这个ip-end位置的数据区offset和长度，解二进制就可以得到数据

这里主要是二级（普通）索引的查找，需要遍历，比如：1.193.92.0|1.193.93.255这个区间，就需要从1开始查找，直到找到1.193.93.255相比小，找到为止。

其实这个就是个顺序查找算法，以我当时的能力自然想到的就是「遍历」！

当我把写完的 node 版本的查找程序让组里 php 同学给改成 php 版本， php 同学拿过来读了一边说：

你这个查找用遍历太慢了，时间复杂度是O(n)，可以用「夹逼法」重新写下，写完后复杂度降到O(log2n)，我给改改，改完了你再照着我写的php改成js版本的

黑线，本来想写完炫耀一番，没想到反而让人嘲笑了，而给我印象最深的是他提到那个邪恶的「夹逼法」让查找效率提升了一个级别，最后我按照他PHP写法重新用js实现的时候才知道，邪恶的「夹逼法」是这样写的：

而自己又查找了好多资料，原来这就是二分查找。。

这个故事讲完了，本来我以为设计的数据结构已经够完美了，值得炫耀一番，没想到查找算法上面反而被嘲笑了。

我常来面试别人的题目：EventBus 实现

这个题目本身是这样的：首先类似微博这种复杂交互的页面，分模块开发，需要多模块之间实现通信配合，如果候选人提到通过自定义事件之类方式来实现模块间通信，那么就会让他写个 EventBus，包括：事件的订阅、发布基本功能。

如果可以实现，则进一步问，如何实现 once 和 context（支持事件回调函数 this 绑定）功能。

这里主要考查点是：

1. 是否了解页面组件化开发通信机制

2. 能否实现自定义事件机制，以及实现的代码灵活度

其实对于 EventBus 的代码，主要设计在存储事件的数据结构上，假设这个存储事件的数据为 listeners：

• 事件监听是往listeners添加监听函数

• 事件触发是遍历相应事件listeners依次触发

• 事件解绑是从listeners上移除函数

一般来说，这三个主要操作的使用频次是：事件触发 > 事件监听 > 事件绑定。所以这是一个以读取为主的数据结构设计，而考虑到回调依次触发（一般先入先出），最好的结构就是队列；再考虑到事件是根据事件名称（类型）分类存储的，所以队列的上层还应该有个集合。最终listeners的结构设计为：

但是这种结构并不满足支持 once（触发一次就删除）的要求，所以 listeners 的事件类型数组（队列）还需要详细设计下：

这样，数组的单个值变成了对象，这个对象内包括了函数的 once 信息，标识是只执行一次的，这样执行完了事件回调函数之后，就可以按照这个 once 来移除 listener。

我用来面试别人的题目讲完了，其实就是一道由浅入深的面试题。我用它面过很多人，一部分人只知道 DOM 事件；

一部分人虽然用过但是不会写；也有虽然没用过，但是可以在引导下一步步实现的。

相对于项目经验丰富的，用过也能实现的候选人，我更喜欢没用过但是却能够理解并且实现的，这种候选人可能是因为项目经验不足，但他理解能力、学习能力强，可塑性高。

题目本身很简单，算是数据结构的基本知识，但是对于我来说面试这么多人，感触还是挺多的。

面挂经验：LRU Cache 实现

这是某一次面试经历，当时二面官是个安卓的研发，所以没啥共同语言可以聊，刚开始聊的多数是项目和人生之类的，突然最后问了一个技术题目：你知道 LRU cache 吧，给写一下吧！

突然画风转的有点摸不着头脑，还好我当时知道LRU大概是什么，根据LRU的特点估计可以写出来。先说下具体题目，再说面试的故事。

Least Recently Used (LRU) cache，直译过来就是最近最少使用的缓存，在有限的内存空间内，采取按照最近访问末尾淘汰机制，越最近使用的数据越往前排，将来使用的可能性越高，所以应该访问越快。

当数量超出设定长度，则根据最早时间访问的缓存先淘汰的原则进行淘汰。通常这是一种读写都频繁的应用场景，需要通过巧妙的算法来实现。

先来分析一下，LRU 通常包括增 add、删del、改set、查get四个方法，一看就想到了js对象，还需要做到更新，不停的将用到的拿到前面，自然想到数组了。

下面讲下两种是实现方式。

时间换空间的简单实现

先说一下最简单通过一个数组的实现。

1. 创建一个数组（array）

2. 新数据加上访问时间，插入（unshift）头部

3. 命中的数据，从数组中拿出（splice），更新访问时间，再插到（unshift）数组头部

4. 当数组长度超过设定长度（array.length=maxSize），则将尾部数据丢掉

缺点：每次都需要遍历查找数据，然后将数据重新推到表头。典型的时间换空间的思路，也是最常想到的最简单实现。

当然面试不能这么简单啊，而且也不实用呢。

空间换时间的实现

注意下，我第一个实现都用的是js常见的名字：数组和对象，其实js没有特别标示出来数组和对象是什么数据格式，数组本身就具有很多种数据结构，看你怎么用了。下面解决方式需用到双向链表和字典。

前面说过，js对象可以做到O(1)的读取，但是不能实现O(1)的查找更新？这时候如果了解数据结构就知道这个怎么搞了！

1. 读取的时候，按 key 从字典中读取出entry，返回 entry.value

2. 更新，将链表 head 改成 entry，entry.next 改成之前的 head

3. 修复链表链接：entry.prev 和 entry.next 连接起来

所有的操作都是常数级别的，不需要遍历！

最后再说面试故事

继续故事，知道LRU是什么东西，我就用对象来快速查找返回缓存的数据，利用数组遍历的方法来完成链表的维护，但是似乎还是怪怪的感觉，所以用js简单写了下数组和对象，后来越写越觉得太多此一举了，完全一个数组就搞定了，然后想跟面试官沟通，跟他解释了半天用对象和对象来做，他愣是没明白，我也知道估计是跨语言，他不懂，然后就随便说字典和队列，然后面试官说：我知道了！

然后就没有然后了。。。

对于这次惨（diu）痛（ren）的面试，我事后认真学习了下LRU的实现，同时总结如下：

1. 存在语言差异的工程师沟通来说，如果懂得基础理论和存在共同认知空间，能够大大提升沟通效率，有时候一个都熟悉的词（比如链表、字典）就可以给别人专业性的体现。

2. 对于了解数据结构和算法这些计算机基础知识，有助于扩展思路去解决问题

总结

故事讲完了，关于前端工程师应不应该掌握算法，我的答案是：肯定需要的。不得不说，现在前端工程师门槛越来越低，前端分工也越来越细，很多前端工程师从事的工作越来越「螺丝钉」，但是对于本Chat参与者，希望通过上面的讲述，能够得到下面的启发：

1. 知识面广度和深度都拓展，做好知识储备，迎接新机遇很重要（级联选择器）

2. 灵活的脑子，也需要系统的知识学习（IP库）

3. 算法和数据结构至少做到下面几点：

   1. 了解基础数据结构和应用场景，（LRU）

   2. 了解常见的排序算法和查找算法：比如冒泡、快排、二分法

   3. 了解常见算法思想：分治、动态规划、广度和深度搜索等

   4. 抽象能力和算法思维是工程师必备的技能！

4. 多联系工作和生活场景，活学活用

对于这个 chat，你有什么启发或疑惑，欢迎继续后面通过微信群来提问沟通~

福利

「阅读原文」看交流实录，你想知道的都在这里