DEV Community

JS Performance: Perhaps We Shouldn't Always Use Arrays

Nimmo on July 26, 2018

It feels like I spend quite a lot of time trying to find things that are in arrays. Almost as much time as I spend trying to locate my cats! Cons...
Collapse
 
weswedding profile image
Weston Wedding

I love maps! I have often found myself getting pushed to use arrays despite my preferences by frameworks/libraries I am using or the simple convenience of being able to use .forEach(), .map(), etc.

At least In ES6-land we also finally have an actual Map object which gives us the ability to iterate over entries, easy size determination, using things other than strings as keys... probably other goodies.

const catsMap = new Map([
  ['Aeris', { name: 'Aeris', isFavourite: true }],
  ['Juri', { name: 'Juri' }],
  ['Dante', { name: 'Dante' }],
  ['Frankenstein', { name: 'Frankenstein' }],
  ['Aeris', { name: 'Aeris' }],
])

const findMyCat =
    requestedCat => catsMap.get(requestedCat)

console.log(findMyCat('Dante'))
console.log(findMyCat('Marmalade'))
Collapse
 
nimmo profile image
Nimmo

Ooh, I must have missed Map in JS, that's much better! When was this introduced? :-O

(I'll be honest, I posted this thinking "someone will tell me a better way to do this" - I'm glad I was proven correct! :-D )

Thanks <3

Collapse
 
weswedding profile image
Weston Wedding

Not sure, I actually stumbled on it by accident a while ago but haven't used it much because I never remember it exists.

Collapse
 
kepta profile image
Kushan Joshi

If you love exploring the new data structures in Javascript, there is a less talked version called WeakMap (also WeakSet). I recently wrote an article on their practical usage dev.to/kepta/javascript-underdogs-...

Collapse
 
nimmo profile image
Nimmo

Fantastic, thanks - will check this out. :-)

Collapse
 
pchinery profile image
Philip

Thanks for this nice-to-read article and +1 for adding 100% accurate cat samples! There is just one performance problem: If your cats look too similar, you might have to look at more than one (which goes for cats in the house as well as in maps)

Collapse
 
nimmo profile image
Nimmo

Cat examples are the future I expect. :D

And yes, absolutely - this post was really meant just to say "maybe don't always use arrays", and offer an alternative in a specific example (i.e. searching for Marmalade in an array of 10,000 cats). And the reason for this was more because I am guilty of over-using arrays when other data structures are more appropriate!

Unless I've misunderstood your comment, in which case please feel free to expand if you think there's something more kind of...fundamentally wrong with this post - part of the reason for posting it was to get feedback from other people to be honest!

Collapse
 
pchinery profile image
Philip

Basically, I probably failed in making a pun 😉 My two cats look very similar and I sometimes have to look twice to tell them apart. And as maps usually use hashing, two hashes can be the same and you'd have to compare two cats (or more) to find the correct one, but that's a rather rare case, when not happening in my garden 😉

Collapse
 
cdhowie profile image
Chris Howie • Edited

In most languages, I'd argue that you should only use a map if you're looking up many times using the same map object, since you have to pay the upfront cost of hashing the keys. But, in JavaScript, arrays are just hash tables with a length attribute; the indices are converted to strings and hashed anyway. So, in JS, there's little reason not to use maps all the time when you have unique string keys.

Collapse
 
nimmo profile image
Nimmo

Even in JS I wouldn't automatically reach for maps to be honest, as arrays are arguably easier for people to reason about and have so many useful methods on their prototypes (and um, I only found out that Map exists in JS last night...), but the thing that sparked this blog post was a real-world scenario that caused something at work to literally not work (due to AWS Lambda timing out) thanks to the poor performance of array.find on a massive array of things!

So definitely something to keep in mind if you know you'll be trying to find a cat in 10,000 cats, but yeah, I hear you re: not defaulting to them in other languages (and would go so far as to say that I wouldn't default to them in JS either - although I didn't know that about arrays being hash tables, so thanks for the extra info there! :) ).

Collapse
 
cdhowie profile image
Chris Howie • Edited

To clarify, when I refer to maps, I am primarily referring to objects, not instances of Map. Native JS objects are usable as maps, when the keys are strings (or can be unambiguously represented as strings).

The place you have to be careful is if you are already receiving an array from some API and you need to look up one item -- converting that array to some kind of map to look up a single item is going to cost more time than performing a linear search of the array. However, if your code is responsible for building the array in the first place, changing it to build an object should have the same performance while allowing O(1) lookups by key.

