降维打击！为什么我认为数据结构与算法对前端开发很重要

李泽芳 發表於 2019-5-30 15:22:00

降维打击！为什么我认为数据结构与算法对前端开发很重要

<h3> </h3>
<h6>> 事情要从 GitHub 上的一个 issue 谈起：https://github.com/LeuisKen/leuisken.github.io/issues/2，需求里面的我指代为 issue 里面的我。</h6>
<h3 id="hhttpsgithubcomleuiskenleuiskengithubioissues2">从一个需求谈起</h3>
在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：
 
<img src="https://cloud.githubusercontent.com/assets/7701575/15245665/849fb522-193a-11e6-98b2-5f4f39c63034.png">1
 
图中的示例使用的是 Ant-Design 的 Cascader 组件。
要实现这一功能，我需要类似这样的数据结构：
<pre><code class="javascript language-javascript hljs">var data = [{   "value": "浙江",   "children": [{     "value": "杭州",     "children": [{       "value": "西湖"     }]   }] }, {   "value": "四川",   "children": [{     "value": "成都",     "children": [{       "value": "锦里"     }, {       "value": "方所"     }]   }, {     "value": "阿坝",     "children": [{       "value": "九寨沟"     }]   }] }] </code></pre>
一个具有层级结构的数据，实现这个功能非常容易，因为这个结构和组件的结构是一致的，递归遍历就可以了。
但是，由于后端通常采用的是关系型数据库，所以返回的数据通常会是这个样子：
<pre><code class="javascript language-javascript hljs">var data = [{   "province": "浙江",   "city": "杭州",   "name": "西湖" }, {   "province": "四川",   "city": "成都",   "name": "锦里" }, {   "province": "四川",   "city": "成都",   "name": "方所" }, {   "province": "四川",   "city": "阿坝",   "name": "九寨沟" }] </code></pre>
前端这边想要将数据转换一下其实也不难，因为要合并重复项，可以参考数据去重的方法来做，于是我写了这样一个版本。
<pre><code class="javascript language-javascript hljs">'use strict' /**  * 将一个没有层级的扁平对象,转换为树形结构({value, children})结构的对象  * @param {array} tableData - 一个由对象构成的数组,里面的对象都是扁平的  * @param {array} route - 一个由字符串构成的数组,字符串为前一数组中对象的key,最终  * 输出的对象层级顺序为keys中字符串key的顺序  * @return {array} 保存具有树形结构的对象  */ var transObject = function(tableData, keys) {   let hashTable = {}, res = []   for( let i = 0; i < tableData.length; i++ ) {     if(!hashTable]]) {       let len = res.push({         value: tableData],         children: []       })       // 在这里要保存key对应的数组序号,不然还要涉及到查找       hashTable]] = { $$pos: len - 1 }     }     if(!hashTable]]]]) {       let len = res]].$$pos].children.push({         value: tableData],         children: []       })       hashTable]]]] = { $$pos: len - 1 }     }     res]].$$pos].children]]]].$$pos].children.push({       value: tableData]     })   }   return res } var data = [{   "province": "浙江",   "city": "杭州",   "name": "西湖" }, {   "province": "四川",   "city": "成都",   "name": "锦里" }, {   "province": "四川",   "city": "成都",   "name": "方所" }, {   "province": "四川",   "city": "阿坝",   "name": "九寨沟" }] var keys = ['province', 'city', 'name'] console.log(transObject(data, keys)) </code></pre>
还好 keys 的长度只有 3 ，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。
后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道 trie 树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下 trie 树的原理并试着优化一下。
讲道理， trie 树这个数据结构网上确实有很多资料，但很少有使用 JavaScript 实现的，不过原理倒是不难。尝试之后，我就将 <code>transObject</code> 的代码优化成了这样。（关于 trie 树，还请读者自己阅读相关材料）
<pre><code class="javascript language-javascript hljs">var transObject = function(tableData, keys) {   let hashTable = {}, res = []   for (let i = 0; i < tableData.length; i++) {     let arr = res, cur = hashTable     for (let j = 0; j < keys.length; j++) {       let key = keys, filed = tableData       if (!cur) {         let pusher = {           value: filed         }, tmp         if (j !== (keys.length - 1)) {           tmp = []           pusher.children = tmp         }         cur = { $$pos: arr.push(pusher) - 1 }         cur = cur         arr = tmp       } else {         cur = cur         arr = arr.children       }     }   }   return res } </code></pre>
这样，解决方案就和 keys 的长短无关了。
这种解决方案正如《三体》里面使用「二向箔」对宇宙文明进行降维打击一般干净利落！
<img src="https://raw.githubusercontent.com/MisterBooo/myBlogPic/master/20190530093132.jpg">
如果你对「Trie」树的相关概念不了解的话，可以继续往下查看进行阅读学习。
<blockquote>
这是之前的写的一篇旧文，小吴这里进行了一定的修改和排版
</blockquote>
<h3 id="htrie">Trie树</h3>
<blockquote>
Trie 这个名字取自“retrieval”，检索，因为 Trie 可以只用一个前缀便可以在一部字典中找到想要的单词。 虽然发音与「Tree」一致，但为了将这种字典树与普通二叉树以示区别，程序员小吴一般读「Trie」尾部会重读一声，可以理解为读「TreeE」。

