5

I need to emulate set in JavaScript — i.e. variable that is able to answer question "do I contain x?".

Performance of insertion/deletion doesn't matter. Order doesn't matter. And it isn't multiset.

There are two ways to implement it:

  1. Using regular array with value search:

    var set = [17, 22, 34];
    if (set.indexOf(x)!=-1) ...;
    
    • 1a. Using TypedArray (e.g. Int32Array), when possible:

      var set = Int32Array.of(17, 22, 34);
      if (set.indexOf(x)!=-1) ...;
      
  2. Using object with key search:

    var set = {17: true, 22: true, 34: true};
    if (set[x]) ...;
    

Theoretically object key search should be much faster (depending on how they implemented it in JS engine, it should be either O(log(n)), or O(1) — vs O(n) on array value search). However, is this a case in JavaScript (where access to object member may require multiple lookups) — especially on small sets with dozens of items? Assuming that values in set are quite simple (either integers, or short strings).

Resume. I want to know: what minimum amount of set items is required to make object key search faster than array value search in case of: (1) values are integers; (2) values are short strings — in modern (2015/2016) web-browsers?

I understand that I can perform measurements myself, but it seems to be irrational to make every developer measure the same things — so I put this question here in case somebody have done it.

3
  • 3
  • 1
    Check out this topic.
    – alesc
    Commented Jan 16, 2016 at 15:46
  • @Andreas, the problem with this site is that it doesn't publish results (it would be much better if I could see results of other users with specified dates/other info; it probably will take less time for writing test than for running it in different browsers). Never-the-less, thank you, now I see that object key search is faster even on small sets, at least on Firefox/Linux/64-bit. Maybe I'll write my own test later and publish it (with results) here as answer.
    – Sasha
    Commented Jan 16, 2016 at 16:01

1 Answer 1

3

I was also curious about this and I have done most of these analysis using the same stack as jsPerm on NodeJS 6.3:

https://github.com/amoldavsky/js-array-indexof-vs-hashmap

The input data is array of various sizes ( 2^x where x = 0 .. 11 ) and short keys of 1 to 2 chars.

Tests are broken by insertion, lookup, and insertion + lookup.

Results are:

  • lookup using Object ( basically a HashMap ) is faster from 16 elements an up
  • insert is super slow for Object keys
  • insert + lookup, arrays are always faster regardless of size

Duplicates in your dataset have to be considered as well...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.