JavaScript的array.length的时间复杂度 [英] Time complexity of JavaScript's array.length

问题描述

在JavaScript中调用array.length的时间复杂度是多少?我认为这将是恒定的，因为似乎属性是在所有数组上自动设置的，而您只是在查找它?

What is the time complexity of a call to array.length in JavaScript? I think it would constant since it seems that property is set automatically on all arrays and you're just looking it up?

推荐答案

我认为这将是恒定的，因为似乎属性是在所有数组上自动设置的，而您只是在查找它吗?

I think it would be constant since it seems that property is set automatically on all arrays and you're just looking it up?

对.这是一个存储(未计算)并根据需要自动更新的属性.该规范是关于此处和

Right. It's a property which is stored (not calculated) and automatically updated as necessary. The specification is explicit about that here and here amongst other places.

从理论上讲，只要您不知道，JavaScript引擎就可以自由地在访问时计算length，就好像它是一个访问器属性一样(这意味着它实际上不能成为访问器属性，因为您可以在代码中检测到)，但是考虑到length被重复使用很多(想到的是for (let n = 0; n < array.length; ++n))，我认为我们可以假设所有广泛使用的JavaScript引擎都按照规范说或至少是持续访问时间的内容.

In theory, a JavaScript engine would be free to calculate length on access as though it were an accessor property as long as you couldn't tell (which would mean it couldn't literally be an accessor property, because you can detect that in code), but given that length is used repeatedly a lot (for (let n = 0; n < array.length; ++n) springs to mind), I think we can assume that all JavaScript engines in widespread use do what the spec says or at least something that's constant time access.

FWIW:请记住，从理论上讲，JavaScript的标准数组只是具有特殊行为的对象.从理论上讲， JavaScript对象是属性包.因此，从理论上讲，如果将对象实现为某种名称->值哈希图(并且过去曾经是旧版本)，则在属性包中查找属性可能取决于那里还有多少其他属性.天).现代引擎可以优化对象(Chrome的V8可以动态创建动态类并对其进行编译)，但是对这些对象的操作仍然可以更改属性查找性能.例如，添加属性会导致V8创建子类.删除属性(实际上使用delete)可以使V8举起手来，然后退回到字典模式"，即这会大大降低对象的属性访问权限.

Just FWIW: Remember that JavaScript's standard arrays are, in theory, just objects with special behavior. And in theory, JavaScript objects are property bags. So looking up a property in a property bag could, in theory, depend on how many other properties are there, if the object is implemented as some kind of name->value hashmap (and they used to be, back in the bad old days). Modern engines optimize objects (Chrome's V8 famously creates dynamic classes on the fly and compiles them), but operations on those objects can still change property lookup performance. Adding a property can cause V8 to create a subclass, for instance. Deleting a property (actually using delete) can make V8 throw up its hands and fall back into "dictionary mode," which substantially degrades property access on the object.

换句话说:它可能因引擎而异，甚至因对象而异.但是，如果您仅将数组用作数组(不在其上存储其他非数组属性)，那么很可能会得到固定时间的查找.

In other words: It may vary, engine to engine, even object to object. But if you use arrays purely as arrays (not storing other non-array properties on them), odds are you'll get constant-time lookup.

这篇关于JavaScript的array.length的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！