</blockquote>
Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
此外 Trie 树也称前缀树（因为某节点的后代存在共同的前缀，比如 pan 是 panda 的前缀）。
它的key都为字符串，能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。
它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。
<h3 id="htrie-1">Trie树的特点 </h3>
假设有 5 个字符串，它们分别是：code，cook，five，file，fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 5 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？
如果将这 5 个字符串组织成下图的结构，从肉眼上扫描过去感官上是不是比查找起来会更加迅速。


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b54e82cd?w=1922&h=1074&f=png&s=102217">Trie树样子
通过上图，可以发现 Trie树的三个特点：
<ul>
<li>根节点不包含字符，除根节点外每一个节点都只包含一个字符</li>
<li>从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串</li>
<li>每个节点的所有子节点包含的字符都不相同</li>

</ul>
通过动画理解 Trie 树构造的过程。在构造过程中的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。 

<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b5365880?w=957&h=536&f=gif&s=125312"> Trie 树构造
<h3 id="htrie-2">Trie树的插入操作 </h3>


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b51f4db2?w=957&h=536&f=gif&s=223535">Trie树的插入操作
Trie树的插入操作很简单，其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。比如要插入新单词<code>cook</code>，就有下面几步：
<ul>
<li>插入第一个字母 <code>c</code>，发现 <code>root</code> 节点下方存在子节点 <code>c</code>，则共享节点 <code>c</code></li>
<li>插入第二个字母 <code>o</code>，发现 <code>c</code> 节点下方存在子节点 <code>o</code>，则共享节点 <code>o</code></li>
<li>插入第三个字母 <code>o</code>，发现 <code>o</code> 节点下方不存在子节点 <code>o</code>，则创建子节点 <code>o</code></li>
<li>插入第三个字母 <code>k</code>，发现 <code>o</code> 节点下方不存在子节点 <code>k</code>，则创建子节点 <code>k</code></li>
<li>至此，单词 <code>cook</code> 中所有字母已被插入 Trie树中，然后设置节点 <code>k</code> 中的标志位，标记路径 <code>root-&gt;c-&gt;o-&gt;o-&gt;k</code>这条路径上所有节点的字符可以组成一个单词<code>cook</code></li>

