Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

关于去重算法的性能

  最近看到大家普遍喜欢用 forEach + indexOf 去重。虽然我并不排斥对一些简单的数据使用 indexOf 这种方式,但要记住这是时间复杂度 O(n²) 的算法。简单的场景用用也无妨,真正数据量大的场景还是应该规规矩矩地写个 O(n) 复杂度的算法来去重。
  确切地说,forEach + indexOf 去重是和数据有关的。假如有 n 个数据,其中只有 m 个是不重复的,那么这时候这个算法的时间复杂度就应该是 O(n*m)。说它是 O(n²) 是因为 m 如果无法确定通常会根据 n 来取值。但如果 m 是一个常数的话其实这个算法的时间复杂度也可以降到 O(n)。
  下面是使用两种去重算法在各种数据上测试
<script src="http://www.web-tinker.com/share/performance.js"></script>
</script>
<script>
var makeData = function(length, max) {
  var data = [];
  for(var i = 0; i < length; i++) data[i] = Math.random() * max | 0;
  return data;
}

var testWithIndexOf = function(data) {
  var result = [];
  data.forEach(function(e) {
    if(!~result.indexOf(e)) result.push(e);
  });
};

var testWithSet = function(data) {
  var set = new Set;
  var result = [];
  data.forEach(function(e) {
    set.add(e);
  });
  set.forEach(function(e) {
    result.push(e);
  });
};

var data1 = makeData(1E5, 1E1);
var data2 = makeData(1E5, 1E2);
var data3 = makeData(1E5, 1E3);
var data4 = makeData(1E5, 1E4);
</script>
<button>testWithIndexOf(data1)</button>
<button>testWithIndexOf(data2)</button>
<button>testWithIndexOf(data3)</button>
<button>testWithIndexOf(data4)</button>
<button>testWithSet(data1)</button>
<button>testWithSet(data2)</button>
<button>testWithSet(data3)</button>
<button>testWithSet(data4)</button>

  这个结果其实都可以猜出来,IndexOf 的在重复率低的场景中是很慢的,而另一个算法则非常稳定。这里我直接使用了 Set 做测试,但实际上这玩意儿的兼容性还是个坑。不过不用担心,我以前也写过不用 Set 的字典去重。总之算法还是看着选吧,根据业务需求来定制才是做好的。
网名:
3.80.32.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^