{"action":"created","issue":{"url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/2","repository_url":"https://api.github.com/repos/LeuisKen/leuisken.github.io","labels_url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/2/labels{/name}","comments_url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/2/comments","events_url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/2/events","html_url":"https://github.com/LeuisKen/leuisken.github.io/issues/2","id":154684034,"number":2,"title":"为什么我认为数据结构与算法对前端开发很重要？","user":{"login":"LeuisKen","id":7701575,"avatar_url":"https://avatars3.githubusercontent.com/u/7701575?v=3","gravatar_id":"","url":"https://api.github.com/users/LeuisKen","html_url":"https://github.com/LeuisKen","followers_url":"https://api.github.com/users/LeuisKen/followers","following_url":"https://api.github.com/users/LeuisKen/following{/other_user}","gists_url":"https://api.github.com/users/LeuisKen/gists{/gist_id}","starred_url":"https://api.github.com/users/LeuisKen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LeuisKen/subscriptions","organizations_url":"https://api.github.com/users/LeuisKen/orgs","repos_url":"https://api.github.com/users/LeuisKen/repos","events_url":"https://api.github.com/users/LeuisKen/events{/privacy}","received_events_url":"https://api.github.com/users/LeuisKen/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":5,"created_at":"2016-05-13T10:43:24Z","updated_at":"2017-06-22T04:53:50Z","closed_at":null,"body":"## 从一个需求谈起\n\n在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：\n\n![1](https://cloud.githubusercontent.com/assets/7701575/15245665/849fb522-193a-11e6-98b2-5f4f39c63034.png)\n\n图中的示例使用的是Ant-Design的Cascader组件。\n\n要实现这一功能，我需要类似这样的数据结构：\n\n``` js\nvar data = [{\n  \"value\": \"浙江\",\n  \"children\": [{\n    \"value\": \"杭州\",\n    \"children\": [{\n      \"value\": \"西湖\"\n    }]\n  }]\n}, {\n  \"value\": \"四川\",\n  \"children\": [{\n    \"value\": \"成都\",\n    \"children\": [{\n      \"value\": \"锦里\"\n    }, {\n      \"value\": \"方所\"\n    }]\n  }, {\n    \"value\": \"阿坝\",\n    \"children\": [{\n      \"value\": \"九寨沟\"\n    }]\n  }]\n}]\n```\n\n一个具有层级结构的数据，实现这个功能非常容易，因为这个结构和组件的结构是一致的，递归遍历就可以了。\n\n但是，由于后端通常采用的是关系型数据库，所以返回的数据通常会是这个样子：\n\n``` js\nvar data = [{\n  \"province\": \"浙江\",\n  \"city\": \"杭州\",\n  \"name\": \"西湖\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"成都\",\n  \"name\": \"锦里\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"成都\",\n  \"name\": \"方所\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"阿坝\",\n  \"name\": \"九寨沟\"\n}]\n```\n\n前端这边想要将数据转换一下其实也不难，因为要合并重复项，可以参考数据去重的方法来做，于是我写了这样一个版本。\n\n``` js\n'use strict'\n\n/**\n * 将一个没有层级的扁平对象,转换为树形结构({value, children})结构的对象\n * @param {array} tableData - 一个由对象构成的数组,里面的对象都是扁平的\n * @param {array} route - 一个由字符串构成的数组,字符串为前一数组中对象的key,最终\n * 输出的对象层级顺序为keys中字符串key的顺序\n * @return {array} 保存具有树形结构的对象\n */\n\nvar transObject = function(tableData, keys) {\n  let hashTable = {}, res = []\n  for( let i = 0; i < tableData.length; i++ ) {\n    if(!hashTable[tableData[i][keys[0]]]) {\n      let len = res.push({\n        value: tableData[i][keys[0]],\n        children: []\n      })\n      // 在这里要保存key对应的数组序号,不然还要涉及到查找\n      hashTable[tableData[i][keys[0]]] = { $$pos: len - 1 }\n    }\n    if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {\n      let len = res[hashTable[tableData[i][keys[0]]].$$pos].children.push({\n        value: tableData[i][keys[1]],\n        children: []\n      })\n      hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]] = { $$pos: len - 1 }\n    }\n    res[hashTable[tableData[i][keys[0]]].$$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].$$pos].children.push({\n      value: tableData[i][keys[2]]\n    })\n  }\n  return res\n}\n\nvar data = [{\n  \"province\": \"浙江\",\n  \"city\": \"杭州\",\n  \"name\": \"西湖\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"成都\",\n  \"name\": \"锦里\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"成都\",\n  \"name\": \"方所\"\n}, {\n  \"province\": \"四川\",\n  \"city\": \"阿坝\",\n  \"name\": \"九寨沟\"\n}]\n\nvar keys = ['province', 'city', 'name']\n\nconsole.log(transObject(data, keys))\n```\n\n还好keys的长度只有3，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。\n\n后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道trie树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下trie树的原理并试着优化一下。\n\n讲道理，trie树这个数据结构网上确实有很多资料，但很少有使用JavaScript实现的，不过原理倒是不难。尝试之后，我就将`transObject`的代码优化成了这样。（关于trie树，还请读者自己阅读相关材料）\n\n``` js\nvar transObject = function(tableData, keys) {\n  let hashTable = {}, res = []\n  for (let i = 0; i < tableData.length; i++) {\n    let arr = res, cur = hashTable\n    for (let j = 0; j < keys.length; j++) {\n      let key = keys[j], filed = tableData[i][key]\n      if (!cur[filed]) {\n        let pusher = {\n          value: filed\n        }, tmp\n        if (j !== (keys.length - 1)) {\n          tmp = []\n          pusher.children = tmp\n        }\n        cur[filed] = { $$pos: arr.push(pusher) - 1 }\n        cur = cur[filed]\n        arr = tmp\n      } else {\n        cur = cur[filed]\n        arr = arr[cur.$$pos].children\n      }\n    }\n  }\n  return res\n}\n```\n\n这样，解决方案就和keys的长短无关了。\n\n这大概是我第一次，真正将数据结构的知识和前端项目需求结合在一起。\n## 再谈谈我在面试遇到的问题\n\n目前为止我参加过几次前端开发方面的面试，确实有不少面试官会问道一些算法。通常会涉及的，是链表、树、字符串、数组相关的知识。前端面试对算法要求不高，似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分，但是仅凭常见的面试题，而不去联系需求，很难让人觉得，算法对于前端真的很重要。\n\n直到有一天，有一位面试官问我这样一个问题，下面我按照自己的回忆把对话模拟出来，A指面试官，B指我：\n\nA：你有写过瀑布流吗？\n\nB：我写过等宽瀑布流。实现是当用户拉到底部的一定高度的时候，向后端请求一定数量的图片，然后再插入到页面中。\n\nA：那我问一下，如何让几列图片之间的高度差最小？\n\nB：这个需要后端发来的数据里面有图片的高度，然后我就可以看当前高度最小的是哪里列，将新图片插入那一列，然后再看看新的高度最小的是哪一列。\n\nA：我觉得你没有理解我的问题，我的意思是如何给后端发来的图片排序，让几列图片之间的高度差最小？\n\nB：（想了一段时间）对不起，这个问题我没有思路。\n\nA：你是软件工程专业的对吧？你们数据结构课有没有学动态规划？\n\nB：可能有讲吧，但是我没什么印象了。\n\n对话大概就是这样，虽然面试最终还是pass了，但这个问题确实让我很在意，因为我觉得，高度差“最”小，真的能用很简单的算法就解决吗？\n\n这个问题的实质，其实就是有一个数组，将数组元素分成n份，每份所有元素求和，如何使每份的和的差最小。\n\n搜索上面这个问题，很快就能找到相关的解答，很基本的一类动态规划问题——背包问题。\n\n之前我确实看过背包问题的相关概念（也仅仅是相关概念）。当时我看到这样一段话：\n\n> 许多使用递归去解决的编程问题，可以重写为使用动态规划的技巧去解决。动态规划方案通常会使用一个数组来建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解将会在这个表中很明显的地方被找到。\n\n后面是一个用动态规划重写斐波那契数列的例子。我看到它只是将递归的结果，保存在了一个数组中，就天真的以为动态规划是优化递归的一种方法，并没有深入去理解。\n\n不求甚解，确实早晚会出问题的。当时我虽然以为自己知道了算法的重要性，但其实还是太年轻。\n\n动态规划可以求解一类“最优解”问题，这在某种程度上让我耳目一新。由于本文主要还是为了说明数据结构与算法对于前端的意义，关于动态规划的细节，本文也不会涉及，而且水平确实也不够。网上有许多非常好的博文，尤其推荐《背包九讲》。\n## 多说两句——一道思考题\n\n将如下扁平对象，转为树形对象。`parent`字段为空字符串的节点为根节点：\n\n``` js\nvar input = {\n  h3: {\n    parent: 'h2',\n    name: '副总经理(市场)'\n  },\n  h1: {\n    parent: 'h0',\n    name: '公司机构'\n  },\n  h7: {\n    parent: 'h6',\n    name: '副总经理(总务)'\n  },\n  h4: {\n    parent: 'h3',\n    name: '销售经理'\n  },\n  h2: {\n    parent: 'h1',\n    name: '总经理'\n  },\n  h8: {\n    parent: 'h0',\n    name: '财务总监'\n  },\n  h6: {\n    parent: 'h4',\n    name: '仓管总监'\n  },\n  h5: {\n    parent: 'h4',\n    name: '销售代表'\n  },\n  h0: {\n    parent: '',\n    name: 'root'\n  }\n};\n```\n\n这个需求在前端其实也很实际，示例中的对象是一个公司组织结构图。如果需求是让你在前端用svg之类的技术画出这样一张图，就需要这个功能。（另外我想到的一种应用场景，就是在前端展示类似windows资源管理器的文件树）\n\n我当时想了很久，没有想到一个循环解决的方法，后来在stackoverflow上找到了答案：\n\n``` js\nvar plain2Tree = function (obj) {\n  var key, res\n  for(key in obj) {\n    var parent = obj[key].parent\n    if(parent === '') {\n      res = obj[key]\n    } else {\n      obj[parent][key] = obj[key]\n    }\n  }\n  return res\n}\n```\n\n这段代码，就是利用了JavaScript里面的引用类型，之后的思路，和操作指针没什么区别，就是构造一棵树。\n\n但对于我来说，从来都没有往树和指针的那方面思考，就很被动了。\n## 结语\n\n以上列举了三道题，希望可以引起大家对于在前端应用数据结构与算法相关知识的共鸣。\n"},"comment":{"url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/comments/310275075","html_url":"https://github.com/LeuisKen/leuisken.github.io/issues/2#issuecomment-310275075","issue_url":"https://api.github.com/repos/LeuisKen/leuisken.github.io/issues/2","id":310275075,"user":{"login":"liujinyang1994","id":15340367,"avatar_url":"https://avatars1.githubusercontent.com/u/15340367?v=3","gravatar_id":"","url":"https://api.github.com/users/liujinyang1994","html_url":"https://github.com/liujinyang1994","followers_url":"https://api.github.com/users/liujinyang1994/followers","following_url":"https://api.github.com/users/liujinyang1994/following{/other_user}","gists_url":"https://api.github.com/users/liujinyang1994/gists{/gist_id}","starred_url":"https://api.github.com/users/liujinyang1994/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liujinyang1994/subscriptions","organizations_url":"https://api.github.com/users/liujinyang1994/orgs","repos_url":"https://api.github.com/users/liujinyang1994/repos","events_url":"https://api.github.com/users/liujinyang1994/events{/privacy}","received_events_url":"https://api.github.com/users/liujinyang1994/received_events","type":"User","site_admin":false},"created_at":"2017-06-22T04:53:50Z","updated_at":"2017-06-22T04:53:50Z","body":"非常赞同！不把数据结构和算法当基础的，都是耍流氓"}}
{"actor":{"display_login":"liujinyang1994"}}