</ul>
<h3 id="htrie-3">Trie树的查询操作 </h3>
在 Trie 树中查找一个字符串的时候，比如查找字符串 <code>code</code>，可以将要查找的字符串分割成单个的字符 c，o，d，e，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b57767ae?w=1928&h=1084&f=png&s=149652">code的匹配路径
如果要查找的是字符串<code>cod</code>(鳕鱼)呢？还是可以用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串<code>cod</code>匹配的路径。但是，路径的最后一个节点「d」并不是橙色的，并不是单词标志位，所以<code>cod</code>字符串不存在。也就是说，<code>cod</code>是某个字符串的前缀子串，但并不能完全匹配任何字符串。


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b7443080?w=1920&h=1082&f=png&s=138065">cod的匹配路径
<h3 id="htrie-4">Trie树的删除操作 </h3>
Trie树的删除操作与二叉树的删除操作有类似的地方，需要考虑删除的节点所处的位置，这里分三种情况进行分析：
<h4 id="hhi">删除整个单词（比如 hi ）</h4>


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c049b68802a6?w=957&h=536&f=gif&s=177162">删除整个单词
<ul>
<li>从根节点开始查找第一个字符<code>h</code></li>
<li>找到<code>h</code>子节点后，继续查找<code>h</code>的下一个子节点<code>i</code></li>
<li><code>i</code>是单词<code>hi</code>的标志位，将该标志位去掉</li>
<li><code>i</code>节点是<code>hi</code>的叶子节点，将其删除</li>
<li>删除后发现<code>h</code>节点为叶子节点，并且不是单词标志位，也将其删除</li>
<li>这样就完成了<code>hi</code>单词的删除操作</li>

</ul>
<h4 id="hcod">删除前缀单词（比如 cod ）</h4>


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c04a41644ab1?w=957&h=536&f=gif&s=193343">删除前缀单词 这种方式删除比较简单。 只需要将<code>cod</code>单词整个字符串查找完后，<code>d</code>节点因为不是叶子节点，只需将其单词标志去掉即可。
 
<h4 id="hcook">删除分支单词（比如 cook ）</h4>


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c04a415421ef?w=957&h=536&f=gif&s=173918">删除分支单词 与 删除整个单词 情况类似，区别点在于删除到 <code>cook</code> 的第一个 <code>o</code> 时，该节点为非叶子节点，停止删除，这样就完成<code>cook</code>字符串的删除操作。
 
<h3 id="htrie-5">Trie树的应用 </h3>
事实上 Trie树在日常生活中的使用随处可见，比如这个：
具体来说就是经常用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
<h4 id="h1">1. 前缀匹配</h4>
例如：找出一个字符串集合中所有以 <code>五分钟</code> 开头的字符串。我们只需要用所有字符串构造一个 trie树，然后输出以五−>分−>钟开头的路径上的关键字即可。
trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能


<img src="https://user-gold-cdn.xitu.io/2019/1/2/1680c04a4167a729?w=1430&h=1210&f=png&s=392579">google搜索
<h4 id="h2">2. 字符串检索</h4>
给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。
检索/查询功能是Trie树最原始的功能。给定一组字符串，查找某个字符串是否出现过，思路就是从根节点开始一个一个字符进行比较：
<ul>
<li>如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。</li>
<li>如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。</li>

</ul>
<h3 id="htrie-6">Trie树的局限性 </h3>
如前文所讲，Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
假设字符的种数有<code>m</code>个，有若干个长度为n的字符串构成了一个 Trie树，则每个节点的出度为 <code>m</code>（即每个节点的可能子节点数量为<code>m</code>），Trie树的高度为<code>n</code>。很明显我们浪费了大量的空间来存储字符，此时Trie树的最坏空间复杂度为<code>O(m^n)</code>。也正由于每个节点的出度为<code>m</code>，所以我们能够沿着树的一个个分支高效的向下逐个字符的查询，而不是遍历所有的字符串来查询，此时Trie树的最坏时间复杂度为<code>O(n)</code>。
这正是空间换时间的体现，也是利用公共前缀降低查询时间开销的体现。
LeetCode 第 208 号问题就是 实现 Trie (前缀树)，感兴趣的小伙伴可以去实操一下。
希望今天的这篇文章能帮大家认识到掌握好了数据结构可以在工作中带来多大的帮助，大家加油：）
<img src="https://raw.githubusercontent.com/MisterBooo/myBlogPic/master/20190530152152.png">
  
来源：https://www.cnblogs.com/fivestudy/p/10949774.html

頁: [1]

琼殿技术论坛's Archiver

降维打击！为什么我认为数据结构与算法对前端开发很重要