[[319992]]

提出問題

從一個我常用的面試題，也是真實需求開始聊起：

你需要在前端展示 5000 條甚至更多的數(shù)據(jù)，每一條數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是一個對象，里面有各式各樣的屬性。每個屬性的值又可以是基本類型，對象，甚至數(shù)組。這里的對象或者數(shù)組內(nèi)部的元素又可以繼續(xù)包含對象或者數(shù)組并且允許無限嵌套下去。比如

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

頁面上提供一個搜索框，用戶通過輸入搜索的內(nèi)容可以找到包含這個內(nèi)容的數(shù)據(jù)。注意，只要任意數(shù)據(jù)對象的任意屬性值 (比如在上面的數(shù)據(jù)結(jié)構(gòu)中，只要 name, age, roles 任何一個屬性的值)包含這個關(guān)鍵詞即可。如果屬性值是數(shù)組或者對象，那么數(shù)組的元素或者對象的值繼續(xù)對輸入內(nèi)容進(jìn)行匹配檢測，并遞歸的檢測下去，只要有命中，便算該數(shù)據(jù)匹配

如何設(shè)計這個功能，讓搜索功能盡可能的快?

解決思路

• 如果你稍有程序員的敏感度，此時你的腦海里應(yīng)該有兩個念頭：
• 遍歷以及深度優(yōu)先遍歷是最直接的方式
• 如果要求夠快的話遍歷我就輸了

的確，遍歷是最簡單但也是最慢的。所以通常的優(yōu)化方法之一是通過空間換取時間;而另一個方法……稍后再引出。

這里我們嘗試通過建立字典樹(Trie)來優(yōu)化搜索。

如果你還不了解什么是字典樹，下面做簡單的介紹：假設(shè)我們有一個簡單的對象，鍵值的對應(yīng)關(guān)系如下： 

我們根據(jù)「鍵」的字母出現(xiàn)順次構(gòu)建出一棵樹出來，葉子節(jié)點值即有可能是某個「鍵」的值 

那么此時無論用戶想訪問任何屬性的值，只要從樹的根節(jié)點出發(fā)，依據(jù)屬性字母出現(xiàn)的順序訪問樹的葉子節(jié)點，即可得到該屬性的值。比如當(dāng)我們想訪問tea時： 

但是在我們需要解決的場景中，我們不需要關(guān)心「屬性」，我們只關(guān)心「值」是否匹配上搜索的內(nèi)容。所以我們只需要對「值」建立字典樹。

假設(shè)有以下的對象值

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 時，從a開始訪問，至最后訪問到字母 e 時，若在樹中有對應(yīng)的節(jié)點，表示命中;當(dāng)用戶搜索 aha 時，在訪問 h 時就已經(jīng)無法在樹中找到對應(yīng)的節(jié)點了，表示該對象不符合搜索條件

但實際工作中我們會有非常多個對象值，多個對象值之間可能有重復(fù)的值，所以匹配時，我們要把所有可能的匹配結(jié)果都返回。比如

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

上面兩個對象有相同的值 ack 和 an，所以在樹上的葉子節(jié)點中我們還要添加對象的 id 辨識信息

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

這樣當(dāng)用戶搜索 an 時，我們能返回所有的匹配項

OK，有了思路之后我們開始實現(xiàn)代碼。

代碼實現(xiàn)

假數(shù)據(jù)

首先要解決的一個問題是如果快速的偽造 5000 條數(shù)據(jù)?這里我們使用 https://randomuser.me/api/開源 API。為了簡單起見，我們讓它只返回 gender, email, phone, cell, nat基本數(shù)據(jù)類型的值，而不返回嵌套結(jié)構(gòu)(對象和數(shù)組)。注意這里只是為了便于代碼展示和理解，略去了復(fù)雜的結(jié)構(gòu)，也就避免了復(fù)雜的代碼。加入復(fù)雜結(jié)構(gòu)之后代碼其實也沒有大的變化，只是增加了遍歷的邏輯和遞歸邏輯而已。

請求 https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat 結(jié)果如下：

