4

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.

Sasha
  • 3,599
  • 1
  • 31
  • 52
  • 3
    https://www.google.com/?q=object+key+array+indexof+site:jsperf.com – Andreas Jan 16 '16 at 15:43
  • 1
    Check out [this topic](http://stackoverflow.com/questions/7737850/in-js-which-is-faster-objects-in-operator-or-arrays-indexof). – alesc Jan 16 '16 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 Jan 16 '16 at 16:01

1 Answers1

2

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...

Assaf Moldavsky
  • 1,681
  • 1
  • 19
  • 30