码神之路:JavaScript篇@IT·互联网码神之路

JavaScript 数据结构之 用 Object 做 索引 实

2017-05-22  本文已影响69人  JSON_NULL

随着Web前端技术的不断发展,技术团队的不断壮大,越来越多的数据需要放在前端用JavaScript做处理。本篇我就来介绍一下,如何使用 Object 对象做索引,从而实现信息的快速检索。

场景一:根据ID找到学生信息

拿学生信息管理举例说明吧,其实公司里的员工管理,药店里的药品管理及分类管理都是类似的。

场景说明

在学生列表页面,后端把20名学生(每页20条数据)的所有信息都给到了Web前端;前端根据情况选择比较重要的信息在列表中显示。如果需要查看学生的详细信息,则需要点击“学生名”,或该点击对应列的“查看详情”按钮。

一般情况下在列表中,可点击部分都会绑定该第信息的“唯一标识码”(ID)。所以前端需要根据这个“唯一标识码”检索出对应学生的信息并显示出来。

在列表页面学生信息的结构如下面的代码段所示:

var students = [
    {id:1,name:"仵士杰",gender:"男",birthday:"1990-02-03",……},
    {id:2,name:"张珍珍",gender:"女",birthday:"1989-02-08",……},
     ……
];

需要强调以下几点:

  1. 在列表页面,学生的所有信息都已经加载到Web前端;
  2. 在列表页面仅显示了比较重要的学生信息,如:姓名、性别,班级;
  3. 详细信息页面包含列表页面所没有的信息,如:入学时间,年龄,证件照、学费金额、学费缴纳状态等;

一般做法

可能有人会想到,每次“查看详细信息”时就向后端发起一次请求。如果在列表页面仅是加载了学生的部分信息,而详情页面中显示的很多信息在列表页面中没有加载的情况下,只能用这种方式。当然我们例举的这个场景下这种做法也可以,但是对于一个在程序优化方面有强迫症且有些偏执的人来说,是绝对不会这么做的。

还有人想到了可以使用循环,代码如下:

function getStudentById(id){
  for(var i=0; i<students.length;i++){
    if(students[i].id == id){
      return students[i];
    }
  }
}

或者有人觉得循环的效率太低,于是想先对 students 数组排序,然后用二分查找。这是一个好的想法,但必须保证所选择的排序算法有较高的效率。否则还不如使用上面的循环。

以上这些方法中,最优的应该是二分查找;但门槛较高,需要写一个高效率的排序,然后还需要写二分查找的算法。

用 Object 做索引

在JavaScript中,Object 对象可以动态增加属性,对属性的访问速度是非常快的(可暂且认为与平衡二叉树的叶子结点的访问速度相同)。所以可以利用Object对象的这一特点构造快速检索的数据结构。

针对此场景生成 可快速检索的 Object 对象的代码如下:

var stuObj = {};
for(var i=0; i<students.length;i++){
  stuObj["_"+students[i].id] = students[i];
}

上面的代码生成了一个 stuObj 对象,这个对象中的属性与 students 数组中元素的id一一对应。可使用如下代码完成快速检索:

function getStudentById(id){
  return stuObj["_"+id];
}

小结

每次“查看详细信息”都向服务端发起一次请求的方案是最差的,这一点应该不会有异议。

使用循环的方式进行查找的时间复杂度是 O(n)。

排序后进行二分查找时,假设使用了效率较高的排序算法(如快排,n*logn)。二分查找的时间复杂度是 logn 。则总体时间复杂度为:n*logn /n+logn = 2logn。但这种方式需要我们写复杂的排序和二分查找算法,有些得不尝失。

最后分析用Object 做索引的方案。每次向Object中增加属性的时间复杂度是 logn(n是Object中当前属性的数量) ,外面有个for循环时间复杂度为n。而检索时的时间复杂度是 logn(n是Object中当前属性的数量)。所以总体时间复杂度约为: n*logn/n +logn = 2logn。

虽然我们用 Object 做索引时,在时间复杂度上与“快速排序+二分查找”相同,但是这种方案容易实现。不用写复杂的快排和二分查找算法。

场景二:多级联动时查找下一级select元素应该需要显示的option。

简单点,举一个“省、市、县”三级联动的例子吧。

场景说明

后端一次性把全国所有的省、市、县信息及它们之间的所属关系都发送到前端了。后面的事全部交给前端处理。原始数据结构如下面的代码段所示:

// 省
var province=[{name:"北京",id:1},{name:"河北",id:2},{name:"河南",id:3},……];

// 市
var city=[{name:"郑州市",id:1,province_id:3},{name:"周口",id:2,province_id:3},……];

// 县
var county=[{name:"郸城县",id:1,city_id:2},{name:"西化县",id:2,city_id:2},……];

当我选中一个省的时候,在第二级的select上元素需要显示该省下面所有的市以供选择。当我选择一个市时,在第三级的select元素上需要显示对应市下面所有的县以供选择。

一般做法

循环方式,当选中一个省时的示例代码如下:

function getCitysByProvinceId(province_id){
  var results = [];
  for(var i=0;i<city.length;i++){
    if(province_id == city[i].province_id){
      results.push(city[i]);
    }
  }
  return results;
}

当选中一个市时,获取市下面所有县的代码与上面的代码类似。

用 Object 做索引

首先需要创建索引,代码如下:

var cityByProvinceId = {};
for(var i=0;i<city.length;i++){
  if(!cityByProvinceId["_"+city[i].province_id]){
    cityByProvinceId["_"+city[i].province_id] = [];
  }
  cityByProvinceId["_"+city[i].province_id].push(city[i]);
}

索引完成后,检索就容易了,并且效率会非常之高:

function getCityByProvinceId(province_id){
  return cityByProvinceId["_"+province_id];
}

选择市时对县的处理方式,与选择省时对市的处理方式完全相同,在此不再赘述。

总结

在Web前端,需要用到快速检索的地方,用 Object 做索引的方式来完成是一个非常好的方案。首先,Object 中属性的检索效率是由JavaScript引擎优化过的,值得信赖。其次,没有复杂的算法和逻辑,代码清晰易读。即提高了效率又简化了代码,何乐而不为呢。

上一篇下一篇

猜你喜欢

热点阅读