Javascript集与数组性能

xmakbtuz  于 2023-03-06  发布在  Java
关注(0)|答案(7)|浏览(178)

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

JavaScript

7条答案

按热度按时间
k2fxgqgv

k2fxgqgv1#

好的，我已经测试了从数组和集合中添加、迭代和删除元素。我运行了一个“小”测试，使用10000个元素，和一个“大”测试，使用100000个元素。以下是结果。

向集合添加元素

看起来.push数组方法比.add集合方法快大约4倍，无论添加的元素数量是多少。

迭代和修改集合中的元素

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

从集合中删除元素

这就是有趣的地方，我使用for循环和.splice的组合从数组中删除一些元素，使用for of和.delete从集合中删除一些元素。从集合中删除项目的速度大约是原来的三倍（2.6ms对7.1ms）但是对于其中花费1955.1ms来从阵列中移除项目而仅花费83.6ms来从集合中移除项目的“大”测试来说情况发生了剧烈变化，快了23倍。

结论

对于10k个元素，两个测试的运行时间相当（数组：16.6 ms，设置：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.")
赞(0）分享  回复(0）举报  2023-03-06
irlmq6kh

irlmq6kh2#

意见：

  • 集合操作可以理解为执行流中的快照。
  • 我们面前不是一个最终的替代者。
  • *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的has方法和数组indexOf：
数组/索引（0.281毫秒）|设置/具有（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.612毫秒）|设置/添加（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没有本机方法，因此需要一个外部函数。
数组/从数组中删除（0.356毫秒）|设置/删除（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' );

阅读完整文章here

赞(0）分享  回复(0）举报  2023-03-06
g52tjvyc

g52tjvyc3#

只有属性查找，很少或零写入

如果属性查找是您主要关心的问题，这里有一些数字。
JSBench测试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速度降低〈-1.29%
  • obj[target]〈-最快

Map

  • map.has(target)速度降低〈-2.94%

结果来自2021年1月，Chrome 87

  • 欢迎使用其他浏览器搜索结果，请更新此答案。

您可以使用this spreadsheet制作一个漂亮的屏幕截图。*

  • JSBench测试源自Zargold的答案 *
赞(0）分享  回复(0）举报  2023-03-06
myss37ts

myss37ts4#

对于您的问题的迭代部分，我最近运行了这个测试，发现Set的性能远远超过10，000项的Array（大约10倍的操作可能发生在同一时间段内）。并且取决于浏览器在同类测试中击败或丢失Object. hasOwnProperty。另一个有趣的点是对象没有官方保证的顺序，而JavaScript中的Set是作为有序集实现的，并保持插入顺序。
Set和Object都有自己的"has"方法，执行起来似乎是O（1），但取决于浏览器的实现，单个操作可能需要更长或更快的时间。似乎大多数浏览器在Object中实现key比Set.has（）更快。即使是Object. hasOwnProperty（包括对key的额外检查）也比Set.has（）快5%，至少对我来说，在Chrome v86上是这样。

  • 一个月一次 *

更新日期：2020年11月11日：https://jsbench.me/irkhdxnoqa/2
如果您想在不同的浏览器/环境下运行自己的测试。在此期间（当此测试运行时）：Chrome V8显然只针对对象进行了优化：以下是Chrome v86在2020年11月的快照。

  1. For循环：104167.14操作/秒‡最慢0.22%
  2. Array.includes:每秒运算次数‡ 0.24%每秒运算次数是for循环的1.07倍（两者都是9k次迭代）
    1.对于反循环：218074.48操作/秒‡ 0.59%操作/秒比非反向阵列高1.96倍。包括（9k次迭代）
  3. Set.has：154744804.61操作/秒‡ 1.88%709.6x比for循环反转的操作/秒多（由于目标位于右侧，因此仅需1k次迭代）
  4. hasOwnProperty：161399953.02次操作/秒‡ 1.81%操作/秒比Set.has高1.043倍
  5. key in myObject：每秒883055194.54次操作‡ 2.08% ...每秒操作数比myObject.hasOwnProperty高5倍。
    更新日期：2022年11月10日：今天我在Safari和Chrome上重新运行了同样的测试（在我的原始图像2年后），得到了一些有趣的结果：TLDR Set在两种浏览器上都比key in Object快，甚至快得多。Chrome还在某种程度上显著优化了Array.includes，使其与Object/Set查找时间处于相同的速度范围内（而for循环要多花1000+倍的时间来完成）。
    对于Safari来说，Set明显比key in Object快，而Object. hasOwnProperty几乎不在同一速度范围内。所有数组变体（循环/包含）都比set/object查找慢得多。
    2022年11月10日快照：在Safari v16.1上测试的每秒操作数（更高=更快）：
  • 共计1 550 924 292.31英镑
  • key in myObject：942，192，599.63（速度降低39.25%，即使用Set时，每秒可以多执行约1.6倍的操作
  • myObject.hasOwnProperty(key)：21，363，224.51（慢98.62%）也就是说，您可以多执行大约72.6倍的Set. has操作，因为hasOwnProperty检查在1秒内完成。
  • Reverse For循环619，876.17 ops/s（目标是10，000次中的9，000次-因此reverse for循环意味着迭代次数仅为1，000次，而不是9，000次），这意味着即使您知道项的位置是有利的，您也可以执行比循环检查多2502倍的Set查找。
  • for循环：137，434次运算/秒：正如预期的那样，甚至更慢，但令人惊讶的是，并没有慢多少：包含1/9循环迭代的反向for循环仅比for循环快约4.5倍。
  • Array.includes(target) 111，076 ops/s比for循环手动检查目标要慢一点，您可以为每次include检查手动执行1.23次检查。

在Chrome浏览器上www.example.com 2022年11月10日：v107.0.5304.87它们现在几乎相等了。（虽然预期的行为是set将优于Object，因为set与object的选项可能性更小，以及这是Safari中的行为。）值得注意的是，Array. includes显然在Chrome（v8）中至少针对此类测试进行了显著优化： It is no longer true that Set significantly underperforms Object in operation: they now nearly tie. (Though the expected behavior is that set would outperform Object in due to the smaller possible of options with a set vs an object and how this is the behavior in Safari.) Notably impressive Array.includes has apparently been significantly optimized in Chrome (v8) for at least this type of test:

  • Object in完成792894327.81次操作/秒‡ 2.51%最快
  • Set.prototype.has完成790523864.11次操作/秒‡ 2.22%最快
  • Array.prototype.includes完成679373215.29次操作/秒‡速度慢1.82% 14.32%
  • Object.hasOwnProperty已完成154217006.71次操作/秒‡速度降低1.31%和80.55%
  • for loop完成103015.26操作/秒+慢0.98% 99.99%

赞(0）分享  回复(0）举报  2023-03-06
7z5jn7bk

7z5jn7bk5#

我的观察结果是，Set总是更好，但对于大型数组来说，它有两个缺陷：
a）从数组创建集合必须在for循环中完成，循环长度为预先缓存的长度。

  • 慢速（例如18毫秒）* new Set(largeArray)
  • 快速（例如6毫秒）* 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/
对于与具有40，000个元素的difference()、intersection()、union()和uniq()（+其迭代同伴等）的实际比较

赞(0）分享  回复(0）举报  2023-03-06
8yparm6h

8yparm6h6#

让我们考虑一下你想要维护一组唯一值的情况，你可以使用数组模拟几乎所有的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中收集的数据，用于一个普通用例（see benchmarking code）：

正如预期的那样，我们看到了一个O（n）的加速集：

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

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

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

赞(0）分享  回复(0）举报  2023-03-06
zvokhttg

zvokhttg7#

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

这三个一万件物品的操作给了我：

set: 7.787ms
array: 2.388ms
赞(0）分享  回复(0）举报  2023-03-06
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com