最近看到大家普遍喜欢用 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 的字典去重。总之算法还是看着选吧，根据业务需求来定制才是做好的。