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