场景描述:从几十万条数据中要找到某条或某几条满足条件的纪录
问题描述:采用循环检查的方式,几十万次循环,每次都要好几秒钟,多条时翻倍
思考过程:数组在获取某条数据时,即便有几十万条数据,如果知道下标,那么取到数据绝对分分钟搞定, 可否参照这个思路呢,说干就干,搜索排序数组,二分法可以将循环次数降低一个维度,有可能是好几个数量级,
实现步骤:先将数组根据指定属性排序,再用二分查找找到目标值,然后向前后探索,找到重复值,注意重复值个数
代码实现如下:
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=0">
</head>
<body>
< script>
var dataModel = [
{_id: 1001, w: ' u'},
{_id: 1002, w: '!b'},
{_id: 1003, w: '"'},
{_id: 1004, w: '&a'},
{_id: 1004, w: '&A'},
{_id: 1005, w: '- '},
{_id: 1006, w: '-!'},
{_id: 1007, w: '-1'},
{_id: 1008, w: '-a'},
{_id: 1009, w: '-c'},
{_id: 1010, w: '1a'},
{_id: 1011, w: '\''},
{_id: 1011, w: 'da'},
{_id: 1012, w: 'n'},
{_id: 1013, w: 'u '},
{_id: 1014, w: 'Un'},
{_id: 1015, w: 'un'},
]
// dataModel 必须是根据 attr 排过序的数组
var searchSortList = function (kk, attr) {
if (!kk || !attr) return []
kk = String(kk).toLowerCase()
var aa = 0
var bb = dataModel.length - 1
var mid = null
var cur = null
var item = null
var result = []
var max = 1000
while (max-- > 0) {
mid = Math.floor((aa + bb)/2)
cur = String(dataModel[mid][attr]).toLowerCase()
if (kk === cur) {
result.push(dataModel[mid])
for (var j = 8; j > 0; j--) {
item = dataModel[mid + j]
if (item && String(item[attr]).toLowerCase() === kk) result.push(item)
item = dataModel[mid - j]
if (item && String(item[attr]).toLowerCase() === kk) result.push(item)
}
break
} else if (kk > cur) {
aa = mid
} else {
bb = mid
}
}
return result
}
console.log(searchSortList('un', 'w'))
< / script >
</body>
</html>
总结:高一个维度思考找到的解决方案结果天差地别.