{ 
  "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" 
    } 
    //... 
  ] 
} 

葉子節(jié)點數(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é)點添加多個相同的匹配的id

幫助函數(shù)

在編碼的過程中我們需要一些幫助函數(shù)，比如:

• isEmptyObject: 判斷是否是空對象
• distinct: 移除一個數(shù)組中的重復(fù)元素

這兩個函數(shù)可以借用lodash類庫實現(xiàn)，即使手動實現(xiàn)起來也很簡單，這里就不贅述了

另一個重要的方法是normalize，我更習(xí)慣將normalize翻譯為「扁平化」(而不是「標(biāo)準(zhǔn)化」)，因為這樣更形象。該方法用于將一個數(shù)組里的對象拆分為 id 與對象的映射關(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é)果返回一個 id 數(shù)組時：[1, 2, 3]，我們只需要遍歷一邊返回結(jié)果就能通過 id 在扁平化的 Map 里立即找到對應(yīng)的數(shù)據(jù)。否則還要不停的遍歷原始數(shù)據(jù)數(shù)組找到對應(yīng)的數(shù)據(jù).

因為 randomuser.me 返回的信息中不包含 id 信息，所以我們暫時用 email 信息作為唯一標(biāo)示。normalize 的實現(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 => { 
        // 注意這里會把 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]; 
  }); 
} 

注意這里有一個collectChildrenInsideIds方法，這個方法用于收集該葉子節(jié)點下所有的子節(jié)點的 id。這么做是因為當(dāng)前操作模糊匹配，當(dāng)你搜索a時，apple, anna, ack 都算匹配。

常規(guī)搜索辦法以及字典樹的缺陷

為了對比效率，并且為了測試搜索結(jié)果的正確性，我們?nèi)匀恍枰帉懸粋€常規(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 
} 

注意在測試對象值是否匹配搜索詞時，我們使用了startsWith，而不是indexOf，這是因為字典樹的缺陷在于只能匹配以搜索詞開頭的詞!比如當(dāng)你搜索a時，只能匹配apple、anna而不能匹配banana。為了便于對比，我們不得不使用startsWith

性能的對比

性能的對比結(jié)果是很有意思的：

• 當(dāng)數(shù)據(jù)量較小時，查找效率不會有大的差異
• 當(dāng)數(shù)據(jù)量較大時，比如 5000 條的情況下，當(dāng)你的搜索詞非常短小，比如a，那么字典樹的查找效率會比遍歷搜索低，也就是反而花費的時間長;當(dāng)搜索詞變得具體時，比如ali，字典樹的查找效率會比遍歷搜索高
• 效率反而低的問題不難想到是為什么：當(dāng)你搜索詞簡單時，訪問的葉子節(jié)點會少，所以只能掃描children收集子節(jié)點的所有的可能 id，這步操作中遍歷的過程占用了大部分時間

但是我們?nèi)匀恍枰獫M足這部分的查詢需求，所以我們要針對這個場景做一些優(yōu)化

優(yōu)化簡短搜索的場景

我們回想一下簡單搜索的場景，性能的瓶頸主要在于我們需要遍歷葉子節(jié)點下的所有子節(jié)點。好辦，鑒于樹構(gòu)建完之后不會再發(fā)生變化，那么我們只需要提前計算好每個葉子節(jié)點的所以子 id 就好了，這就是文章開頭說的第二類優(yōu)化方案，即預(yù)計算。

我編寫了一個新的方法，用于遞歸的給每個葉子節(jié)點添加它所有子節(jié)點的 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)建完樹之后，用這個方法把所有葉子節(jié)點「裝飾」一遍就好了

結(jié)論

在通過預(yù)計算之后，在 5000 條數(shù)據(jù)的情況下，無論是短搜索還是長搜索，字典樹的查找效率基本是在 1ms 左右，而常規(guī)的遍歷查找則處于 10ms 左右，的確是十倍的提升。但是這個提升的代價是建立在犧牲空間，以及提前花費了時間計算的情況下。相信如果數(shù)據(jù)結(jié)構(gòu)變得更復(fù)雜，效率提升會更明顯