为什么我认为数据结构与算法对前端开发很重要?

更新日期: 2018-12-30阅读量: 1482标签: 算法

从一个需求谈起

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


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

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

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

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

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

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


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

'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[tableData[i][keys[0]]]) {
      let len = res.push({
        0]],
        children: []
      })
      // 在这里要保存key对应的数组序号,不然还要涉及到查找
      hashTable[tableData[i][keys[0]]] = { $$pos: len - 1 }
    }
    if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {
      let len = res[hashTable[tableData[i][keys[0]]].$$pos].children.push({
        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({
      2]]
    })
  }
  return res
}

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

var keys = ['province', 'city', 'name']

console.log(transObject(data, keys))


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

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

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

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[j], filed = tableData[i][key]
      if (!cur[filed]) {
        let pusher = {
          value: filed
        }, tmp
        if (j !== (keys.length - 1)) {
          tmp = []
          pusher.children = tmp
        }
        cur[filed] = { $$pos: arr.push(pusher) - 1 }
        cur = cur[filed]
        arr = tmp
      } else {
        cur = cur[filed]
        arr = arr[cur.$$pos].children
      }
    }
  }
  return res
}


这样,解决方案就和keys的长短无关了。

这大概是我第一次,真正将数据结构的知识和前端项目需求结合在一起。


再谈谈我在面试遇到的问题

目前为止我参加过几次前端开发方面的面试,确实有不少面试官会问道一些算法。通常会涉及的,是链表、树、字符串、数组相关的知识。前端面试对算法要求不高,似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分,但是仅凭常见的面试题,而不去联系需求,很难让人觉得,算法对于前端真的很重要。

直到有一天,有一位面试官问我这样一个问题,下面我按照自己的回忆把对话模拟出来,A指面试官,B指我:

A:你有写过瀑布流吗?

B:我写过等宽瀑布流。实现是当用户拉到底部的一定高度的时候,向后端请求一定数量的图片,然后再插入到页面中。

A:那我问一下,如何让几列图片之间的高度差最小?

B:这个需要后端发来的数据里面有图片的高度,然后我就可以看当前高度最小的是哪里列,将新图片插入那一列,然后再看看新的高度最小的是哪一列。

A:我觉得你没有理解我的问题,我的意思是如何给后端发来的图片排序,让几列图片之间的高度差最小?

B:(想了一段时间)对不起,这个问题我没有思路。

A:你是软件工程专业的对吧?你们数据结构课有没有学动态规划?

B:可能有讲吧,但是我没什么印象了。

对话大概就是这样,虽然面试最终还是pass了,但这个问题确实让我很在意,因为我觉得,高度差“最”小,真的能用很简单的算法就解决吗?

这个问题的实质,其实就是有一个数组,将数组元素分成n份,每份所有元素求和,如何使每份的和的差最小。

搜索上面这个问题,很快就能找到相关的解答,很基本的一类动态规划问题——背包问题。

之前我确实看过背包问题的相关概念(也仅仅是相关概念)。当时我看到这样一段话:

许多使用递归去解决的编程问题,可以重写为使用动态规划的技巧去解决。动态规划方案通常会使用一个数组来建立一张表,用于存放被分解成众多子问题的解。当算法执行完毕,最终的解将会在这个表中很明显的地方被找到。

后面是一个用动态规划重写斐波那契数列的例子。我看到它只是将递归的结果,保存在了一个数组中,就天真的以为动态规划是优化递归的一种方法,并没有深入去理解。

不求甚解,确实早晚会出问题的。当时我虽然以为自己知道了算法的重要性,但其实还是太年轻。

动态规划可以求解一类“最优解”问题,这在某种程度上让我耳目一新。由于本文主要还是为了说明数据结构与算法对于前端的意义,关于动态规划的细节,本文也不会涉及,而且水平确实也不够。网上有许多非常好的博文,尤其推荐《背包九讲》。


多说两句——一道思考题

将如下扁平对象,转为树形对象。parent字段为空字符串的节点为根节点:

