湖北赖子麻将下载|赖子麻将中心下载
主頁 > 知識庫 > 網頁基礎 > Javascript/Ajax >
欄目列表

JavaScript 數組去重談性能優化

來源:中國IT實驗室 作者:佚名 發表于:2013-02-16 17:24  點擊:
JavaScript 數組去重經常出現在前端招聘的筆試題里,比如: 有數組 var arr = [a, b, c, 1, 0, c, 1, , 1, 0],請用 JavaScript 實現去重函數 unqiue,使得 unique(arr) 返回 [a, b, c, 1, 0, 1, ] 作為筆試題,考點有二: 1. 正確。別小看這個考點,考慮到
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 = []
    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' 等情況。
    但優化真的很容易帶來坑,比如上面的實現,對下面這種輸入就無法判斷:
    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) {
    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 的處理方式。**對于前端來說,要保障“正確”是一件多么不容易的事。**

    有幫助
    (3)
    50%
    沒幫助
    (3)
    50%
    湖北赖子麻将下载 福彩3d732试机号历史记录 视频营销 赚钱 陕西快乐十分前三组走势 14场胜负现场直播 喜乐彩中奖规则 拼多多怎么做单赚钱 30选5中奖规则 投资电影哪里赚钱 黑龙江p62带连线走势图 167组选的关系