0

Possible Duplicate:
Is there a library for a Set data type in Javascript?

Is there a way to create a JavaScript data structure that mimics a c++ set? I need to perform searches in log(n) time, but can't find anything in the language that serves well. I've seen a couple of questions saying that I should represent the set as an object. Will that work? The key and payload of the array are numbers.

Community
  • 1
  • 1
Disco Globeulon
  • 459
  • 1
  • 6
  • 16
  • A similar question to this is: http://stackoverflow.com/questions/2342749/is-there-a-library-for-a-set-data-type-in-javascript Perhaps having a look at the source code for the JS.Set library will give you some ideas? http://jsclass.jcoglan.com/set.html – River Aug 14 '12 at 17:34

3 Answers3

2

For unordered sets, you'll probably be better off with a hash table implementation. These do O(1) lookups, so long as the hash table doesn't get overloaded.

For ordered, in-memory sets, the standard answers seem to be treaps (good average time, high standard deviation) and red-black trees (poor average time, low standard deviation). These are both O(logn) lookup.

user1277476
  • 2,871
  • 12
  • 10
0

It will have to, in javascript everything is an object.

GitaarLAB
  • 14,536
  • 11
  • 60
  • 80
  • What I meant was creating my own by doing something like `var set = {};` – Disco Globeulon Aug 14 '12 at 16:44
  • yep, see [Crockford on JavaScript - Chapter 2: And Then There Was JavaScript](http://www.youtube.com/watch?v=RO1Wnu-xKoY), and you WILL understand. Something to keep in mind: if needed, you check (set/convert) type of value before you use/read it, not while declaring the value. – GitaarLAB Aug 14 '12 at 16:45
  • Note that the main part of my question is if it's possible to search these objects or arrays in O(nlogn) time – Disco Globeulon Aug 14 '12 at 16:51
  • then you might find [this question](http://stackoverflow.com/questions/11514308/big-o-of-javascript-arrays) on SO helpfull. – GitaarLAB Aug 14 '12 at 17:01
0

If you need ordered set (which allows you to loop from the smallest element to the largest element, in the order you define), you can implement your own data structure in JS. I can't give more information on this, since I haven't done this first hand.

If you are satisfied with unordered set, you can implement it as followed:

  1. Define a normalized String representation of the object to be stored in the set. If you need a set with number, just use the string representation of the number. If you need a set of user-defined object, you can pick out the properties that defines the identity of the object, and use them in the normalized String representation.
  2. Create a JS Object to use as set by mapping normalized String representation to the actual object.
  3. Searching can be done by checking the property name with the String representation.
  4. Insertion to the set can be done by: first check whether the String representation is already there by searching, then map the String representation to the actual object if the object is not yet in the set.
  5. Deletion can be done by using delete, with the property name being the String representation of the object to be deleted.
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
  • I'll try that, since I actually require an unordered set. Then I'm hoping I can implement a logarithmic time search method. Thanks – Disco Globeulon Aug 14 '12 at 16:57
  • @Josh: For performance reason, accessing to Javascript property is at least O(log n). Depending on implementation, it might be better than that, but we at least expect a dictionary like structure to back the property lookup. – nhahtdh Aug 14 '12 at 17:11