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

场景

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

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

问题:原先使用的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倍,效果显著

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