用100行代码提升10倍的性能

2021/07/03 10:55

提出问题

{
"name": {
"firstName": "yi",
"lastName": "li"
},
"age": 23,
"projects": [{
"name": "demo",
"repo": ""
}]
}

解决思路

• 遍历以及深度优先遍历是最直接的方式
• 如果要求够快的话遍历我就输了

const o = {
message: 'ack'
fruit: 'apple',
unit: 'an',
name: 'anna',
}

root--a
|--c
|--k
|--p
|--p
|--l
|--e
|--n
|--n
|--a

[
{
id: 1,
message: 'ack'
fruit: 'apple',
unit: 'an',
name: 'anna',
},
{
id: 2,
message: 'ack'
fruit: 'banana',
unit: 'an',
name: 'lee',
},
]

root--a
|--c
|--k (ids: [1,2])
|--p
|--p
|--l
|--e (ids: [1])
|--n (ids: [1, 2])
|--n
|--a (ids: [1])

OK，有了思路之后我们开始实现代码。

代码实现

假数据

{
"results": [
{
"gender": "male",
"email": "enzo.dumont@example.com",
"phone": "02-65-13-26-00",
"cell": "06-09-02-19-99",
"nat": "FR"
},
{
"gender": "male",
"email": "gerald.omahony@example.com",
"phone": "011-376-3811",
"cell": "081-697-1414",
"nat": "IE"
}
//...
]
}

叶子节点数据结构

class Leaf {
constructor(id = "", value = "") {
this.ids = id ? [id] : [];
this.value = value;
this.children = {};
}
share(id) {
this.ids.push(id);
}
}

share方法用于向该叶子节点添加多个相同的匹配的id

帮助函数

• isEmptyObject: 判断是否是空对象
• distinct: 移除一个数组中的重复元素

[
{
id: 1,
message: 'ack'
fruit: 'apple',
unit: 'an',
name: 'anna',
},
{
id: 2,
message: 'ack'
fruit: 'banana',
unit: 'an',
name: 'lee',
},
]

{
'1': {
id: 1,
message: 'ack'
fruit: 'apple',
unit: 'an',
name: 'anna',
},
'2': {
id: 2,
message: 'ack'
fruit: 'banana',
unit: 'an',
name: 'lee',
}
}

function normalize(identify, data) {
const id2Value = {};
data.forEach(item => {
const idValue = item[identify];
id2Value[idValue] = item;
});
return id2Value;
}

构建一棵树

fetch("https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat")
.then(response => {
return response.json();
})
.then(data => {
const { results } = data;
const root = new Leaf();
const identifyKey = "email";

results.forEach(item => {
const identifyValue = item[identifyKey];
Object.values(item).forEach(itemValue => {
// 注意这里会把 Number 和 Boolean 类型也字符串化
const stringifiedValue = String(itemValue);
let tempRoot = root;
const arraiedStringifiedValue = Array.from(stringifiedValue);
arraiedStringifiedValue.forEach((character, characterIndex) => {
const reachEnd =
characterIndex === arraiedStringifiedValue.length - 1;
if (!tempRoot.children[character]) {
tempRoot.children[character] = new Leaf(
reachEnd ? identifyValue : "",
character
);
tempRoot = tempRoot.children[character];
} else {
if (reachEnd) {
tempRoot.children[character].share(identifyValue);
}
tempRoot = tempRoot.children[character];
}
});
});
});

模糊搜索

function searchBlurry(root, keyword, userMap) {
const keywordArr = Array.from(String(keyword));
let tempRoot = root;
let result = [];

for (let i = 0; i < keywordArr.length; i++) {
const character = keywordArr[i];
if (!tempRoot.children[character]) {
break;
} else {
tempRoot = tempRoot.children[character];
}
if (keywordArr.length - 1 === i) {
result = [
...tempRoot.ids,
...collectChildrenInsideIds(tempRoot.children)
];
}
}
return distinct(result).map(id => {
return userMap[id];
});
}

常规搜索办法以及字典树的缺陷

function regularSearch(searchKeyword) {
const regularSearchResults = [];
results.forEach(item => {
for (const key in item) {
const value = item[key];
if (String(value).startsWith(searchKeyword)) {
regularSearchResults.push(item);
break;
}
}
});
return regularSearchResults
}

性能的对比

• 当数据量较小时，查找效率不会有大的差异
• 当数据量较大时，比如 5000 条的情况下，当你的搜索词非常短小，比如a，那么字典树的查找效率会比遍历搜索低，也就是反而花费的时间长；当搜索词变得具体时，比如ali，字典树的查找效率会比遍历搜索高

优化简短搜索的场景

function decorateWithChildrenIds(root) {
const { children } = root;
root.childrenIds = collectChildrenInsideIds(root.children);
for (const character in children) {
const characterLeaf = children[character];
characterLeaf.childrenIds = collectChildrenInsideIds(
characterLeaf.children
);
decorateWithChildrenIds(characterLeaf);
}
}

2
1 收藏

0 评论
1 收藏
2