Javascript设置与阵列性能




arrays performance (4)

意见

  • 设置操作可以理解为执行流中的快照。
  • 我们不是一个明确的替代品。
  • Set类 的元素没有可访问的索引。
  • Set类 是一个 Array类 补充,在我们需要存储应用基本添加,删除,检查和迭代操作的集合的场景中非常有用。

我分享一些性能测试。 尝试打开控制台并复制下面的代码。

创建一个数组(125000)

var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000

1.查找索引

我们比较了Set with Array indexOf的has方法:

数组/ indexOf (0.281ms)| 设置/ (0.053ms)

// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );

2.添加新元素

我们分别比较Set和Array对象的add和push方法:

阵列/ (1.612ms)| 设置/ 添加 (0.006ms)

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );

console.info( arr.length ); // 125001
console.info( set.size ); // 125001

3.删除元素

删除元素时,我们必须记住,Array和Set不会在相同的条件下启动。 Array没有本机方法,因此需要外部函数。

Array / deleteFromArr (0.356ms)| 设置/ 删除 (0.019ms)

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );

阅读完整的文章

这可能是因为集合对Javascript来说相对较新,但是我无法在StackO或其他任何地方找到一篇文章来讨论Javascript中两者之间的性能差异。 那么,两者之间在性能方面有什么不同? 具体来说,当涉及删除,添加和迭代时。


好的,我测试过添加,迭代和删除数组和集合中的元素。 我运行了一个“小”测试,使用10万个元素和一个“大”测试,使用10万个元素。 结果如下。

将元素添加到集合中

看起来 .push 数组方法比 .add set方法快4倍,无论添加的元素数量是多少。

迭代和修改集合中的元素

对于测试的这一部分,我使用 for 循环迭代数组,并使用 for of 循环遍历集合。 再次,迭代数组更快。 这一次似乎是指数级的,因为它在“小”测试期间花了两倍长,在“大”测试期间花费了近四倍。

从集合中删除元素

现在这是它变得有趣的地方。 我使用了 for 循环和 .splice 的组合来从数组中删除一些元素,我使用和 .delete 来从集合中删除一些元素。 对于“小”测试,从集合中删除项目的速度提高了大约三倍(2.6毫秒vs 7.1毫秒),但“大”测试的情况发生了巨大变化,只需要1955.1毫秒从阵列中删除项目耗时83.6毫秒将它们从集合中移除,速度提高了23倍。

结论

在10k个元素中,两个测试都运行相当的时间(数组:16.6毫秒,设置:20.7毫秒),但在处理100k元素时,该集合是明显的赢家(数组:1974.8毫秒,设置:83.6毫秒),但仅仅是因为删除操作。 否则阵列更快。 我不知道为什么会这样。

我玩了一些混合场景,其中创建并填充了一个数组,然后将其转换为一个集合,其中一些元素将被删除,然后该集合将被重新转换为数组。 虽然这样做会比删除数组中的元素提供更好的性能,但传输到集合和从集合传输所需的额外处理时间超过了填充数组而不是集合的增益。 最后,只处理一组更快。 尽管如此,有一个有趣的想法是,如果选择使用数组作为一些没有重复数据的大数据的数据集合,那么如果需要在一个数据中删除许多元素,那么它可能是有利的性能。操作,将数组转换为集合,执行删除操作,并将集合转换回数组。

数组代码:

var timer = function(name) {
  var start = new Date();
  return {
    stop: function() {
      var end = new Date();
      var time = end.getTime() - start.getTime();
      console.log('Timer:', name, 'finished in', time, 'ms');
    }
  }
};

var getRandom = function(min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];

var genLastName = function() {
  var index = Math.round(getRandom(0, lastNames.length - 1));
  return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
  var index = Math.round(getRandom(0, sex.length - 1));
  return sex[index];
};

var Person = function() {
  this.name = genLastName();
  this.age = Math.round(getRandom(0, 100))
  this.sex = "Male"
};

var genPersons = function() {
  for (var i = 0; i < 100000; i++)
    personArray.push(new Person());
};

var changeSex = function() {
  for (var i = 0; i < personArray.length; i++) {
    personArray[i].sex = genSex();
  }
};

var deleteMale = function() {
  for (var i = 0; i < personArray.length; i++) {
    if (personArray[i].sex === "Male") {
      personArray.splice(i, 1)
      i--
    }
  }
};

var t = timer("Array");

var personArray = [];

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personArray.length + " persons.")

设置代码:

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var getRandom = function (min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];

var genLastName = function() {
    var index = Math.round(getRandom(0, lastNames.length - 1));
    return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
    var index = Math.round(getRandom(0, sex.length - 1));
    return sex[index];
};

var Person = function() {
	this.name = genLastName();
	this.age = Math.round(getRandom(0,100))
	this.sex = "Male"
};

var genPersons = function() {
for (var i = 0; i < 100000; i++)
	personSet.add(new Person());
};

var changeSex = function() {
	for (var key of personSet) {
		key.sex = genSex();
	}
};

var deleteMale = function() {
	for (var key of personSet) {
		if (key.sex === "Male") {
			personSet.delete(key)
		}
	}
};

var t = timer("Set");

var personSet = new Set();

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personSet.size + " persons.")


我的观察是,对于大型数组而言,Set总是更好,有两个陷阱:

a)从数组创建集合必须在具有预先长度的 for 循环中完成。

慢(例如 new Set(largeArray)

快速(例如6ms) const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) } const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

b)迭代可以以相同的方式完成,因为它也比循环更快...

https://jsfiddle.net/0j2gkae7/5/

与40.000元素的 difference()intersection()union()uniq() (+他们的iteratee伴侣等)的真实生活比较


console.time("set")
var s = new Set()
for(var i = 0; i < 10000; i++)
  s.add(Math.random())
s.forEach(function(e){
  s.delete(e)
})
console.timeEnd("set")
console.time("array")
var s = new Array()
for(var i = 0; i < 10000; i++)
  s.push(Math.random())
s.forEach(function(e,i){
  s.splice(i)
})
console.timeEnd("array")

10K项目的这三项操作给了我:

set: 7.787ms
array: 2.388ms






iteration