Javascript设置与阵列性能

Question

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

Answer 1

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

将元素添加到集合中

无论添加的元素数量如何,.push数组方法似乎比.addset方法快4倍.

迭代和修改集合中的元素

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

从集合中删除元素

现在这是它变得有趣的地方.我使用for循环的组合并.splice从数组中删除一些元素,我使用for of并.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.")

Answer 2

意见:

• 设置操作可以理解为执行流中的快照.
• 我们不是一个明确的替代品.
• 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' );

阅读完整的文章在这里

Answer 3

仅属性查找，很少或零写入

如果您主要关心的是房产查找，这里有一些数字。

JSBench 测试

• v2：https ://jsbench.me/3pkjlwzhbr/2
• v1：https ://jsbench.me/3pkjlwzhbr/1

// https://jsbench.me/3pkjlwzhbr/1
// https://docs.google.com/spreadsheets/d/1WucECh5uHlKGCCGYvEKn6ORrQ_9RS6BubO208nXkozk/edit?usp=sharing
// JSBench forked from https://jsbench.me/irkhdxnoqa/2

var theArr = Array.from({ length: 10000 }, (_, el) => el)
var theSet = new Set(theArr)
var theObject = Object.assign({}, ...theArr.map(num => ({ [num]: true })))
var theMap = new Map(theArr.map(num => [num, true]))

var theTarget = 9000


// Array

function isTargetThereFor(arr, target) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}
function isTargetThereForReverse(arr, target) {
  const len = arr.length
  for (let i = len; i > 0; i--) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}

function isTargetThereIncludes(arr, target) {
  return arr.includes(target)
}

// Set

function isTargetThereSet(numberSet, target) {
  return numberSet.has(target)
}

// Object 

function isTargetThereHasOwnProperty(obj, target) {
  return obj.hasOwnProperty(target)
}
function isTargetThereIn(obj, target) {
  return target in obj
}
function isTargetThereSelectKey(obj, target) {
  return obj[target]
}

// Map

function isTargetThereMap(numberMap, target) {
  return numberMap.has(target)
}

大批

• for环形
• for循环（反转）
• array.includes(target)

放

• set.has(target)

目的

• obj.hasOwnProperty(target)
• target in obj <-最快
• obj[target] <-最快

地图

• map.has(target)

2024 年 1 月的结果，Chrome 121

这个结果有趣的是，速度map.has突然变慢到 的相同速度set.has。（评论）

2022 年 2 月的结果，Chrome 98

2021 年 1 月的结果，Chrome 87

来自其他浏览器的结果是最受欢迎的，请更新此答案。
您可以使用此电子表格制作精美的屏幕截图。

JSBench 测试源自Zargold 的答案。

Answer 4

让我们考虑一下您想要维护一组唯一值的情况。您可以使用数组模拟几乎所有 Set 操作：添加、删除、具有、清除和大小。

我们也可以实现迭代，但请注意，它的行为与 Set 不完全相同。您可以在迭代期间安全地修改 Set，而无需跳过元素，但数组则不然。因此，对于所有用例来说，这种比较并不十分公平。

/** Set implemented using an array internally */
class ArraySet{
    constructor(){
        this._arr = [];
    }
    add(value){
        if (this._arr.indexOf(value) === -1)
            this._arr.push(value);
        return this;
    }
    delete(value){
        const idx = this._arr.indexOf(value);
        if (idx !== -1){
            this._arr.splice(idx,1);
            return true;
        }
        return false;
    }
    has(value){
        return this._arr.indexOf(value) !== -1;
    }
    clear(){
        this._arr.length = 0;
    }
    // Note: iterating is not safe from modifications
    values(){   
        return this._arr.values();
    }
    [Symbol.iterator](){
        return this._arr[Symbol.iterator]();
    }
}

虽然 Set 具有更好的算法复杂性（O(1) 与 ArraySet 的 O(n) 操作相比），但它在维护其内部树/哈希方面可能有更多的开销。Set 的开销达到什么程度才值得？以下是我从平均用例的 NodeJS v18.12 基准测试中收集的数据（请参阅基准测试代码）：

正如预期的那样，我们看到 Set 对于许多元素具有 O(n) 算法优势。至于开销：

• size：等速
• add：出现了一个有趣的模式，其中集合的性能根据其大小而波动。一般来说，数组对于 < 33 个元素来说会更快，而 Set 对于 > 52 个元素总是更快。
• delete：对于 < 10 个元素，数组速度更快
• has：对于 < 20 个元素，数组速度更快
• values：设置总是更快
• iterator（例如for-of循环）：设置总是更快

在实践中，您可能不会创建自己的ArraySet类，而只会内联您感兴趣的特定操作。假设数组操作是内联的，性能会如何变化？

结果几乎相同，只是现在 Array 的迭代性能有所提高。内联for-of循环（不经过ArraySet包装类）现在总是比 Set 更快。迭代values器的速度大致相等。

Answer 5

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

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

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

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

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

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

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

Answer 6

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

Set 和 Object 都有它们的“has”方法，其执行方式似乎可以摊销为 O(1)，但取决于浏览器的实现，单个操作可能需要更长或更短的时间。似乎大多数浏览器在 Object 中实现 key 的速度比 Set.has() 快。甚至 Object.hasOwnProperty 包括对密钥的额外检查，至少比我在 Chrome v86 上的 Set.has() 快约 5%。

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1

更新：11/11/2020：https ://jsbench.me/irkhdxnoqa/2

如果您想使用不同的浏览器/环境运行自己的测试。

同样，我将添加一个基准，用于将项目添加到数组与设置和删除。