Quantcast

Map/Set.prototype.size is O(n)

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Map/Set.prototype.size is O(n)

Daniel Herman
In reading the relevant section for the `size` accessors (http://www.ecma-international.org/ecma-262/7.0/index.html#sec-get-map.prototype.size), I'm confused and wondering why this was defined as an O(n) operation in the `get` accessor rather than as an additional step in the `set`, `delete`, and `clear` methods to track an internal `[[Size]]` variable or something, making the public `size` accessor capable of being O(1).

It seems surprising to me that in order to be spec compliant, Map and Set implementations must implement accessors that have surprising perf implications.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Map/Set.prototype.size is O(n)

Michał Wadas

Implementations aren't required to follow exactly these steps, just to have the same result.


On 29/03/17 17:15, Daniel Herman wrote:
In reading the relevant section for the `size` accessors (http://www.ecma-international.org/ecma-262/7.0/index.html#sec-get-map.prototype.size), I'm confused and wondering why this was defined as an O(n) operation in the `get` accessor rather than as an additional step in the `set`, `delete`, and `clear` methods to track an internal `[[Size]]` variable or something, making the public `size` accessor capable of being O(1).

It seems surprising to me that in order to be spec compliant, Map and Set implementations must implement accessors that have surprising perf implications.


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Map/Set.prototype.size is O(n)

Oriol _
In reply to this post by Daniel Herman
Not only `size`. All `get`, `set`, `has`, etc. algorithms in the spec are O(n).

But as explained in http://www.ecma-international.org/ecma-262/7.0/index.html#sec-map-objects,

> Map object must be implemented using either hash tables or other mechanisms that, on average,
> provide access times that are sublinear on the number of elements in the collection.
> The data structures used in this Map objects specification is only intended to describe the required
> observable semantics of Map objects. It is not intended to be a viable implementation model.


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Map/Set.prototype.size is O(n)

Isiah Meadows-2
The only part that matters is that it's *observably* equivalent
functionally. In theory, `indexOf` could be done in constant steps
provided there are no indexed getters or setters, and there's no
overriding proxy hook. It'd be impractical to ensure that, but it's
still theoretically possible to both do that and remaining conformant.
-----

Isiah Meadows
[hidden email]


On Wed, Mar 29, 2017 at 11:31 AM, Oriol _ <[hidden email]> wrote:

> Not only `size`. All `get`, `set`, `has`, etc. algorithms in the spec are
> O(n).
>
> But as explained in
> http://www.ecma-international.org/ecma-262/7.0/index.html#sec-map-objects,
>
>> Map object must be implemented using either hash tables or other
>> mechanisms that, on average,
>> provide access times that are sublinear on the number of elements in the
>> collection.
>> The data structures used in this Map objects specification is only
>> intended to describe the required
>> observable semantics of Map objects. It is not intended to be a viable
>> implementation model.
>
>
> _______________________________________________
> es-discuss mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/es-discuss
>
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Loading...