var input = {
  h3: {
    parent: 'h2',
    name: '副总经理(市场)'
  },
  h1: {
    parent: 'h0',
    name: '公司机构'
  },
  h7: {
    parent: 'h6',
    name: '副总经理(总务)'
  },
  h4: {
    parent: 'h3',
    name: '销售经理'
  },
  h2: {
    parent: 'h1',
    name: '总经理'
  },
  h8: {
    parent: 'h0',
    name: '财务总监'
  },
  h6: {
    parent: 'h4',
    name: '仓管总监'
  },
  h5: {
    parent: 'h4',
    name: '销售代表'
  },
  h0: {
    parent: '',
    name: 'root'
  }
};


这个需求在前端其实也很实际,示例中的对象是一个公司组织结构图。如果需求是让你在前端用svg之类的技术画出这样一张图,就需要这个功能。(另外我想到的一种应用场景,就是在前端展示类似windows资源管理器的文件树)

我当时想了很久,没有想到一个循环解决的方法,后来在stackoverflow上找到了答案:

var plain2Tree = function (obj) {
  var key, res
  for(key in obj) {
    var parent = obj[key].parent
    if(parent === '') {
      res = obj[key]
    } else {
      obj[parent][key] = obj[key]
    }
  }
  return res
}


这段代码,就是利用了JavaScript里面的引用类型,之后的思路,和操作指针没什么区别,就是构造一棵树。

但对于我来说,从来都没有往树和指针的那方面思考,就很被动了。


结语

以上列举了三道题,希望可以引起大家对于在前端应用数据结构与算法相关知识的共鸣。


来自:LeuisKen 


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/1722

一些常用的语音特征提取算法

语言是一种复杂的自然习得的人类运动能力。成人的特点是通过大约100块肌肉的协调运动,每秒发出14种不同的声音。说话人识别是指软件或硬件接收语音信号,识别语音信号中出现的说话人,然后识别说话人的能力

js实现生成任意长度的随机字符串

js生成任意长度的随机字符串,包含:数字,字母,特殊字符。实现原理:可以手动指定字符库及随机字符长度,利用Math.round()和Math.random()两个方法实现获取随机字符

js实现1万的阶乘

但是这样就会存在问题,Js中最大的安全整数为2^53- 1,10000!结果溢出该范围,代码运行结果为Infinity,无法计算出正确的结果。那么如何才能计算大数据的阶乘呢?

用 JavaScript 学习算法复杂度

在后面的例子中,我将引用这两个数组,一个包含 5 个元素,另一个包含 50 个元素。我还会用到 JavaScript 中方便的 performance API 来衡量执行时间的差异

JavaScript字符串压缩_js实现字符串压缩

设计一种方法,通过给重复字符计数来进行基本的字符串压缩。例如,字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数,则返回原始的字符串。 可以假设字符串仅包括a-z的字母

js实现合并两个有序数组

给定两个有序整数数组arr1和arr2,将 arr2和arr1进行合并为一个单调非递减的数组,并将其输出。方法一利用循环、方法二直接使用数组的sort方法。

Js排列组合的实现

犹记得高中数学,组合表示C(m, n),意思为从集合m,选出n个数生成一项,总共有多少个项的可能?组合是无序的,排列是有序的。所以排列的项数量多于组合

js实现快速排序算法的2种方式

通过两个for循环,每一次对比相邻两个数据的大小,小的排在前面,如果前面的数据比后面的大就交换这两个数的位置,这个方法就是比较次数太多了,效率比较低。

Js找出数组中出现次数最多的元素

给定一个数组,找出数组中出现次数最多的元素。给定数组 nums = [3,1,2,1,3,4,3,5,3,6,3], 函数应该返回: 次数最多的元素为:3, 次数为:5

js生成32位uuid算法总汇_js 如何生成uuid?

GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”,其中的 x 是 0-9 或 a-f 范围内的一个32位十六进制数。在理想情况下,任何计算机和计算机集群都不会生成两个相同的GUID。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!