数组间取交集优化-二分查找

发表于   |   分类于   |  

场景

业务：下单时，手术类型中的商品需要与授权商品取交集过滤，剩下的商品才能返回给前端展示

难点：某些大客户手术类型数量有两百多，每个又包含数百商品，需要和多达十万的商品循环做取交集运算

问题：原先使用的lodash的intersection方法循环每个手术类型取交集,在获取用户德高的手术类型时需要耗时2500ms

设手术类型*商品数量为G,授权商品数量为N,当前时间复杂度为GN

优化

使用二分法查找：先确定待查数据的范围，然后逐步缩小范围直到找到或找不到该记录为止，需要先将数组排序

有序数组

先将授权商品排序,使用快速排序（NlogN），再用二分查找搜索商品(logN)

合计时间复杂度为NlogN+GlogN，减去原先N*G得到NlogN+(logN-N)*G所以N,G越大时优化效果越明显

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function searchSortArray(sortArray,val){
  function handle(left, right) {
    if (left > right){
      return false;
    } 
    const mid = Math.floor((left + right ) / 2);
    const midVal = sortArray[mid];
    if(midVal===val){
      return true;
    }
    if(midVal>val){
      return handle(left,mid-1)
    }
    return handle(mid+1,right)
  }
  return handle(0, sortArray.length - 1);
}
二叉搜索树(BST)
  • BST：根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值

有序数组在计算时，每次都要计算一次中间值(logN)，使用BST能省掉这次计算

再排序的基础上构建一个二叉搜索树（N）,再检索二叉树(logN)

所以原先的有序数组时间复杂度为 NlogN+2GlogN,二叉树的时间复杂度为NlogN+GlogN+N,相减得到GlogN-N,当G较大时使用BST效果好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 二叉树结构
function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}
// 有序数组转BST
function arrayToBST(sortArray) {
  function handle(left, right) {
    if (left > right){
      return null;
    } 
    const mid = Math.floor((left + right ) / 2);
    const root = new TreeNode(sortArray[mid]);
    root.left = handle(left, mid - 1);
    root.right = handle(mid + 1, right);
    return root;
  }
  return handle(0, sortArray.length - 1);
}
// 检索BST
function searchBST(BST, val) {
  if (!BST) return false;
  if (val === BST.val) {
    return true;
  }
  if (val < BST.val) {;
    return searchBST(BST.left, val);
  }
  return searchBST(BST.right, val);
}

结果

在使用BST优化后时间降为480ms,比原先快了5倍,效果显著

在实际业务处理中要对商品数量做判断后再选择合适的算法