87
從 JavaScript 數組去重談性能優化
作者：玉伯
緣由
JavaScript 數組去重經常出現在前端招聘的筆試題裏，比如：
有數組 var arr = ['a', 'b', 'c', '1', 0, 'c', 1, '', 1, 0]，請用 JavaScript 實現去重函數unqiue，使得 unique(arr) 返回 ['a', 'b', 'c', '1', 0, 1, '']
作為筆試題，考點有二：
- 正確。別小看這個考點，考慮到 JavaScript 經常要在瀏覽器上運行，在千姿百態的各種瀏覽器環境下要保障一個函數的正確性可不是一件簡單的事，不信你繼續讀完這篇博客。
- 性能。雖然大部分情況下 JavaScript 語言本身（狹義範疇，不包含 DOM 等延拓）不會導致性能問題，但很不幸這是一道考題，因此麵試官們還是會把性能作為一個考點。
在繼續往下閱讀之前，建議先實現一個自己認為最好的版本。
直覺方案
對於數組去重，隻要寫過程序的，立刻就能得到第一個解法：
function unique(arr) {
var ret = []
for (var i = 0; i < arr.length; i++) {
var item = arr[i]
if (ret.indexOf(item) === -1) {
ret.push(item)
}
}
return ret
}
直覺往往很靠譜，在現代瀏覽器下，上麵這個函數很正確，性能也不錯。但前端最大的悲哀也是挑戰之處在於，要支持各種運行環境。在 IE6-8 下，數組的 indexOf 方法還不存在。直覺方案要稍微改造一下：
var indexOf = [].indexOf ?
function(arr, item) {
return arr.indexOf(item)
} :
function indexOf(arr, item) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === item) {
return i
}
}
return -1
}
function unique(arr) {
var ret = []
for (var i = 0; i < arr.length; i++) {
var item = arr[i]
if (indexOf(ret, item) === -1) {
ret.push(item)
}
}
return ret
}
寫到這一步，正確性已沒問題，但性能上，兩重循環會讓麵試官們看了不爽。
優化方案
一談到優化，往往就是八仙過海、百花齊放。但八仙往往不接地氣，百花則很容易招來臭蟲。數組去重的各種優化方案在此不一一討論，下麵隻說最常用效果也很不錯的一種。
function unique(arr) {
var ret = []
var hash = {}
for (var i = 0; i < arr.length; i++) {
var item = arr[i]
var key = typeof(item) + item
if (hash[key] !== 1) {
ret.push(item)
hash[key] = 1
}
}
return ret
}
核心是構建了一個 hash 對象來替代 indexOf. 注意在 JavaScript 裏，對象的鍵值隻能是字符串，因此需要 var key = typeof(item) + item 來區分數值 1 和字符串 '1' 等情況。
但優化真的很容易帶來坑，比如上麵的實現，對下麵這種輸入就無法判斷：
unique([ new String(1), new Number(1) ])
可以繼續修改代碼，做到性能和正確性都很好。但往往，這帶來的結果並不好。
真實需求
寫到這裏，這篇博客才算進入正題。程序員心中都會有一些夢想，比如寫出又通用性能又好的普適函數。這種夢想是讓程序員變得卓越的重要內驅力，但倘若不加以控製，也很容易走入迷途。
回到性能優化。這年頭有各種各樣優化，核心係統、數據庫、網絡、前端等等，所有這些優化，都必須回答下麵這個問題：
- 當前有什麼。在什麼場景下進行優化，場景下有哪些具體限製。理清限製很重要，限製往往帶來自由。
- 究竟要什麼。優化的目的是什麼。是提高穩定性，還是增大吞吐量，抑或減少用戶等待時間。在回答這個問題之前，優化都是徒勞。對這個問題的準確回答，能為優化帶來具體可測量的參數，這樣優化才有目標。
- 可以放棄什麼。魚與熊掌不可兼得。優化的本質是在具體場景下的取舍、權衡。什麼都不願意放棄的話，優化往往會舉步維艱。
寫這篇博客，不是為了解答一到筆試題，這道筆試題有點無聊。寫這篇博客的原始驅動力是因為最近在做 SeaJS 的性能調優，其中有一個需求是：
define(function(require, exports) {
var a = require('./a')
var b = require('./b')
...
require('./a').fn(...)
})
上麵是一個模塊，通過解析函數字符串，可以拿到模塊的依賴數組：['./a', './b', './a']，這個依賴信息有可能會出現重複字段，因此要做去重。
針對這個具體場景，來回答上麵三個問題：
- 當前有什麼。有的是輸入限製，隻需要考慮字符串。
- 究竟要什麼。這個問題比較簡單，希望 unique 方法盡可能快，指標是用 Chrome 調試工具中的 Profiles 麵板查看指定測試頁麵中 unique 方法的耗時，目標是 5ms 以內。
- 可以放棄什麼。隻需處理字符串，其他類型的都可以不支持。談到放棄往往很有意思，這個問題不那麼簡單，接下來再說。
SeaJS 下的解決方案
一旦分析清楚了具體場景，解決方案就相對簡單：
function unique(arr) {
var obj = {}
forEach(arr, function(item) {
obj[item] = 1
})
return keys(obj)
}
上麵的代碼依賴 forEach 和 keys，離不開上下文環境（環境很重要很重要），完整代碼：util-lang.js
上麵這個方案，無論從代碼體積、正確性、還是各種瀏覽器下的綜合性能來考量，都很不錯。
直到有一天出現這樣一個測試用例：
define(function(require, exports) {
var a = require('toString')
var b = require('hasOwnProperty')
...
})
“完美”解決方案
上麵的測試用例，會調用
unique([ 'toString', 'hasOwnProperty' ]) // 期待返回 [ 'toString', 'hasOwnProperty' ]
IE 有各種各樣的 bug，下麵是不怎麼著名但真實存在的一個：
var obj = { toString: 1, hasOwnProperty: 1 }
for (var p in obj) {
console.log(p)
}
在現代瀏覽器下，上麵會正確輸出兩個值，但在 Old IE 下不會輸出。這是 IE 的枚舉 bug：A safer Object.keys compatibility implementation “完美”的解決方案如下：
var keys = Object.keys || (function () {
var hasOwnProperty = Object.prototype.hasOwnProperty,
hasDontEnumBug = !{toString:null}.propertyIsEnumerable("toString"),
DontEnums = [
'toString',
'toLocaleString',
'valueOf',
'hasOwnProperty',
'isPrototypeOf',
'propertyIsEnumerable',
'constructor'
],
DontEnumsLength = DontEnums.length;
return function (o) {
if (typeof o != "object" && typeof o != "function" || o === null)
throw new TypeError("Object.keys called on a non-object");
var result = [];
for (var name in o) {
if (hasOwnProperty.call(o, name))
result.push(name);
}
if (hasDontEnumBug) {
for (var i = 0; i < DontEnumsLength; i++) {
if (hasOwnProperty.call(o, DontEnums[i]))
result.push(DontEnums[i]);
}
}
return result;
};
})();
除了 DontEnums 數組，還可以特別注意 hasOwnProperty 的處理方式。對於前端來說，要保障“正確”是一件多麼不容易的事。
注意：行文至此，已經不是在討論 unique 的實現問題，比如上麵實際上在討論的是 Object.keys 的實現問題。
我可以放棄什麼
我有什麼、我要什麼、我可以放棄什麼，這其實是馬雲在回答內網一個神貼時的回複，那個神貼是我發的，因此馬雲這幾句話讓我印象非常深刻。
優化的本質是做減法，做減法最困難的是選擇放棄。
對於 SeaJS 來說，真的需要上麵那個“完美”的解決方案嗎？
程序員心中的完美主義、理想主義情結曾一度讓我非常不能容忍代碼中有 “bug” 存在。
可是，大家都懂的：
還有紅樓夢……
知道道理容易，比如很懷念小時候的《思想品德》課，要扶老奶奶過馬路、要誠實等等，絕大部分人都懂得這些道理，可做到的，發現沒幾個。
讓場景說話
如果你聽了我上麵一通知易行難的扯淡就決定趕緊“放棄”，那也有悖程序員的職業素養。
依舊得回到具體場景。在 SeaJS 裏，適當調整代碼邏輯：
// Remove duplicated dependencies mod.dependencies = unique(resolve(meta.dependencies))
上麵的代碼，能保證傳給 unique 方法的輸入是：
[ 'https://path/to/a.js', 'https://path/to/toString.js', 'https://path/to/hasOwnProperty.js' ]
因此 DontEnums bug 在 SeaJS 裏通過這麼一調整就不存在了。
仔細分析，控製好輸入，會讓代碼更簡單同時可靠。
其實不控製 unique 的輸入參數，DontEnums 在 SeaJS 裏也可以忽略。隻要心理上邁過那道完美主義設置的檻就好。
小結
2010 年時，總結過性能優化的 ROBI 法則：
- Reduce（減少）。減少可減少的。
- Organize（組織）。妥善組織剩下的。
- Balance（權衡）。權衡所失與所得。
- Invent（創新）。這是更高的要求，比如 SPDY、Chrome 等。
當時忽略了一個重要因素是： 所有這些點，都必須腳踏實地在具體應用場景下去分析、去選擇，要讓場景說話。
因為瀏覽器的多樣性，前端的應用場景經常很複雜，性能優化充滿挑戰，也充滿機遇。
最後更新：2017-04-03 07:57:03