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

>事情要从GitHub上的一个issue谈起:https://github.com/LeuisKen/leuisken.github.io/issues/2,需求里面的我指代为issue里面的我。从一个需求谈起在我之前的项目中,曾经遇到过这样一个需求,编写一个级联选择器,大概是这样:1图中的示例使用的是Ant-Design的Cascader组件。要实现这一功能,我需要类似这样的数据结构:va...

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

>事情要从 GitHub 上的一个 issue 谈起:https://github.com/LeuisKen/leuisken.github.io/issues/2,需求里面的我指代为issue 里面的我

从一个需求谈起

在我之前的项目中,曾经遇到过这样一个需求,编写一个级联选择器,大概是这样:

11

图中的示例使用的是 Ant-Design 的 Cascader 组件。

要实现这一功能,我需要类似这样的数据结构:

vardata=[{
"value":"浙江",
"children":[{
"value":"杭州",
"children":[{
"value":"西湖"
}]
}]
},{
"value":"四川",
"children":[{
"value":"成都",
"children":[{
"value":"锦里"
},{
"value":"方所"
}]
},{
"value":"阿坝",
"children":[{
"value":"九寨沟"
}]
}]
}]

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。

但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:

vardata=[{
"province":"浙江",
"city":"杭州",
"name":"西湖"
},{
"province":"四川",
"city":"成都",
"name":"锦里"
},{
"province":"四川",
"city":"成都",
"name":"方所"
},{
"province":"四川",
"city":"阿坝",
"name":"九寨沟"
}]

前端这边想要将数据转换一下其实也不难,因为要合并重复项,可以参考数据去重的方法来做,于是我写了这样一个版本。

'usestrict'

/**
*将一个没有层级的扁平对象,转换为树形结构({value,children})结构的对象
*@param{array}tableData-一个由对象构成的数组,里面的对象都是扁平的
*@param{array}route-一个由字符串构成的数组,字符串为前一数组中对象的key,最终
*输出的对象层级顺序为keys中字符串key的顺序
*@return{array}保存具有树形结构的对象
*/

vartransObject=function(tableData,keys){
lethashTable={},res=[]
for(leti=0;i<tableData.length;i ){
if(!hashTable[tableData[i][keys[0]]]){
letlen=res.push({
value:tableData[i][keys[0]],
children:[]
})
//在这里要保存key对应的数组序号,不然还要涉及到查找
hashTable[tableData[i][keys[0]]]={$$pos:len-1}
}
if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]){
letlen=res[hashTable[tableData[i][keys[0]]].$$pos].children.push({
value:tableData[i][keys[1]],
children:[]
})
hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]={$$pos:len-1}
}
res[hashTable[tableData[i][keys[0]]].$$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].$$pos].children.push({
value:tableData[i][keys[2]]
})
}
returnres
}

vardata=[{
"province":"浙江",
"city":"杭州",
"name":"西湖"
},{
"province":"四川",
"city":"成都",
"name":"锦里"
},{
"province":"四川",
"city":"成都",
"name":"方所"
},{
"province":"四川",
"city":"阿坝",
"name":"九寨沟"
}]

varkeys=['province','city','name']

console.log(transObject(data,keys))

还好 keys 的长度只有 3 ,这种东西长了根本没办法写,很明显可以看出来这里面有重复的部分,可以通过循环搞定,但是想了很久都没有思路,就搁置了。

后来,有一天晚饭后不是很忙,就跟旁边做数据的同事聊了一下这个需求,请教一下该怎么用循环来处理。他看了一下,就问我:“你知道 trie 树吗?”。我头一次听到这个概念,他简单的给我讲了一下,然后说感觉处理的问题有些类似,让我可以研究一下 trie 树的原理并试着优化一下。

讲道理, trie 树这个数据结构网上确实有很多资料,但很少有使用 JavaScript 实现的,不过原理倒是不难。尝试之后,我就将 transObject 的代码优化成了这样。(关于 trie 树,还请读者自己阅读相关材料)

vartransObject=function(tableData,keys){
lethashTable={},res=[]
for(leti=0;i<tableData.length;i ){
letarr=res,cur=hashTable
for(letj=0;j<keys.length;j ){
letkey=keys[j],filed=tableData[i][key]
if(!cur[filed]){
letpusher={
value:filed
},tmp
if(j!==(keys.length-1)){
tmp=[]
pusher.children=tmp
}
cur[filed]={$$pos:arr.push(pusher)-1}
cur=cur[filed]
源文地址:https://www.guoxiongfei.cn/cntech/18366.html