建站
咨詢
售后
建站咨詢
新聞中心
提出問(wèn)題
從一個(gè)我常用的面試題，也是真實(shí)需求開始聊起：
雨城網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)建站,雨城網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為雨城千余家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的雨城做網(wǎng)站的公司定做！
你需要在前端展示 5000 條甚至更多的數(shù)據(jù)，每一條數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是一個(gè)對(duì)象，里面有各式各樣的屬性。每個(gè)屬性的值又可以是基本類型，對(duì)象，甚至數(shù)組。這里的對(duì)象或者數(shù)組內(nèi)部的元素又可以繼續(xù)包含對(duì)象或者數(shù)組并且允許無(wú)限嵌套下去。比如
- {
- "name": {
- "firstName": "yi",
- "lastName": "li"
- },
- "age": 23,
- "roles": ['developer', 'admin'],
- "projects": [{
- "name": "demo",
- "repo": ""
- }]
- }
頁(yè)面上提供一個(gè)搜索框，用戶通過(guò)輸入搜索的內(nèi)容可以找到包含這個(gè)內(nèi)容的數(shù)據(jù)。注意，只要任意數(shù)據(jù)對(duì)象的任意屬性值 (比如在上面的數(shù)據(jù)結(jié)構(gòu)中，只要 name, age, roles 任何一個(gè)屬性的值)包含這個(gè)關(guān)鍵詞即可。如果屬性值是數(shù)組或者對(duì)象，那么數(shù)組的元素或者對(duì)象的值繼續(xù)對(duì)輸入內(nèi)容進(jìn)行匹配檢測(cè)，并遞歸的檢測(cè)下去，只要有命中，便算該數(shù)據(jù)匹配
如何設(shè)計(jì)這個(gè)功能，讓搜索功能盡可能的快?
解決思路
- 如果你稍有程序員的敏感度，此時(shí)你的腦海里應(yīng)該有兩個(gè)念頭：
- 遍歷以及深度優(yōu)先遍歷是最直接的方式
- 如果要求夠快的話遍歷我就輸了
的確，遍歷是最簡(jiǎn)單但也是最慢的。所以通常的優(yōu)化方法之一是通過(guò)空間換取時(shí)間;而另一個(gè)方法……稍后再引出。
這里我們嘗試通過(guò)建立字典樹(Trie)來(lái)優(yōu)化搜索。
如果你還不了解什么是字典樹，下面做簡(jiǎn)單的介紹：假設(shè)我們有一個(gè)簡(jiǎn)單的對(duì)象，鍵值的對(duì)應(yīng)關(guān)系如下：
我們根據(jù)「鍵」的字母出現(xiàn)順次構(gòu)建出一棵樹出來(lái)，葉子節(jié)點(diǎn)值即有可能是某個(gè)「鍵」的值
那么此時(shí)無(wú)論用戶想訪問(wèn)任何屬性的值，只要從樹的根節(jié)點(diǎn)出發(fā)，依據(jù)屬性字母出現(xiàn)的順序訪問(wèn)樹的葉子節(jié)點(diǎn)，即可得到該屬性的值。比如當(dāng)我們想訪問(wèn)tea時(shí)：
但是在我們需要解決的場(chǎng)景中，我們不需要關(guān)心「屬性」，我們只關(guān)心「值」是否匹配上搜索的內(nèi)容。所以我們只需要對(duì)「值」建立字典樹。
假設(shè)有以下的對(duì)象值
- const o = {
- message: 'ack'
- fruit: 'apple',
- unit: 'an',
- name: 'anna',
- }
建立的樹狀結(jié)構(gòu)如下：
- root--a
- |--c
- |--k
- |--p
- |--p
- |--l
- |--e
- |--n
- |--n
- |--a
當(dāng)用戶搜索 apple 時(shí)，從a開始訪問(wèn)，至最后訪問(wèn)到字母 e 時(shí)，若在樹中有對(duì)應(yīng)的節(jié)點(diǎn)，表示命中;當(dāng)用戶搜索 aha 時(shí)，在訪問(wèn) h 時(shí)就已經(jīng)無(wú)法在樹中找到對(duì)應(yīng)的節(jié)點(diǎn)了，表示該對(duì)象不符合搜索條件
但實(shí)際工作中我們會(huì)有非常多個(gè)對(duì)象值，多個(gè)對(duì)象值之間可能有重復(fù)的值，所以匹配時(shí)，我們要把所有可能的匹配結(jié)果都返回。比如
- [
- {
- id: 1,
- message: 'ack'
- fruit: 'apple',
- unit: 'an',
- name: 'anna',
- },
- {
- id: 2,
- message: 'ack'
- fruit: 'banana',
- unit: 'an',
- name: 'lee',
- },
- ]
上面兩個(gè)對(duì)象有相同的值 ack 和 an，所以在樹上的葉子節(jié)點(diǎn)中我們還要添加對(duì)象的 id 辨識(shí)信息
- root--a
- |--c
- |--k (ids: [1,2])
- |--p
- |--p
- |--l
- |--e (ids: [1])
- |--n (ids: [1, 2])
- |--n
- |--a (ids: [1])
這樣當(dāng)用戶搜索 an 時(shí)，我們能返回所有的匹配項(xiàng)
OK，有了思路之后我們開始實(shí)現(xiàn)代碼。
代碼實(shí)現(xiàn)
假數(shù)據(jù)
首先要解決的一個(gè)問(wèn)題是如果快速的偽造 5000 條數(shù)據(jù)?這里我們使用 https://randomuser.me/api/開源 API。為了簡(jiǎn)單起見，我們讓它只返回 gender, email, phone, cell, nat基本數(shù)據(jù)類型的值，而不返回嵌套結(jié)構(gòu)(對(duì)象和數(shù)組)。注意這里只是為了便于代碼展示和理解，略去了復(fù)雜的結(jié)構(gòu)，也就避免了復(fù)雜的代碼。加入復(fù)雜結(jié)構(gòu)之后代碼其實(shí)也沒有大的變化，只是增加了遍歷的邏輯和遞歸邏輯而已。
請(qǐng)求 https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat 結(jié)果如下：
- {
- "results": [
- {
- "gender": "male",
- "email": "enzo.dumont@cdxwcx.com",
- "phone": "02-65-13-26-00",
- "cell": "06-09-02-19-99",
- "nat": "FR"
- },
- {
- "gender": "male",
- "email": "gerald.omahony@cdxwcx.com",
- "phone": "011-376-3811",
- "cell": "081-697-1414",
- "nat": "IE"
- }
- //...
- ]
- }
葉子節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
根據(jù)思路中的描述，數(shù)據(jù)結(jié)構(gòu)描述如下：
- class Leaf {
- constructor(id = "", value = "") {
- this.ids = id ? [id] : [];
- this.value = value;
- this.children = {};
- }
- share(id) {
- this.ids.push(id);
- }
- }
share方法用于向該葉子節(jié)點(diǎn)添加多個(gè)相同的匹配的id
幫助函數(shù)
在編碼的過(guò)程中我們需要一些幫助函數(shù)，比如:
- isEmptyObject: 判斷是否是空對(duì)象
- distinct: 移除一個(gè)數(shù)組中的重復(fù)元素
這兩個(gè)函數(shù)可以借用lodash類庫(kù)實(shí)現(xiàn)，即使手動(dòng)實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單，這里就不贅述了
另一個(gè)重要的方法是normalize，我更習(xí)慣將normalize翻譯為「扁平化」(而不是「標(biāo)準(zhǔn)化」)，因?yàn)檫@樣更形象。該方法用于將一個(gè)數(shù)組里的對(duì)象拆分為 id 與對(duì)象的映射關(guān)系。
比如將
- [
- {
- 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',
- }
- }
之所以要這么做是為了當(dāng)檢索結(jié)果返回一個(gè) id 數(shù)組時(shí)：[1, 2, 3]，我們只需要遍歷一邊返回結(jié)果就能通過(guò) id 在扁平化的 Map 里立即找到對(duì)應(yīng)的數(shù)據(jù)。否則還要不停的遍歷原始數(shù)據(jù)數(shù)組找到對(duì)應(yīng)的數(shù)據(jù).
因?yàn)?randomuser.me 返回的信息中不包含 id 信息，所以我們暫時(shí)用 email 信息作為唯一標(biāo)示。normalize 的實(shí)現(xiàn)如下：
- function normalize(identify, data) {
- const id2Value = {};
- data.forEach(item => {
- const idValue = item[identify];
- id2Value[idValue] = item;
- });
- return id2Value;
- }
構(gòu)建一棵樹
這部分代碼就沒有什么秘密了，完全是按照遞算法歸構(gòu)建一顆樹了
- 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 => {
- // 注意這里會(huì)把 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];
- });
- }
注意這里有一個(gè)collectChildrenInsideIds方法，這個(gè)方法用于收集該葉子節(jié)點(diǎn)下所有的子節(jié)點(diǎn)的 id。這么做是因?yàn)楫?dāng)前操作模糊匹配，當(dāng)你搜索a時(shí)，apple, anna, ack 都算匹配。
常規(guī)搜索辦法以及字典樹的缺陷
為了對(duì)比效率，并且為了測(cè)試搜索結(jié)果的正確性，我們?nèi)匀恍枰帉懸粋€(gè)常規(guī)的遍歷的搜索方法：
- 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
- }
注意在測(cè)試對(duì)象值是否匹配搜索詞時(shí)，我們使用了startsWith，而不是indexOf，這是因?yàn)樽值錁涞娜毕菰谟谥荒芷ヅ湟运阉髟~開頭的詞!比如當(dāng)你搜索a時(shí)，只能匹配apple、anna而不能匹配banana。為了便于對(duì)比，我們不得不使用startsWith
性能的對(duì)比
性能的對(duì)比結(jié)果是很有意思的：
- 當(dāng)數(shù)據(jù)量較小時(shí)，查找效率不會(huì)有大的差異
- 當(dāng)數(shù)據(jù)量較大時(shí)，比如 5000 條的情況下，當(dāng)你的搜索詞非常短小，比如a，那么字典樹的查找效率會(huì)比遍歷搜索低，也就是反而花費(fèi)的時(shí)間長(zhǎng);當(dāng)搜索詞變得具體時(shí)，比如ali，字典樹的查找效率會(huì)比遍歷搜索高
- 效率反而低的問(wèn)題不難想到是為什么：當(dāng)你搜索詞簡(jiǎn)單時(shí)，訪問(wèn)的葉子節(jié)點(diǎn)會(huì)少，所以只能掃描children收集子節(jié)點(diǎn)的所有的可能 id，這步操作中遍歷的過(guò)程占用了大部分時(shí)間
但是我們?nèi)匀恍枰獫M足這部分的查詢需求，所以我們要針對(duì)這個(gè)場(chǎng)景做一些優(yōu)化
優(yōu)化簡(jiǎn)短搜索的場(chǎng)景
我們回想一下簡(jiǎn)單搜索的場(chǎng)景，性能的瓶頸主要在于我們需要遍歷葉子節(jié)點(diǎn)下的所有子節(jié)點(diǎn)。好辦，鑒于樹構(gòu)建完之后不會(huì)再發(fā)生變化，那么我們只需要提前計(jì)算好每個(gè)葉子節(jié)點(diǎn)的所以子 id 就好了，這就是文章開頭說(shuō)的第二類優(yōu)化方案，即預(yù)計(jì)算。
我編寫了一個(gè)新的方法，用于遞歸的給每個(gè)葉子節(jié)點(diǎn)添加它所有子節(jié)點(diǎn)的 id:
- 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);
- }
- }
那么在構(gòu)建完樹之后，用這個(gè)方法把所有葉子節(jié)點(diǎn)「裝飾」一遍就好了
結(jié)論
在通過(guò)預(yù)計(jì)算之后，在 5000 條數(shù)據(jù)的情況下，無(wú)論是短搜索還是長(zhǎng)搜索，字典樹的查找效率基本是在 1ms 左右，而常規(guī)的遍歷查找則處于 10ms 左右，的確是十倍的提升。但是這個(gè)提升的代價(jià)是建立在犧牲空間，以及提前花費(fèi)了時(shí)間計(jì)算的情況下。相信如果數(shù)據(jù)結(jié)構(gòu)變得更復(fù)雜，效率提升會(huì)更明顯
本文標(biāo)題：用100行代碼提升10倍的性能
轉(zhuǎn)載源于：http://www.dlmjj.cn/article/dhdiggg.html
