Javascript 集与数组性能

Javascript Set vs. Array performance

提问by snowfrogdev

It maybe because Sets are relatively new to Javascript but I haven't been able to find an article, on StackO or anywhere else, that talks about the performance difference between the two in Javascript. So, what is the difference, in terms of performance, between the two? Specifically, when it comes to removing, adding and iterating.

这可能是因为 Sets 对 Javascript 来说相对较新，但我无法在 StackO 或其他任何地方找到一篇文章来讨论 Javascript 中两者之间的性能差异。那么，就性能而言，两者之间有什么区别？具体来说，当涉及到删除、添加和迭代时。

回答by snowfrogdev

Ok, I have tested adding, iterating and removing elements from both an array and a set. I ran a "small" test, using 10 000 elements and a "big" test, using 100 000 elements. Here are the results.

好的，我已经测试了从数组和集合中添加、迭代和删除元素。我使用 10 000 个元素进行了“小”测试，并使用 100 000 个元素进行了“大”测试。这是结果。

Adding elements to a collection

向集合中添加元素

It would seem that the .pusharray method is about 4 times faster than the .addset method, no matter the number of elements being added.

无论添加多少元素，.pusharray 方法似乎比.addset 方法快 4 倍。

Iterating over and modifying elements in a collection

迭代和修改集合中的元素

For this part of the test I used a forloop to iterate over the array and a for ofloop to iterate over the set. Again, iterating over the array was faster. This time it would seem that it is exponentially so as it took twice as long during the "small" tests and almost four times longer during the "big" tests.

对于测试的这一部分，我使用了一个for循环来迭代数组和一个for of循环来迭代集合。同样，对数组的迭代速度更快。这一次似乎是指数级的，因为在“小”测试期间花费了两倍的时间，在“大”测试期间花费的时间几乎是四倍。

Removing elements from a collection

从集合中删除元素

Now this is where it gets interesting. I used a combination of a forloop and .spliceto remove some elements from the array and I used for ofand .deleteto remove some elements from the set. For the "small" tests, it was about three times faster to remove items from the set (2.6 ms vs 7.1 ms) but things changed drastically for the "big" test where it took 1955.1 ms to remove items from the array while it only took 83.6 ms to remove them from the set, 23 times faster.

现在这就是它变得有趣的地方。我使用了for循环的组合并.splice从数组中删除了一些元素，并使用了for of并.delete从集合中删除了一些元素。对于“小”测试，从集合中删除项目的速度大约快三倍（2.6 毫秒对 7.1 毫秒），但“大”测试的情况发生了巨大变化，从数组中删除项目需要 1955.1 毫秒，而它只需要花了 83.6 毫秒将它们从集合中移除，快了 23 倍。

Conclusions

结论

At 10k elements, both tests ran comparable times (array: 16.6 ms, set: 20.7 ms) but when dealing with 100k elements, the set was the clear winner (array: 1974.8 ms, set: 83.6 ms) but only because of the removing operation. Otherwise the array was faster. I couldn't say exactly why that is.

在 10k 个元素时，两个测试的运行时间相当（数组：16.6 毫秒，集合：20.7 毫秒）但在处理 100k 个元素时，集合是明显的赢家（数组：1974.8 毫秒，集合：83.6 毫秒）但仅仅是因为删除手术。否则阵列更快。我说不出确切的原因。

I played around with some hybrid scenarios where an array was created and populated and then converted into a set where some elements would be removed, the set would then be reconverted into an array. Although doing this will give much better performance than removing elements in the array, the additional processing time needed to transfer to and from a set outweighs the gains of populating an array instead of a set. In the end, it is faster to only deal with a set. Still, it is an interesting idea, that if one chooses to use an array as a data collection for some big data that doesn't have duplicates, it could be advantageous performance wise, if there is ever a need to remove many elements in one operation, to convert the array to a set, perform the removal operation, and convert the set back to an array.

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

Array code:

数组代码：

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.")

Set code:

设置代码：

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.")

回答by Daniel Eduardo Delgado Diaz

OBSERVATIONS:

• Set operations can be understood as snapshots within the execution stream.
• We are not before a definitive substitute.
• The elements of a Set classhave no accessible indexes.
• Set classis an Array classcomplement, useful in those scenarios where we need to store a collection on which to apply basic addition, Deletion, checking and iteration operations.

观察：

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

I share some test of performance. Try to open your console and copypaste the code below.

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

Creating an array (125000)

创建数组 (125000)

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

1. Locating an Index

1. 定位索引

We compared the has method of Set with Array indexOf:

我们将 Set 的 has 方法与 Array indexOf 进行了比较：

Array/indexOf(0.281ms) | Set/has(0.053ms)

数组/ 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. Adding a new element

2. 添加新元素

We compare the add and push methods of the Set and Array objects respectively:

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

Array/push(1.612ms) | Set/add(0.006ms)

数组/推送(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. Deleting an element

3. 删除元素

When deleting elements, we have to keep in mind that Array and Set do not start under equal conditions. Array does not have a native method, so an external function is necessary.

在删除元素时，我们必须记住 Array 和 Set 不是在相等的条件下开始的。Array 没有本地方法，因此需要外部函数。

Array/deleteFromArr(0.356ms) | Set/remove(0.019ms)

数组/ 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' );

Read the full article here

在此处阅读全文

回答by sebilasse

My observation is that a Set is always better with two pitfalls for large arrays in mind :

我的观察是，考虑到大型数组的两个陷阱，Set 总是更好：

a) The creation of Sets from Arrays must be done in a forloop with a precached length.

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

slow (e.g. 18ms)new Set(largeArray)

慢（例如 18 毫秒）new Set(largeArray)

fast (e.g. 6ms)const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

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

b) Iterating could be done in the same way because it is also faster than a for ofloop ...

b）迭代可以用同样的方式完成，因为它也比for of循环更快......

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

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

for a real life comparison to difference(), intersection(), union()and uniq()( + their iteratee companions etc.) with 40.000 elements

与difference(), intersection(),union()和uniq()(+ 他们的 iteratee 伙伴等) 与 40.000 个元素的现实生活比较

回答by Zargold

I recently ran this test and found that Set much outperformed an Array of 1000 items (around 10x the operations could happen in the same timeframe). And depending on the browser either beat or lost to Object.hasOwnProperty in a like for like test.

我最近运行了这个测试，发现 Set 的性能远远优于包含 1000 个项目的 Array（大约 10 倍的操作在同一时间范围内发生）。并且取决于浏览器在类似测试中击败或输给 Object.hasOwnProperty。

Both Set and Object have their "has" method performing in what seems to be amortized to O(1), but depending on the browser's implementation a single operation could take longer or faster.

Set 和 Object 都有它们的“has”方法，其执行方式似乎可以摊销为 O(1)，但取决于浏览器的实现，单个操作可能需要更长或更短的时间。

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1In case you want to run your own tests with different browsers/environments.

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1如果您想使用不同的浏览器/环境运行自己的测试。

回答by jessh

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")

Those three operations on 10K items gave me:

对 10K 项的这三个操作给了我：

set: 7.787ms
array: 2.388ms