從 JavaScript 陣列重談效能優化

JavaScript 陣列去重常出現在前端招募的筆試題裡，例如：

有陣列var arr = ['a', 'b', 'c', '1', 0, 'c', 1, ' ', 1, 0]，請用JavaScript 實作去重函數unqiue，使得unique(arr) 回傳['a', 'b', 'c', '1', 0, 1, '']

當筆試題，考點有二：

1. 正確。別小看這個考點，考慮到 JavaScript 經常要在瀏覽器上運行，在千姿百態的各種瀏覽器環境下要保障一個函數的正確性可不是一件簡單的事，不信你繼續讀完這篇博客。

2. 性能。雖然大部分情況下 JavaScript 語言本身（狹義範疇，不包含 DOM 等延拓）不會導致效能問題，但很不幸這是一道考題，因此面試官們還是會把表現當作一個考點。

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

直覺方案

對於陣列去重，只要寫過程序的，立刻就能得到第一個解法：

 

function unique(arr) {

  var ret = []

( i = 0; i     var item = arr[i]

    if (ret.indexOf(item) === -1) {

  }

 

  return ret

}

直覺往往很可靠，在現代瀏覽器下，上面這個函數很正確，性能也不錯。但前端最大的悲哀也是挑戰之處在於，要支援各種運作環境。在 IE6-8 下，陣列的 indexOf 方法還不存在。直覺方案要稍微改造一下：

 

var indexOf = [].indexOf ?

    function(arr, item) {

 indexOf(arr, item) {

      for (var i = 0; i         if (arr[i] === item) {

 

      }

      return -1

}

 

function unique(arr) {

  var ret = []

 

  for (var i = 0   if (indexOf(ret, item) === -1) {

      ret.push(item)

    }

  }

 

但性能上，兩重循環會讓面試官們看了不爽。

優化方案

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

 

function unique(arr) {

  var ret = []

  var hash = {}

 

  for (var i = 0

 

arr [i]

    var key = typeof(item) + item

    if (hash[key] !== 1) {

   努

  }

 

  return ret

}

核心是建立了一個hash 物件來取代indexOf. 注意在JavaScript 裡，物件的鍵值只能是字串，因此需要var key = typeof(item) + item 來區分數值1 和字串'1' 等情況。

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

1

unique([ new String(1), new Number(1) ])

可以繼續修改程式碼，做到效能和正確性都很好。但往往，這帶來的結果並不好。

真實需求

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

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

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

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

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

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

 

define(function(require, exports) {

  var a = require('./a' )

  var b = require('./b')

  ...

  require('./a').fn(...)

})

上面是一個模組，透過解析函數來解析函數字串，可以拿到模組的依賴數組：['./a', './b', './a']，這個依賴資訊有可能會出現重複字段，因此要做去重。

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

1. 目前有什麼。有的是輸入限制，只需要考慮字串。

2. 究竟要什麼。這個問題比較簡單，希望 unique 方法盡可能快，指標是用 Chrome 偵錯工具中的 Profiles 面板查看指定測試頁面中 unique 方法的耗時，目標是 5ms 以內。

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

SeaJS 下的解決方案

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

 

function unique(arr) {

) {

    obj[item] = 1

  })

 

  return keys(obj)

}

上面的依賴程式碼很重要程式碼：util-lang.js

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

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

 

define(function(require, exports) {

  var a = require('toString')

  var a = require('toString')

  var .

})

「完美」解決方案

上面的測試案例，會呼叫

 

unique([ 'toString', 'hasOwn4Property' ]) // 期待返回[ 'tounique([ 'toString', 'hasOwn' ]) // 期待返回[ 'toString', 'hasn']

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

 

var obj = { toString: 1, hasOwnProperty: 1 }

for (var p in objj) {

console.log(p)

}

在現代瀏覽器下，上面會正確輸出兩個值，但在Old IE 下不會輸出。這是IE 的列舉bug：A safer Object.keys compatibility implementation 「完美」的解決方案如下：

 

var keys = Object.keys || (function () {

    has  ,

        hasDontEnumBug = !{toString:null}.propertyIsEnumerable("toString"),

        Dont          'toLocaleString',

            'valueOf',

       'isPrototypeOf',

            'propertyIsEnumerable',

            'constructor'

🠎 = DontEnums.length;

 

    return function (o) {

        if (typeof o != "object" && typeof o != "function" || o === null)

            throw new TypeError("Object.keys called on a non-object");      for (var name in o) {

            if (hasOwnProperty.call(o, name))

                result.push(name);

        if (hasDontEnumBug) {

            for (var i = 0 ; i                 if (hasOwnProperty.call(o, DontEnums[i]))

     ;

            }   

        }

 

        return

 

        return return result;

    };

})();

除了DontEnums 數組，還可以特別注意hasOwnProperty 的處理方式。 **對於前端來說，要保障「正確」是一件多麼不容易的事。 **