2

I'm creating a data structure that will contain that I will be using to repeatedly check to see if certain values are defined. I've come up with two possible solutions, and am wondering which is more efficient, or if there is a better way than either:

1) Use an array: keys = ['key1' , 'key2', 'key3']

I can create an array like this and then use jQuery.inArray(keyToCheck, keys) > -1 to check and see if keyToCheck is in my array.

2) Use an object: keys = {key1 : 1, key2 : 1, key3: 1}

I can create this object and then use keys[keyToCheck] || 0 to see if keyToCheck is defined.

What I'm not sure about is how searching an object is implemented in javascript, and whether or not it's more efficient than jQuery.inArray, which loops through an array. Is there a performance difference between these methods? Using jQuery isn't an issue for me since I already have it in my code for other reasons.

ckersch
  • 7,507
  • 2
  • 37
  • 44
  • 1
    http://jsperf.com/object-index-vs-array-search/6 – Diodeus - James MacFarlane Sep 09 '13 at 20:05
  • As [another question](http://stackoverflow.com/questions/7700987/performance-of-key-lookup-in-javascript-object) states, the object lookup should be at least linear. – XZS Sep 09 '13 at 20:06
  • 1
    you're comparing apples to oranges, In the case of an array you're searching for value of any key, and in the case of an object you're searching for a specific key and ignoring the value. If you instead looked for a specific key in an array vs a specific key in an object, it would be a far closer comparison. – Kevin B Sep 09 '13 at 20:07
  • For the one who voted to close this question for being primarily based on opinion, whether one method is more efficient than the other is a matter of opinion, not speculation. – Geeky Guy Sep 09 '13 at 20:07
  • @XZS object property lookup is much closer to constant time than linear. Kevin B is right though; the comparison is problematic. – Pointy Sep 09 '13 at 20:08
  • 1
    inArray() is very slow, object lookup is very fast, near-instant in V8... the theoretical stuff about linear this or that is nothing compared to racing a user-land loop against a single native property lookup. JIT cheats most of those c++ benchmarks anyway. use the look-up-table instead of the array if you want your code to be fast. – dandavis Sep 09 '13 at 20:22
  • How would the search for a specific key in an array work? I generally think of arrays as being keyed with numbers, and I guess I'm not understanding what the parallel method of searching an array would be. – ckersch Sep 09 '13 at 20:24
  • It would be identical to checking for the existence of a key in an object. `keys[keyToCheck] || 0` http://jsfiddle.net/pcqju/ – Kevin B Sep 09 '13 at 20:39

1 Answers1

9

When wondering about performances, a way to get an answer is to test several cases on jsperf.
(There might be other benchmark site i don't know of, please comment if you know another one, i don't mean to advertise)

For your case, i tested 3 methods :
- using indexOf in an array
- using the 'in' operator
- testing the object's property value

the psperf is here for around 10 items is here : http://jsperf.com/key-or-array-search/2enter image description here

We can see that using the object's property value is by far faster on Firefox (>20 times faster than array, >5 times than in).
On Safari, everything is slower than on Firefox, still the object property access is more than two times faster.
But on Chrome i don't understand what's happening : all 3 methods are quite close, but the fastest is the array/indexOf method, ...

Performances are often surprising.

Notice that results might change -even change dramatically- depending on the number of keys (5, 20, 5000 ?), and also on the probability that a checked key is within the set.

I wondered how things would change wit a 500 length key array. Here are the results : http://jsperf.com/key-or-array-search/3 enter image description here

We see that the array is defeated for a 'big' key count.
So you have to make clear the situation you're in.
With a little key count, the overhead of handling a property makes the array win.
With a large key count, the cost of iterating within the array makes the property win...

GameAlchemist
  • 18,995
  • 7
  • 36
  • 59