Re arrays having useful methods on their prototypes: yes -- though .find in particular is usually useless since you already have a way to look up items by key. (If you need the other prototype methods, there is Object.values(), though this does create an intermediate array which can impact performance.)

Collapse
 
qm3ster profile image
Mihail Malo

There is often a case where I have multiple indexes, so I end up doing something like this:

const cats = [
  { name: "Aeris", id: 0x00, isFavourite: true },
  { name: "Juri", id: 0x01 },
  { name: "Dante", id: 0x03 },
  { name: "Frankenstein", id: 0xff }
]
const byName = new Map()
const byId = new Map()
for (const cat of cats) {
  byName.set(cat.name, cat)
  byId.set(cat.id, cat)
}

If this wasn't as common, I'd probably investigate making a function that takes a predicate and an array and makes an iterator of entries that new Map() can consume.
But like this, I only iterate once to populate multiple Maps.

Plus there's the cases where I receive an object (including from JSON), so normal iteration wouldn't work:

const cats = {
  Aeris: { id: 0x00, isFavourite: true },
  Juri: { id: 0x01 },
  Dante: { id: 0x03 },
  Frankenstein: { id: 0xff }
}
const byName = new Map()
const byId = new Map()
for (const name of Object.keys(cats)) {
  const cat = { name, ...cats[name] }
  byName.set(name, cat)
  byId.set(cat.id, cat)
}
Collapse
 
kepta profile image
Kushan Joshi • Edited

Most of the times choosing the right data structure is crucial to ones application. Maps and Arrays both have places where one is favoured over the other.

For Map

  • I choose map when I want to iterate over a collection and also want to look up directly using a unique ID. It sorta works like a regular object, with added powers of being able to iterate efficiently and keys can be of any data type.
  • Maps are much more efficient when you have to do a lot of read and writes. Last I read, an array with holes (deleting values in between) gets deoptimized into an object.

For Array

  • Maps even though good at iteration, can never be faster than a plain array when it comes to iteration.
  • Arrays are great when you want a data structure which has a continuous range of number indices. For eg array[4]; or array[10000].
  • With arrays you get loads of functional helper methods (.map, .reduce, .every, .some, .reduce, etc), but with Map you do not! If you find yourself implementing them, you should rethink about using Map in the first place.
  • Arrays are great when you have a one to many data structure. In your example what if there are 2 or more Aeries?
  • Maps and other complex data structure are hard to JSON.stringify (serialise). To serialise them, you end up converting them into an array of tuples. If you frequently have to serialise your data structure, you should be careful before using Maps.
  • Maps do not play well when you want to enforce immutability as the native API is not really written keeping immutability in mind. But with Arrays you can use Object.freeze or use .concat. If you want your data structure to be a Map (dictionary), Immutable.js is a good place to look at.
Collapse
 
nimmo profile image
Nimmo

You should make this into a post in itself - this is great advice. <3

Collapse
 
ibibgor profile image
Oscar • Edited

thepracticaldev.s3.amazonaws.com/i...
Just to underline your point with some fancy numbers. I wrote this jsperf test on my way to work on my phone. 😅

Collapse
 
nimmo profile image
Nimmo

Excellent :-D If you add the link I'll add it to the post (and credit you obviously). <3

Collapse
 
nimmo profile image
Nimmo

Ah you did already. Thanks!

Collapse
 
chiangs profile image
Stephen Chiang

This is great, I'm always reaching for arrays because they are easy and my datasets are typically pretty small, but I have been wanting to get better at utilizing maps, especially with the ES6 update.

Collapse
 
rhymes profile image
rhymes

You could also try Sets for this example 😁

Collapse
 
nimmo profile image
Nimmo

Tell me more! :-) (please :-D )

Collapse
 
rhymes profile image
rhymes

It's a new ES6 addition but sometimes they come in handy, you can add elements, you are sure they are unique and you can ask if the element is in there without enumerating everything. If you need to associate a key with values Map is a better choice though developer.mozilla.org/en-US/docs/W...

Thread Thread
 
nimmo profile image
Nimmo • Edited

Ah my apologies, I should have asked my question better than "tell me more", but thank you for the detail!

What I really meant was "how would I use a Set to allow findMyCat('Dante') to work?" In the interests of understanding better is all - I agree that a Map (which I now exists thanks to the comments on this post :-D) would have been a better choice here.