javascript的.length的时间复杂度 [英] time complexity of javascript's .length

问题描述

javascript的数组.length的时间复杂度是多少？我认为它会保持不变，因为看起来属性是在所有数组上自动设置的，你只是查找它？

what is the time complexity of javascript's array .length? I think it would be 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. Probably. It's a property which is stored (not calculated) and automatically updated as necessary.

话虽如此，记住JavaScript引擎可以自由地做他们在封面下喜欢什么，但你不能发现任何偏离规范的说法。由于规范没有说明长度的时间复杂度 ...

Having said that, remember that JavaScript engines are free to do what they like under the covers provided you can't observe any deviation from what the specification says. Since the specification doesn't say anything about the time complexity of length...

还要记住JavaScript的标准理论上，数组只是具有特殊行为的对象。理论上 ，JavaScript对象是属性包。因此，在理论上，查找属性包中的属性可能取决于有多少其他属性，如果对象被实现为某种名称 - >值hashmap（过去它们曾经是旧的）。现代引擎优化对象（Chrome的V8着名创建动态类并编译它们），但对这些对象的操作仍然可以改变属性查找性能。例如，添加属性可能会导致V8创建子类。删除一个属性（实际上使用 delete ）可能会使V8失控并退回到字典模式，这会大大降低对象的属性访问权。

Also 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的.length的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！