一尘不染

为什么有时array.push比array [n] = value快?

javascript

作为测试某些代码的附带结果,我编写了一个小函数来比较使用array.push方法与直接寻址(array [n] =
value)的速度。令我惊讶的是,推送方法通常显示出更快的速度,尤其是在Firefox和Chrome中。出于好奇:有人对此有解释吗?您可以找到测试(单击“数组方法比较”)


阅读 296

收藏
2020-04-25

共1个答案

一尘不染

各种各样的因素都在起作用,大多数JS实现使用平面数组,如果以后需要的话,可以转换为稀疏存储。

基本上,决定稀疏的决定是基于设置哪些元素以及要浪费多少空间才能保持平坦的启发式方法。

在您的情况下,您要首先设置最后一个元素,这意味着JS引擎将看到一个数组,该数组需要具有一个长度,n但只有一个元素的长度。如果n足够大,则将立即使该数组成为稀疏数组-
在大多数引擎中,这意味着所有后续插入将采用慢速稀疏数组的情况。

您应该添加一个额外的测试,在其中填充从索引0到索引n-1的数组-它应该快得多。

为响应@Christoph并出于拖延的愿望,这里描述了如何在JS中(通常)实现数组-具体情况因JS引擎而异,但一般原理是相同的。

所有JS Object(而不是字符串,数字,true,false undefinednull)都不继承自基本对象类型-
确切的实现有所不同,可能是C ++继承,也可能是在C中手动实现(以任何一种方式这样做都有好处)-基本的Object类型定义默认的属性访问方法,例如

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

此Object类型处理所有标准属性访问逻辑,原型链等。然后Array实现变为

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

现在,当您在JS中创建数组时,引擎将创建类似于上述数据结构的内容。当您将对象插入Array实例时,Array的put方法将检查属性名称是否为0到2 ^
32之间的整数(或可以转换为整数,例如“ 121”,“ 2341”等)。 -1(或者可能是2 ^
31-1,我完全忘记了)。如果不是,则将put方法转发到基本Object实现,并完成标准的[[Put]]逻辑。否则,将值放入数组自己的存储中,如果数据足够紧凑,则引擎将使用平面数组存储,在这种情况下,插入(和检索)仅是标准数组索引操作,否则引擎将转换数组稀疏存储,并放置/获取使用映射来从propertyName到值位置。

老实说,我不确定在发生这种转换后当前是否有任何JS引擎从稀疏存储转换为平面存储。

顺便说一下,这是对所发生情况的一个较高层次的概述,并省略了一些更棘手的细节,但这是一般的实现模式。引擎之间如何增加存储以及如何分配/放置如何分配的细节各不相同-
但这是我可以真正描述的最清晰的设计/实现方式。

一个较小的附加点,尽管ES规范指的propertyName是字符串JS引擎也倾向于专门处理整数查找,所以someObject[someInteger]如果您查看的是具有整数属性的对象,则不会将整数转换为字符串。数组,字符串和DOM类型(NodeLists等)。

2020-04-25