速度提高几百倍，記一次數據結構在實際工作中的運用
這段時間寫了一堆源碼解析，這篇文章想換換口味，跟大家分享一個我工作中遇到的案例。畢竟作為一個打工人，上班除了摸魚看源碼外，磚還是要搬的。本文會分享一個使用恰當的數據結構來進行性能優化，從而大幅提高響應速度的故事，提高有幾百倍那麼多。
事情是這樣的，我現在供職一家外企，我們有一個給外國人用的線下賣貨的APP，賣的商品有衣服，鞋子，可樂什麼的。某天，產品經理找到我，提了一個需求：需要支援三層的產品選項。聽到這個需求，我第一反應是我好像沒有見到過三層的產品選項，畢竟我也是一個十來年的資深剁手黨，一般的產品選項好像最多兩層，比如下面是某電商APP一個典型的鞋子的選項：
這個鞋子就是兩層產品選項，一個是顏色，一個是尺碼，顏色總共有11種，尺碼總共也是11種。為了驗證我的直覺，我把我手機上所有的購物APP，啥淘寶，京東，拼多多，蘇寧易購全部打開看了一遍。在我看過的商品中，沒有發現一個商品有三層選項的，最多也就兩層。
本文可運行的示例程式碼已經上傳GitHub，大家可以拿下來玩玩：//github.com/dennis-jiang/Front-End-Knowledges/tree/master/Examples/DataStructureAndAlgorithm/OptimizeVariations
為什麼沒人做三層選項？
一兩家不做這個，可能是各家的需求不一樣，但是大家都不做，感覺事情不對頭。經過仔細分析後，我覺得不做三層選項可能有以下兩個原因：
1. 這可能是個偽需求
上面這個鞋子有11種顏色，11種尺碼，意味著這些選項後面對應的是11 * 11，總共121個商品。如果再來個第三層選項，假設第三層也有11個選項，那對應的商品總共就是11 * 11 * 11，也就是1331個商品，好多店鋪總共可能都沒有1331個商品。也就是說，第三層選項可能是個偽需求，用戶並沒有那麼多選項放在第三層，還是以上面的鞋子為例，除了顏色，尺碼外，非要再添一個層級，那隻能是性別了，也就是男鞋和女鞋。對於男鞋和女鞋來說，版型，尺碼這些很不一樣，一般都不會放到一個商品下面，更常用的做法是分成兩個商品，各自有自己的顏色和尺碼。
2. 有性能問題
僅僅是加上第三層選項這個功能並沒有什麼難的，也就是多展示幾個可以點擊的按鈕而已，點擊邏輯跟兩層選項並沒有太大區別。但是細想下去，我發現了他有潛在的性能問題。以上面這雙鞋子為例，我從後端API拿到的數據是這樣的：
const merchandise = {
// variations存放的是所有選項
variations: [
{
name: '顏色',
values: [
{ name: '限量版574海軍藍' },
{ name: '限量版574白粉' },
// 下面還有9個
]
},
{
name: '尺碼',
values: [
{ name: '38' },
{ name: '39' },
// 下面還有9個
]
},
],
// products數組存放的是所有商品
products: [
{
id: 1,
price: 208,
// 與上面variations的對應關係在每個商品的variationMappings裡面
variationMappings: [
{ name: '顏色', value: '限量版574白粉' },
{ name: '尺碼', value: '38'},
]
},
// 下面還有一百多個產品
]
}
上面這個結構本身還是挺清晰的，merchandise.variations是一個數組，有幾層選項，這個數組就有幾個對象，每個對象的name就是當前層級的名字，values就是當前層級包含的選項，所以merchandise.variations可以直接拿來顯示在UI上，將他們按照層級渲染成按鈕就行。
上面圖片中，用戶選擇了第一層的限量版574白粉，第二層的40，41等不存在的商品就自動灰掉了。用上面的數據結構可以做到這個功能，當用戶選擇限量版574白粉的時候，我們就去遍歷merchandise.products這個數組，這個數組的一個項就是一個商品，這個商品上的variationMappings會有當前商品的顏色和尺碼資訊。對於我當前的項目來說，如果這個商品可以賣，他就會在merchandise.products這個數組裡面，如果不可以賣，這個數組裡面壓根就不會有這個商品。比如上圖的限量版574白粉，40碼的組合就不會出現在merchandise.products裡面，查找的時候找不到這個組合，那就會將它變為灰色，不可以點。
所以對於限量版574白粉，40這個鞋子來說，為了知道它需不需要灰掉，我需要整個遍歷merchandise.products這個數組。按照前面說的11個顏色，11個尺碼來說，最多會有121個商品，也就是最多查找121次。同樣的要知道限量版574白粉，41這個商品可以不可以賣，又要整個遍歷商品數組，11個尺碼就需要將商品數組整個遍歷11次。對於兩層選項來說，11 * 11已經算比較多的了，每個尺碼百來次運算可能還不會有嚴重的性能問題。但是如果再加一層選項，新加這層假如也有11個可選項，這複雜度瞬間就增加了一個指數，從\(O(n^2)\)變成\(O(n^3)\)！現在我們的商品總數是11 * 11 * 11，也就是1331個商品，假如第三層是性別，現在為了知道限量版574白粉，40，男性這個商品可不可以賣，我需要遍歷1331個商品，如果遍歷121個商品需要20ms，還比較流暢，那遍歷1331個商品就需要220ms，這明顯可以感覺到卡頓了，在某些硬體較差的設備上，這種卡頓會更嚴重，變得不可接受了。而且我們APP使用的技術是React Native，本身性能就比原生差，這樣一來，用戶可能就怒而卸載了！
我拿著上述對需求的疑問，和對性能的擔心找到了產品經理，發生了如下對話：
我：大佬，我發現市面上好像沒有APP支援三層選項的，這個需求是不是有問題哦，而且三層選項相較於兩層選項來說，複雜度是指數增長，可能會有性能問題，用戶用起來會卡的。
產品經理：兄弟，你看的都是中國的APP，但是我們這個是給外國人用的，人家外國人就是習慣這麼用，咱要想賣的出去就得滿足他們的需求。太卡了肯定不行，性能問題，想辦法解決嘛，這就是在UI上再加幾個按鈕，設計圖都跟以前是一樣的，給你兩天時間夠了吧~
我：啊！？額。。。哦。。。
咱也不認識幾個外國人，咱也不敢再問，都說了是用戶需求，咱必須滿足了產品才賣的出去，產品賣出去了咱才有飯吃，想辦法解決吧！
解決方案
看來這個需求是必須要做了，這個功能並不複雜，因為三層選項可以沿用兩層選項的方案，繼續去遍歷商品數組，但是這個複雜度增長是指數級的，即從\(O(n^2)\)變成\(O(n^3)\)，用戶用起來會卡。現在，我需要思考一下，有沒有其他方案可以提高性能。經過仔細思考，我發現，這種指數級的複雜度增長是來自於我們整個數組的遍歷，如果我能夠找到一個方法不去遍歷這個數組，立即就能找到限量版574白粉，40，男性對應的商品存不存在就好了。
這個具體的問題轉換一下，其實就是：在一個數組中，通過特定的過濾條件，查找符合條件的一個項。嗯，查找，聽起來蠻耳熟的，現在我之所以需要去遍歷這個數組，是因為這些查找條件跟商品間沒有一個直接的對應關係，如果我能建立一個直接的對應關係，不就可以一下就找到了嗎？我想到了：查找樹。假如我重組這些層級關係，將它們組織為一顆樹，每個商品都對應樹上的一個葉子節點，我可以將三層選項的查找複雜度從\(O(n^3)\)降到\(O(1)\)。
兩層查找樹
為了說明白這個演算法，我先簡化這個問題，假設我們現在有兩層選項，顏色和尺碼，每層選項有兩個可選項：
- 顏色：白色，紅色
- 尺碼：39，40
我們現在對應有4個商品：
- 一號商品：productId為1，白色，39碼
- 二號商品：productId為2，白色，40碼
- 三號商品：productId為3，紅色，39碼
- 四號商品：productId為4，紅色，40碼
如果按照最簡單的做法，為了查找紅色的39碼鞋子存不存在，我們需要遍歷所有的這四個商品，這時候的時間複雜度為\(O(n^2)\)。但是如果我們構建像下面這樣一顆樹，可以將時間複雜度降到\(O(1)\)：
上面這顆樹，我們忽略root節點，在本例中他並沒有什麼用，僅僅是一個樹的入口，這棵樹的第一層淡黃色節點是我們第一層選項顏色，第二層淡藍色節點是我們的第二層選項尺碼，只是每個顏色節點都會對應所有的尺碼，這樣我們最後第二層的葉子節點其實就對應了具體的商品。現在我們要查找紅色的39碼鞋子，只需要看圖中紅色箭頭指向的節點上有沒有商品就行了。
那這種數據結構在JS中該怎麼表示呢？其實很簡單，一個對象就行了，像這樣：
const tree = {
"顏色：白色": {
"尺碼：39": { productId: 1 },
"尺碼：40": { productId: 2 }
},
"顏色：紅色": {
"尺碼：39": { productId: 3 },
"尺碼：40": { productId: 4 }
}
}
有了上面這個數據結構，我們要查找紅色的39碼直接取值tree["顏色：紅色"]["尺碼：39"]就行了，這個複雜度瞬間就變為\(O(1)\)了。
三層查找樹
理解了上面的兩層查找樹，要將它擴展到三層就簡單了，直接再加一層就行了。假如我們現在第三層選項是性別，有兩個可選項男和女，那我們的查找樹就是這樣子的：
對應的JS對象：
const tree = {
"顏色：白色": {
"尺碼：39": {
"性別：男": { productId: 1 },
"性別：女": { productId: 2 },
},
"尺碼：40": {
"性別：男": { productId: 3 },
"性別：女": { productId: 4 },
}
},
"顏色：紅色": {
"尺碼：39": {
"性別：男": { productId: 5 },
"性別：女": { productId: 6 },
},
"尺碼：40": {
"性別：男": { productId: 7 },
"性別：女": { productId: 8 },
}
}
}
同樣的，假如我們要查找一個白色的，39碼，男的鞋子，直接tree["顏色：白色"]["尺碼：39"]["性別：男"]就行了，這個時間複雜度也是\(O(1)\)。
寫程式碼
上面演算法都弄明白了，剩下的就是寫程式碼了，我們主要需要寫的程式碼就是用API返回的數據構建一個上面的tree這種結構就行了，一次遍歷就可以做到。比如上面這個三層查找樹對應的API返回的結構是這樣的：
const merchandise = {
variations: [
{
name: '顏色',
values: [
{ name: '白色' },
{ name: '紅色' },
]
},
{
name: '尺碼',
values: [
{ name: '39' },
{ name: '40' },
]
},
{
name: '性別',
values: [
{ name: '男' },
{ name: '女' },
]
},
],
products: [
{
id: 1,
variationMappings: [
{ name: '顏色', value: '白色' },
{ name: '尺碼', value: '39' },
{ name: '性別', value: '男' }
]
}
// 下面還有7個商品，我就不重複了
]
}
為了將API返回的數據轉換為我們的樹形結構數據我們寫一個方法：
function buildTree(apiData) {
const tree = {};
const { variations, products } = apiData;
// 先用variations將樹形結構構建出來，葉子節點默認值為null
addNode(tree, 0);
function addNode(root, deep) {
const variationName = variations[deep].name;
const variationValues = variations[deep].values;
for (let i = 0; i < variationValues.length; i++) {
const nodeName = `${variationName}：${variationValues[i].name}`;
if (deep === 2) {
root[nodeName] = null
} else {
root[nodeName] = {};
addNode(root[nodeName], deep + 1);
}
}
}
// 然後遍歷一次products給樹的葉子節點填上值
for (let i = 0; i < products.length; i++) {
const product = products[i];
const { variationMappings } = product;
const level1Name = `${variationMappings[0].name}：${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}：${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}：${variationMappings[2].value}`;
tree[level1Name][level2Name][level3Name] = product;
}
// 最後返回構建好的樹
return tree;
}
然後用上面的API測試數據運行下看下效果，發現構建出來的樹完全符合我們的預期：
這就好了嗎？
現在我們有了一顆查找樹，當用戶選擇紅色，40碼後，為了知道對應的男可不可以點，我們不需要去遍歷所有的商品了，而是可以直接從這個結構上取值。但是這就大功告成了嗎？並沒有！再仔細看下我們構建出來的數據結構，層級關係是固定的，第一層是顏色，第二層是尺碼，第三層是性別，而對應的商品是放在第三層性別上的。也就是說使用這個結構，用戶必須嚴格按照，先選顏色，再選尺碼，然後我們看看性別這裡哪個該灰掉。如果他不按照這個順序，比如他先選了性別男，然後選尺碼40，這時候我們應該計算最後一個層級顏色哪些該灰掉。但是使用上面這個結構我們是算不出來的，因為我們並沒有tree["性別：男"]["尺碼：40"]這個對象。
這怎麼辦呢？我們沒有性別-尺碼-顏色這種順序的樹，那我們就建一顆唄！這當然是個方法，但是用戶還可能有其他的操作順序呀，如果我們要覆蓋用戶所有可能的操作順序，總共需要多少樹呢？這其實是性別，尺碼，顏色這三個變數的一個全排列，也就是\(A_3^3\)，總共6顆樹。像我這樣的懶人，讓我建6棵樹，我實在懶得干。如果不建這麼多樹，需求又覆蓋不了，怎麼辦呢，有沒有偷懶的辦法呢？如果我能在需求上動點手腳，是不是可以規避這個問題？帶著這個思路，我想到了兩點：
1. 給一個默認值。
用戶打開商品詳情頁的時候，默認選中第一個可售商品。這樣就相當於我們一開始就幫用戶按照顏色-尺碼-性別這個順序選中了一個值，給了他一個默認的操作順序。
2. 不提供取消功能，只能切換選項
如果提供取消功能，他將我們提供的顏色-尺碼-性別默認選項取消掉，又可以選成性別-尺碼-顏色了。不提供取消功能，只能通過選擇其他選項來切換，只能從紅色換成白色，而不能取消紅色，其他的一樣。這樣我們就能永遠保證顏色-尺碼-性別這個順序，用戶操作只是只是每個層級選中的值不一樣，層級順序並不會變化，我們的查找樹就一直有效了。而且我發現某些購物網站也不能取消選項，不知道他們是不是也遇到了類似的問題。
對需求做這兩點修改並不會對用戶體驗造成多大影響，跟產品經理商量後，她也同意了。這樣我就從需求上幹掉了另外5棵樹，偷懶成功！
下面是三層選項跑起來的樣子：
還有一件事
前面的方案我們解決了查找的性能問題，但是引入了一個新問題，那就是需要創建這顆查找樹。創建這顆查找樹還是需要對商品列表進行一次遍歷，這是不可避免的，為了更順滑的用戶體驗，我們應該盡量將這個創建過程隱藏在用戶感知不到的地方。我這裡是將它整合到了商品詳情頁的載入狀態中，用戶點擊進入商品詳情頁，我們要去API取數據，不可避免的會有一個載入狀態，會轉個圈什麼的。我將這個遍歷過程也做到了這個轉圈中，當API數據返回，並且查找樹創建完成後，轉圈才會結束。這在理論上會延長轉圈的時間，但是本地的遍歷再慢也會比網路請求快點，所以用戶感知並不明顯。當轉圈結束後，所有數據都準備就緒了，用戶操作都是\(O(1)\)的複雜度，做到了真正的絲般順滑~
為什麼不讓後端創建這棵樹？
上面的方案都是在前端創建這顆樹，那有沒有可能後端一開始返回的數據就是這樣的，我直接拿來用就行，這樣我又可以偷懶了~我還真去找過後端，可他給我說：「我也想偷懶！」開個玩笑，真是情況是，這個商品API是另一個團隊維護的微服務，他們提供的數據不僅僅給我這一個終端APP使用，也給公司其他產品使用，所以要改返回結構涉及面太大，根本改不動。
封裝程式碼
其實我們這個方案實現本身是比較獨立的，其他人要是用的話，他也不關心你裡面是棵樹還是顆草，只要傳入選擇條件，能夠返回正確的商品就行，所以我們可以將它封裝成一個類。
class VariationSearchMap {
constructor(apiData) {
this.tree = this.buildTree(apiData);
}
// 這就是前面那個構造樹的方法
buildTree(apiData) {
const tree = {};
const { variations, products } = apiData;
// 先用variations將樹形結構構建出來，葉子節點默認值為null
addNode(tree, 0);
function addNode(root, deep) {
const variationName = variations[deep].name;
const variationValues = variations[deep].values;
for (let i = 0; i < variationValues.length; i++) {
const nodeName = `${variationName}：${variationValues[i].name}`;
if (deep === variations.length - 1) {
root[nodeName] = null;
} else {
root[nodeName] = {};
addNode(root[nodeName], deep + 1);
}
}
}
// 然後遍歷一次products給樹的葉子節點填上值
for (let i = 0; i < products.length; i++) {
const product = products[i];
const { variationMappings } = product;
const level1Name = `${variationMappings[0].name}：${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}：${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}：${variationMappings[2].value}`;
tree[level1Name][level2Name][level3Name] = product;
}
// 最後返回構建好的樹
return tree;
}
// 添加一個方法來搜索商品，參數結構和API數據的variationMappings一樣
findProductByVariationMappings(variationMappings) {
const level1Name = `${variationMappings[0].name}：${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}：${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}：${variationMappings[2].value}`;
const product = this.tree[level1Name][level2Name][level3Name];
return product;
}
}
然後使用的時候直接new一下就行：
const variationSearchMap = new VariationSearchMap(apiData); // new一個實例出來
// 然後就可以用這個實例進行搜索了
const searchCriteria = [
{ name: '顏色', value: '紅色' },
{ name: '尺碼', value: '40' },
{ name: '性別', value: '女' }
];
const matchedProduct = variationSearchMap.findProductByVariationMappings(searchCriteria);
console.log('matchedProduct', matchedProduct); // { productId: 8 }
總結
本文講述了一個我工作中實際遇到的需求，分享了我的實現和優化思路，供大家參考。我的實現方案不一定完美，如果大家有更好的方案，歡迎在評論區討論~
本文可運行的示例程式碼已經上傳GitHub，大家可以拿下來玩玩：//github.com/dennis-jiang/Front-End-Knowledges/tree/master/Examples/DataStructureAndAlgorithm/OptimizeVariations
下面再來回顧下本文的要點：
- 本文要實現的需求是一個商品的三層選項。
- 當用戶選擇了兩層後，第三層選項應該自動計算出哪些能賣，哪些不能賣。
- 鑒於後端API返回選項和商品間沒有直接的對應關係，為了找出能賣還是不能賣，我們需要遍歷所有商品。
- 當總商品數量不多的時候，所有商品遍歷可能不會產生明顯的性能問題。
- 但是當選項增加到三層，商品數量的增加是指數級的，性能問題就會顯現出來。
- 對於\(O(n^3)\)這種寫程式碼時就能預見的性能問題，我們不用等著報BUG了才處理，而是開發時直接就解決了。
- 本例要解決的是一個查找問題，所以我想到了建一顆樹，直接將\(O(n^3)\)的複雜度降到了\(O(1)\)。
- 但是一顆樹並不能覆蓋所有的用戶操作，要覆蓋所有的用戶操作需要6棵樹。
- 出於偷懶的目的，我跟產品經理商量，調整了需求和交互砍掉了5顆樹。真實原因是樹太多了，會佔用更多的記憶體空間，也不好維護。有時候適當的調整需求和交互也可以達到優化性能的效果，性能優化可以將交互和技術結合起來思考。
- 這個樹的搜索模組可以單獨封裝成一個類，外部使用者，不需要知道細節，直接調用介面查找就行。
- 前端會點數據結構還是有用的，本文這種場景下還很有必要。
文章的最後，感謝你花費寶貴的時間閱讀本文，如果本文給了你一點點幫助或者啟發，請不要吝嗇你的贊和GitHub小星星，你的支援是作者持續創作的動力。
作者博文GitHub項目地址： //github.com/dennis-jiang/Front-End-Knowledges
作者掘金文章匯總：//juejin.im/post/5e3ffc85518825494e2772fd
我也搞了個公眾號[進擊的大前端]，不打廣告，不寫水文，只發高品質原創，歡迎關注~
