從 JavaScript 數組去重談性能優化

作者：玉伯

javascript 數組去重經常出現在前端招聘的筆試題裡，比如：

有數組 <code>var arr = ['a', 'b', 'c', '1', 0, 'c', 1, '', 1, 0]</code>，請用 javascript 實作去重函數<code>unqiue</code>，使得 <code>unique(arr)</code> 傳回 <code>['a', 'b', 'c', '1', 0, 1, '']</code>

作為筆試題，考點有二：

正确。别小看這個考點，考慮到 javascript 經常要在浏覽器上運作，在千姿百态的各種浏覽器環境下要保障一個函數的正确性可不是一件簡單的事，不信你繼續讀完這篇部落格。

性能。雖然大部分情況下 javascript 語言本身（狹義範疇，不包含 dom 等延拓）不會導緻性能問題，但很不幸這是一道考題，是以面試官們還是會把性能作為一個考點。

在繼續往下閱讀之前，建議先實作一個自己認為最好的版本。

對于數組去重，隻要寫過程式的，立刻就能得到第一個解法：

直覺往往很靠譜，在現代浏覽器下，上面這個函數很正确，性能也不錯。但前端最大的悲哀也是挑戰之處在于，要支援各種運作環境。在 ie6-8 下，數組的 <code>indexof</code> 方法還不存在。直覺方案要稍微改造一下：

寫到這一步，正确性已沒問題，但性能上，兩重循環會讓面試官們看了不爽。

一談到優化，往往就是八仙過海、百花齊放。但八仙往往不接地氣，百花則很容易招來臭蟲。數組去重的各種優化方案在此不一一讨論，下面隻說最常用效果也很不錯的一種。

核心是建構了一個 <code>hash</code> 對象來替代 <code>indexof</code>. 注意在 javascript 裡，對象的鍵值隻能是字元串，是以需要 <code>var key = typeof(item) + item</code> 來區分數值 <code>1</code> 和字元串 <code>'1'</code> 等情況。

但優化真的很容易帶來坑，比如上面的實作，對下面這種輸入就無法判斷：

可以繼續修改代碼，做到性能和正确性都很好。但往往，這帶來的結果并不好。

寫到這裡，這篇部落格才算進入正題。程式員心中都會有一些夢想，比如寫出又通用性能又好的普适函數。這種夢想是讓程式員變得卓越的重要内驅力，但倘若不加以控制，也很容易走入迷途。

回到性能優化。這年頭有各種各樣優化，核心系統、資料庫、網絡、前端等等，所有這些優化，都必須回答下面這個問題：

目前有什麼。在什麼場景下進行優化，場景下有哪些具體限制。理清限制很重要，限制往往帶來自由。

究竟要什麼。優化的目的是什麼。是提高穩定性，還是增大吞吐量，抑或減少使用者等待時間。在回答這個問題之前，優化都是徒勞。對這個問題的準确回答，能為優化帶來具體可測量的參數，這樣優化才有目标。

可以放棄什麼。魚與熊掌不可兼得。優化的本質是在具體場景下的取舍、權衡。什麼都不願意放棄的話，優化往往會舉步維艱。

寫這篇部落格，不是為了解答一到筆試題，這道筆試題有點無聊。寫這篇部落格的原始驅動力是因為最近在做 seajs 的性能調優，其中有一個需求是：

上面是一個子產品，通過解析函數字元串，可以拿到子產品的依賴數組：<code>['./a', './b', './a']</code>，這個依賴資訊有可能會出現重複字段，是以要做去重。

針對這個具體場景，來回答上面三個問題：

目前有什麼。有的是輸入限制，隻需要考慮字元串。

究竟要什麼。這個問題比較簡單，希望 unique 方法盡可能快，名額是用 chrome 調試工具中的 profiles 面闆檢視指定測試頁面中 unique 方法的耗時，目标是 5ms 以内。

可以放棄什麼。隻需處理字元串，其他類型的都可以不支援。談到放棄往往很有意思，這個問題不那麼簡單，接下來再說。

一旦分析清楚了具體場景，解決方案就相對簡單：

上面的代碼依賴 <code>foreach</code> 和 <code>keys</code>，離不開上下文環境（環境很重要很重要），完整代碼：util-lang.js

上面這個方案，無論從代碼體積、正确性、還是各種浏覽器下的綜合性能來考量，都很不錯。

直到有一天出現這樣一個測試用例：

上面的測試用例，會調用

ie 有各種各樣的 bug，下面是不怎麼著名但真實存在的一個：

在現代浏覽器下，上面會正确輸出兩個值，但在 old ie 下不會輸出。這是 ie 的枚舉 bug：a safer object.keys compatibility implementation “完美”的解決方案如下：

除了 <code>dontenums</code> 數組，還可以特别注意 <code>hasownproperty</code> 的處理方式。對于前端來說，要保障“正确”是一件多麼不容易的事。

注意：行文至此，已經不是在讨論 <code>unique</code> 的實作問題，比如上面實際上在讨論的是 <code>object.keys</code> 的實作問題。

我有什麼、我要什麼、我可以放棄什麼，這其實是馬雲在回答内網一個神貼時的回複，那個神貼是我發的，是以馬雲這幾句話讓我印象非常深刻。

優化的本質是做減法，做減法最困難的是選擇放棄。

對于 seajs 來說，真的需要上面那個“完美”的解決方案嗎？

程式員心中的完美主義、理想主義情結曾一度讓我非常不能容忍代碼中有 “bug” 存在。

可是，大家都懂的：

還有紅樓夢……

知道道理容易，比如很懷念小時候的《思想品德》課，要扶老奶奶過馬路、要誠實等等，絕大部分人都懂得這些道理，可做到的，發現沒幾個。

如果你聽了我上面一通知易行難的扯淡就決定趕緊“放棄”，那也有悖程式員的職業素養。

依舊得回到具體場景。在 seajs 裡，适當調整代碼邏輯：

上面的代碼，能保證傳給 unique 方法的輸入是：

是以 dontenums bug 在 seajs 裡通過這麼一調整就不存在了。

仔細分析，控制好輸入，會讓代碼更簡單同時可靠。

其實不控制 unique 的輸入參數，dontenums 在 seajs 裡也可以忽略。隻要心理上邁過那道完美主義設定的檻就好。

2010 年時，總結過性能優化的 robi 法則：

reduce（減少）。減少可減少的。

organize（組織）。妥善組織剩下的。

balance（權衡）。權衡所失與所得。

invent（創新）。這是更高的要求，比如 spdy、chrome 等。

當時忽略了一個重要因素是： 所有這些點，都必須腳踏實地在具體應用場景下去分析、去選擇，要讓場景說話。

因為浏覽器的多樣性，前端的應用場景經常很複雜，性能優化充滿挑戰，也充滿機遇。