javascript 数组 输出-你知道在 Javascript 中合并链表最快的方法是什么吗?

2023-08-29 0 2,672 百度已收录

如果要组合具有数千个元素的字段,使用 arr1.push(...arr2) 可以比 arr1=arr1.concat(arr2) 节省时间。 如果你想更快,你甚至可以编写自己的函数来实现组合字段的功能。

等一下...用 .concat 组合 15,000 个字段需要多长时间?

最近,我们的一位用户抱怨说,当他使用 UI-licious 测试他们的 UI 时javascript 数组 输出,速度明显变慢。 一般来说,每次I.clickI.fill

一、see命令大约需要1秒才能完成(后期处理,比如截图),现在需要40多秒才能完成,所以平时20分钟就能完成的测试现在需要几个小时才能完成,这严重减慢了他们的部署进程。

我快速设置了计时器并锁定了导致速度变慢的代码部分,但当我找到罪魁祸首时,我大吃一惊:

arr1=arr1.concat(arr2)

字段的 .concat 方法。

允许在编写测试时使用 I.click("Login") 这样的简单命令,而不是像 I.click("#login-btn") 这样的 CSS 或 XPATH 选择器,UI-licious 基于网站的语义、可访问性属性,以及各种流行但非标准的模式,动态代码分析(模式)用于分析 DOM 树,以确定测试什么以及如何测试网站。 那些 .concat 操作是用来压平 DOM 树进行解析的,但是当 DOM 树很大很深时,性能就很糟糕,这就是我们用户最近更新他们的应用程序时发生的情况,这波更新也导致了他们的页面明显臃肿(这是他们这边的性能问题,这是另一个话题了)。

使用 .concat 合并 15,000 个字段(平均 5 个元素)需要 6 秒。

纳尼?

6秒...

只有 15,000 个字段,但平均只有 5 个元素?

数据量不是很大。

为什么这么慢? 有没有更快的方法来合并链表?

基准比较

.pushvs..concat,合并10000个字段和10个元素

所以我开始研究(我的意思是微软搜索).concat 和 Java 中其他形式的合并字段的基准比较。

事实证明,合并链表最快的方法是使用.push方法,该方法可以接收n个参数:

//将arr2的内容压入arr1

arr1.push(arr2[0],arr2[1],arr2[3],...,arr2[n])

//因为我的字段大小不固定,所以我使用了`apply`方法

Array.prototype.push.apply(arr1,arr2)

相比之下,它的速度更快,简直就是一个飞跃。

多快

我自己运行了一些性能基准来亲眼看看。 瞧,这是在 Chrome 上执行的差异:

合并的字段大小为 10 10000 次,.concat 的速率为 0.40ops/sec(每秒操作数),.push 的速率为 378ops/sec。 也就是说push比concat快945倍! 这些差异可能不是线性的,但在这些小数据量下已经很显着。

在火狐浏览器上,执行结果如下:

一般来说,与Chrome的V8引擎相比,Firefox的SpiderMonkeyJava引擎速度较慢,但​​.push始终排名第一,比concat快2260倍。

我们对代码进行了内部更改,它解决了整个速度下降的问题。

.pushvs..concat,合并2个字段50000个元素

但是好吧,如果您合并了两个包含 50,000 个元素的巨大字段,而不是包含 10 个元素的 10,000 个字段,该怎么办?

下面是在Chrome上的测试结果:

.push 仍然比 .concat 快,但这次快了 9 倍。

事实上,慢了 945 倍并不引人注目,但已经很慢了。

更优雅的扩展操作

如果你想到Array.prototype.push。

apply(arr1, arr2) 非常冗长,你可以使用 ES6 的展开运算符做一个简单的转换:

到达1。 推(...arr2)

Array.prototype.push.apply(arr1,arr2) 和 arr1.push(...arr2) 之间的性能差异基本上可以忽略不计。

但为什么 Array.concat 这么慢?

和Java引擎有很大关系,也不知道确切的答案,所以我问了我的同学@picocreator,GPU.js的联合创始人,他花了很多时间研究V8的源码。 由于我的 MacBook 没有足够的 VRAM 来运行 .concat 来组合两个宽度为 50000 的字段,@picocreator 还卖给了我他用来对 GPU.js 进行基准测试以运行 JsPerf 测试的珍贵游戏 PC。

也许答案与它们的工作方式有很大关系:合并字段时,.concat 创建一个新字段,而 .push 只是更改第一个链接列表。 这种额外的操作(将第一个链表元素添加到返回的字段)会减慢 .concat 速率。

