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?
-
2If I may, why is the time complexity of an object property of concern? It seems so, minimal?Sterling Archer– Sterling Archer2015-09-29 17:54:59 +00:00Commented Sep 29, 2015 at 17:54
-
2@SterlingArcher any time complexity is important, so that the final time complexity can be compared to other solutions complexity.KeitelDOG– KeitelDOG2019-04-18 21:09:03 +00:00Commented Apr 18, 2019 at 21:09
-
2@KeitelDOG if you're calculating the time complexity of object props you either like pain or your boss hates youSterling Archer– Sterling Archer2019-04-18 22:10:36 +00:00Commented Apr 18, 2019 at 22:10
-
1@SterlingArcher In this case I agree because that is object prop. But more because it's out of our control than because it's minimal.KeitelDOG– KeitelDOG2019-04-19 17:20:28 +00:00Commented Apr 19, 2019 at 17:20
Add a comment
|
2 Answers
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.
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.
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.
4 Comments
cmgchess
in brief does this mean that i don't have to save the array length in a variable and refer it like
(let n = 0; n < arrLen; ++n). using (let n = 0; n < array.length; ++n) is fine?
T.J. Crowder
@cmgchess - Pretty much, yeah. Technically, if you save it to a variable (even better, a
const) you're avoiding a property access on each loop, which very slightly speeds up the loop. But the savings there is likely washed out by whatever you're doing in the loop, and you'd have to be looping over a huge array. With today's engines, it's probably premature optimization. :-) Just for fun, I put this together. While there is an effect, it's really small in modern JS engines. :-)T.J. Crowder
Of course, sometimes it matters semantically (e.g., if your'e changing the length of the array), but I know you know that. :-)
Appaji Chintimi
@T.J.Crowder Thanks for the jsfiddle, Nice to see there is little performance gain.
It doesn't seem like a bottleneck but if you want to be sure use var len = arr.length and check that. It doesn't hurt and seems to be a tad faster on my machine albeit not a significant difference.
var arr = [];
for (var i = 0; i < 1000000; i++) {
arr[i] = Math.random();
}
var start = new Date();
for (var i = 0; i < arr.length; i++) {
arr[i] = Math.random();
}
var time1 = new Date() - start;
var start = new Date();
for (var i = 0, len = arr.length; i < len; i++) {
arr[i] = Math.random();
}
var time2 = new Date() - start;
document.getElementById("output").innerHTML = ".length: " + time1 + "<br/>\nvar len: " + time2;<div id="output"></div>