从 JavaScript 数组去重谈性能优化

分享到

发布于2013-6-27

缘由

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' 等情况。

但优化真的很容易带来坑，比如上面的实现，对下面这种输入就无法判断：

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 的处理方式。**对于前端来说，要保障“正确”是一件多么不容易的事。

注意：行文至此，已经不是在讨论 unique 的实现问题，比如上面实际上在讨论的是 Object.keys 的实现问题。

1、我可以放弃什么

我有什么、我要什么、我可以放弃什么，这其实是马云在回答内网一个神贴时的回复，那个神贴是我发的，因此马云这几句话让我印象非常深刻。

2、优化的本质是做减法，做减法最困难的是选择放弃。

对于 SeaJS 来说，真的需要上面那个“完美”的解决方案吗？

程序员心中的完美主义、理想主义情结曾一度让我非常不能容忍代码中有 “bug” 存在。

可是，大家都懂的：

还有红楼梦……

知道道理容易，比如很怀念小时候的《思想品德》课，要扶老奶奶过马路、要诚实等等，绝大部分人都懂得这些道理，可做到的，发现没几个。

让场景说话

如果你听了我上面一通知易行难的扯淡就决定赶紧“放弃”，那也有悖程序员的职业素养。

依旧得回到具体场景。在 SeaJS 里，适当调整代码逻辑：

// Remove duplicated dependencies
mod.dependencies = unique(resolve(meta.dependencies))

上面的代码，能保证传给 unique 方法的输入是：

[
  'http://path/to/a.js',
  'http://path/to/toString.js',
  'http://path/to/hasOwnProperty.js'
]

因此 DontEnums bug 在 SeaJS 里通过这么一调整就不存在了。

仔细分析，控制好输入，会让代码更简单同时可靠。

其实不控制 unique 的输入参数，DontEnums 在 SeaJS 里也可以忽略。只要心理上迈过那道完美主义设置的槛就好。

小结

1. Reduce（减少）。减少可减少的。

2. Organize（组织）。妥善组织剩下的。

3. Balance（权衡）。权衡所失与所得。

4. Invent（创新）。这是更高的要求，比如 SPDY、Chrome 等。

当时忽略了一个重要因素是：所有这些点，都必须脚踏实地在具体应用场景下去分析、去选择，要让场景说话。

因为浏览器的多样性，前端的应用场景经常很复杂，性能优化充满挑战，也充满机遇。