我:“纳尼?不可能?就这样吧?可是为什么差别这么大?不可能!” @picocreator:“我不是在开玩笑,尝试编写 .concat 和 .push 的本机实现,你就会看到!”

于是我按照他说的尝试了一下,写了几个实现方法,并添加了和​​lodash的_.concat的对比:

原生实现方法1

让我们讨论第一组本机实现:

.concat 的本机实现

//创建结果字段

vararr3=[]

//添加arr1

对于(变量=0;i <arr1Length;i++){

arr3[i]=arr1[i]

//添加arr2

对于(变量=0;i <arr2Length;i++){

arr3[arr1长度+i]=arr2[i]

.push 的本机实现

对于(变量=0;i <arr2Length;i++){

arr1[arr1长度+i]=arr2[i]

正如你所看到的,两者之间唯一的区别是.push在实现中直接改变了第一个链表。

常规执行结果:

原生实现方法1的结果:

事实证明,我自己编写的 concat 和 push 比它们的常规实现要快……但是我们可以看到,简单地创建一个新字段并将第一个链表的内容复制到其中可以使整个过程显着加快。 慢的。

原生实现方法2(预先分配final字段的大小)

我们可以通过在添加元素之前预先分配字段的大小来进一步改进本机实现,这会产生巨大的差异。

带有预分配的 .concat 的本机实现

// 创建结果字段并预分配其大小

vararr3=数组(arr1长度+arr2长度)

//添加arr1

对于(变量=0;i <arr1Length;i++){

arr3[i]=arr1[i]

//添加arr2

对于(变量=0;i <arr2Length;i++){

arr3[arr1长度+i]=arr2[i]

带有预分配的 .push 的本机实现

// 预分配大小

arr1.length=arr1长度+arr2长度

//将arr2的元素添加到arr1中

对于(变量=0;i <arr2Length;i++){

arr1[arr1长度+i]=arr2[i]

原生实现方法1的结果:

原生实现方法2的结果:

预分配最终字段的大小可以将性能提高 2-3 倍。

.push 字段与 ..push 单个元素

如果我们一次只 .push 一个元素怎么办? 它会比 Array.prototype.push.apply(arr1, arr2) 更快吗?

对于(变量=0;i <arr2Length;i++){

到达1。 推(arr2[i])

结果

所以 .push 单个元素比 .push 整个链表慢,这是有道理的。

推理

为什么.push比.concat快 总而言之,concat比.push慢很多的主要原因是它创建了一个新字段javascript 数组 输出,并且另外将第一个链表的元素复制到这个新字段中。 现在对我来说还有另一个谜……

现在对我来说还有另一个谜……

另一个粉丝

为什么常规实现比本机实现慢? 我再次向@picocreator 寻求帮助。

我们查看了 lodash 的 _.concat 实现,并希望获得有关 .concat 一般如何实现的一些提示,因为它们在性能上具有可比性(lodash 更快一点)。

事实证明,根据.concat例程实现方法的规范,该方法是重载的,支持两种形式的参数传递:

传递要添加的n个值作为参数,如:[1,2].concat(3,4,5) 传递要合并的链表作为参数,如:[1,2]。连接([3,4,5])

你甚至可以写: [1,2].concat(3,4,[5,6])

Lodash 也是重载的,支持两种形式的参数传递。 lodash将所有参数加载到一个链表中,然后将其展平。 因此,如果您传递多个字段也是有意义的。 而且当你传递一个需要合并的字段时,它不会仅仅使用链表本身,而是将其复制到一个新字段中,然后将其展平。

……好的……

所以性能肯定是可以优化的。 这就是您可能想要自己实现合并字段的原因。

据我所知,这只是我和@picocreator基于Lodash的源代码和他对V8源代码稍微过时的了解,.concat在引擎中的正常实现是如何工作的。

您可以在闲暇时间点击这里阅读lodash的源码。

补充说明

我们的测试仅使用包含整数的字段。 我们都知道,Java引擎通过使用指定类型的字段可以执行得更快。 如果链表中有对象,则结果预计会更慢。 以下是用于运行基准测试的 PC 的尺寸:

为什么我们在 UI-licious 测试中要执行如此大的链表操作?

从工作原理来看,UI-licious测试引擎扫描目标应用程序的DOM树,评估语义、可访问属性和其他常见模式,以确定目标元素和测试方法。

这样我们就可以确保我们可以轻松地编写如下测试:

//跳转到dev.to

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

悟空资源网 javascript javascript 数组 输出-你知道在 Javascript 中合并链表最快的方法是什么吗? https://www.wkzy.net/game/181060.html

常见问题

相关文章

官方客服团队

为您解决烦忧 - 24小时在线 专业服务