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!
Consider the following:
const catsArray =
[ {name: 'Aeris', isFavourite: true}
, {name: 'Juri'}
, {name: 'Dante'}
, {name: 'Frankenstein'}
];
const findMyCat =
requestedCat =>
catsArray.find(({name}) => name === requestedCat);
findMyCat('Dante'); // {name: 'Dante'}
findMyCat('Marmalade'); // undefined
I want to find Dante (which is a common real-world problem), and to do so I first need to check to make sure that Aeris isn't Dante, and then I have to check that Juri isn't Dante either. A bit weird, but okay. And if I want to check to see if I have a cat called Marmalade, I have to check all of my cats first, just to be sure I don't. Hm.
Perhaps my data could be represented a bit better here?
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)
findMyCat('Dante'); // {name: 'Dante'}
findMyCat('Marmalade'); // undefined
Now the next time I want to find Dante, I can just look for him. If he's there at catsMap['Dante'] like he's supposed to be, I'll find him, and if he's not, I won't - but I won't need to waste my time looking at any other cats along the way. Imagine the difference this will make when I have 10,000 cats, none of which are called Marmalade; I just saved myself 10,000 (hypothetical) operations!
Update:
I knew that if I posted this message here, someone would quickly offer up a better alternative, so thank you to Weston Wedding for pointing out that Maps actually exist in JS now! (I've updated the example in this post to reflect this, so if you're reading this for the first time you don't need to worry about the "old" one :) )
Also thanks to Oscar for the following performance test, showing the difference between the two approaches described in the original post. <3
Top comments (24)
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.
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
Not sure, I actually stumbled on it by accident a while ago but haven't used it much because I never remember it exists.
If you love exploring the new data structures in Javascript, there is a less talked version called
WeakMap
(alsoWeakSet
). I recently wrote an article on their practical usage dev.to/kepta/javascript-underdogs-...Fantastic, thanks - will check this out. :-)
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)
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!
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 😉
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.
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 ofarray.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! :) ).
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 isObject.values()
, though this does create an intermediate array which can impact performance.)There is often a case where I have multiple indexes, so I end up doing something like this:
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
Map
s.Plus there's the cases where I receive an object (including from JSON), so normal iteration wouldn't work:
Most of the times choosing the right data structure is crucial to ones application.
Map
s andArray
s both have places where one is favoured over the other.For Map
For Array
array[4];
orarray[10000]
..map
,.reduce
,.every
,.some
,.reduce
, etc), but withMap
you do not! If you find yourself implementing them, you should rethink about usingMap
in the first place.Aeries
?Map
s and other complex data structure are hard toJSON.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 usingMap
s.Map
s do not play well when you want to enforce immutability as the native API is not really written keeping immutability in mind. But withArray
s you can useObject.freeze
or use.concat
. If you want your data structure to be a Map (dictionary), Immutable.js is a good place to look at.You should make this into a post in itself - this is great advice. <3
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. 😅
Excellent :-D If you add the link I'll add it to the post (and credit you obviously). <3
Ah you did already. Thanks!
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.
You could also try Sets for this example 😁
Tell me more! :-) (please :-D )
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...
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.Some comments may only be visible to logged-in visitors. Sign in to view all comments.