Set polyfill with a "has" method more efficient than O(n)

David Bruant bruant.d at gmail.com
Fri Mar 30 00:44:32 PDT 2012


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 
http://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.

David


More information about the es-discuss mailing list