Set polyfill with a "has" method more efficient than O(n)
Peter Michaux wrote:
I've worked on a generic Set polyfill. It is quite a simple task to build one but determining if an object is in the set is O(n) with the following "has" method.
Set.prototype.has = function(element) { for (var i = 0, ilen = this._elements.length; i< ilen; i++) { if (element === this._elements[i]) {
You need Object.is here, not ===, per
Object.is spec:
return true; } } return false; };It seems like a long shot but is there some trick that someone has discovered that allows for a more efficient generic Set polyfill?
There's no portable way. Could you use something in the DOM, e.g. UserData? Not sure.
Le 30/03/2012 07:17, Peter Michaux a écrit :
I've worked on a generic Set polyfill. It is quite a simple task to build one but determining if an object is in the set is O(n) with the following "has" method.
Set.prototype.has = function(element) { for (var i = 0, ilen = this._elements.length; i< ilen; i++) { if (element === this._elements[i]) { return true; } } return false; };It seems like a long shot but is there some trick that someone has discovered that allows for a more efficient generic Set polyfill?
The issue here is that without native Set, the representations you have of an object set requires to traverse it entirely the representation to find something in it. This isn't true for sets of orderable things like strings or numbers since orderable things could be ordered and found in O(log(n)). But opaque things like objects can't be ordered.
One idea would be that each Set puts a unique marker on each object it contains as a non-enumerable property. Override Object.getOwnPropertyNames, Object.preventExtensions|seal|freeze for consistency. Much like the technique in code.google.com/p/es-lab/source/browse/trunk/src/ses/WeakMap.js
Certainly not the best solution ever, but it seems like a step forward assuming the costs of such a solution (in terms of performance and security) is acceptable in your applications.
I was thinking the same, create a __setUniqueId property per each set, add it per each added element to the set, and check if this.__setUniqueId in element is true.
This is way too dirty to me in any case, I preferred to do not pollute objects at all indeed with es6-collections shim ( WebReflection/es6-collections)
It must be said I am not using there what Brendan suggested, the Object.is equivalent ... good catch ( however, I think the NaN and -0 cases are extremely edge )
br
I think it is fair, for the shimming crowd, to ask objects to
implement a hash method to return a consistent string. Collection
types can degrade to O(n) in the absence of a provided consistent
hash, but enhance to O(1) in the best case. This would involve having
a two layer internal datastructure, an object that maps consistent
hashes -> to array buckets -> to values for Set or [key, value] pairs
for Map. I would also implement Map in terms of Set, just overriding the hash and equals functions to operate on the key portion of each pair in the set.
Kris Kowal
Good point, IIRC dherman and markm have discussed basing sets and maps on delegated hash and equals, so it's not all object identity. As you point out, this helps the shim builders.
I'm not sure I understand the reasonning here. Introducing a new feature to shim another new feature? What about implementators just implement the initial new feature?
In other words: would hash be of any use if Set, Map and WeakMaps (why not WeakSets?) were deployed? Set/Map/WeakMap are already being implemented in Firefox and Chrome. At this pace, hashes will be implemented only in browsers that don't need these to be shimed.
Is there another use case for exposing hashes?
David
Le 30/03/2012 20:16, Brendan Eich a écrit :
Or basically, Map/WeakMap/Set IS essentially that exact feature. In the future when something is needing to be shimmed that needs the ability to do anything a hash would enable, then those three things will be enough to do it.
On Thu, Mar 29, 2012 at 10:20 PM, Brendan Eich <brendan at mozilla.org> wrote:
Peter Michaux wrote:
I've worked on a generic Set polyfill. It is quite a simple task to build one but determining if an object is in the set is O(n) with the following "has" method.
Set.prototype.has = function(element) { for (var i = 0, ilen = this._elements.length; i< ilen; i++) { if (element === this._elements[i]) {
You need Object.is here, not ===, per
Object.is spec:
Thanks for mentioning this.
What is the license on the "is" function implementation shown in the wiki? I'd like to include it in a file that is 2-clause BSD licensed. I see the wiki itself is under the CC non-commercial license which seems incompatible.
Peter
On Fri, Mar 30, 2012 at 12:44 AM, David Bruant <bruant.d at gmail.com> wrote:
One idea would be that each Set puts a unique marker on each object it contains
I thought about an approach like this but am looking to avoid mutating the elements in the set. Thanks though.
Peter
Don't worry about it -- I'll slap a PD declaration in there.
Mark says this Object.is polyfill came from Caja code, so is ASL2-licensed. See
code.google.com/searchframe#wBZsFl6bRv8/trunk/src/com/google/caja/ses/repairES5.js
and use with ASL2 and Mark's blessing.
I've worked on a generic Set polyfill. It is quite a simple task to build one but determining if an object is in the set is O(n) with the following "has" method.
It seems like a long shot but is there some trick that someone has discovered that allows for a more efficient generic Set polyfill?
Thanks, Peter
I've worked on a generic Set polyfill. It is quite a simple task to build one but determining if an object is in the set is O(n) with the following "has" method. Set.prototype.has = function(element) { for (var i = 0, ilen = this._elements.length; i < ilen; i++) { if (element === this._elements[i]) { return true; } } return false; }; It seems like a long shot but is there some trick that someone has discovered that allows for a more efficient generic Set polyfill? Thanks, Peter