Optimal way to collect keys into an Array JavaScript?

Question

What is the optimal way to get unique strings in an array? There are times when it makes sense to do it one of many ways, here are 3:

creating an array and, for each new item you push, first check if _.indexOf(array, newItem) == -1
creating a hash, with all values as true, such as {key1: true, key2: true}, then _.keys(hash)
pushing all items in the array, then running keys = _.uniq(keys)

The above code is using underscore.js helpers.

Having knowledge of the internals of JavaScript constructs/vm's, and some formal algorithms knowledge, would probably make this a no brainer but I'm not there yet. I'm sure it differs from browser to browser (and node), but maybe there is a preferred approach. Any ideas?

Niet the Dark Absol · Accepted Answer · 2012-07-08 01:31:45Z

6

The first solution has to loop through every element of the array, for each element of the array. That makes a complexity of O(n²).

The second is probably the best, because it only loops through the array, then loops through the keys. That's basically O(2n), which is just O(n).

The third depends on how efficient uniq() is. For instance, it might well just be an implementation of method 2.

answered Jul 8, 2012 at 1:31

Niet the Dark Absol

326k86 gold badges480 silver badges604 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lance Pollard Over a year ago

At small scales (less than 50 keys per object), the first solution seems to be more than 3x as fast as the second in node: gist.github.com/4633028.

Collectives™ on Stack Overflow

Optimal way to collect keys into an Array JavaScript?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related