4 ms·
> I was surprised to learn that even implementing isEmpty(ob) in Javascript is an O(n) operation on most runtimes. That is surprising. Where `n` is the number
by Karellen 2y ago
> I was surprised to learn that even implementing isEmpty(ob) in Javascript is an O(n) operation on most runtimes.
That is surprising. Where `n` is the number of members, yes?
Surely that kind of operation should either return false immediately if there are no members, or return true in constant time if there is at least one member?
...although, do you have to iterate through the inherited members and check for `hasOwnProperty()`? Is it maybe O(n) where `n` is the number of enumerable inherited properties?
- paulgb 2y agoYou would think, right? The JS runtime itself must have a constant time way to know this, but it’s not exposed anywhere. The best you can do is iterate over the keys and bail the first time you get a key. But (at least in V8) iterating over the keys does some work up front that is O(n), even if you bail at the first key!
- patates 2y agoI think the issue is that the arrays are allowed to have holes: test = new Array(2) -> Array [ <2 empty slots> ] test[1] = true -> true test.length -> 2 test[0] -> undefined test[3] -> undefined test.some(x => x) -> true delete test[1] -> true test.some(x => x) -> false