Quickie Dev #4: Using Javascript’s reduce function

Because this hammer is actually a Swiss Army knife!

This article is also available on Medium.

When I first encountered the reduce function in Javascript, I found it strange to use. I had a code with various arrays all over the place but, right there, I needed to create an object and not an array. This meant I couldn’t use the forEach and map methods I was used to – instead, I had to go for reduce.

So, first off, it was strange because it took in an array, and it spit out an object. I felt like I was shifting from one world to the other. And in addition to that, you add to pass around this weird “accumulator” variable.

Little did I know I had actually just stumped upon an amazing tool… 🙂

Using reduce: the basics

The basic idea behind the reduce function is to iterate through a list of values and use those to gradually “fill an accumulator”. This accumulator is a variable of any type you want that you simply initialize at the very beginning of the reduction, and then modify (or just pass through) at each iteration. A common usage of the reduce is the use case I was talking about in my intro: creating an object from an array of things.

For example, suppose you have a list of blog posts. Those blog posts are stored as an array of objects, where each object looks like this:

{
  id: '20210512-my-first-article',
  title: 'My first article',
  pubdate: '2021-05-12T14:20:19.528622',
  excerpt: 'This is my first article - yay!',
  // ... additional info
}

Many blogs work in a similar way: you first land on a homepage with the list of available articles and when you click the big thumbnail or the title of one article, you are then redirected to the dedicated page. If you look at the URL of this new page in your browser, it will most likely contain some unique ID matching the post you chose.

It’s therefore more than probable that the website has some logic where it reads the ID in the URL and it uses it to fetch the blog post info and content. This means that you need to find the right object in your array of blog posts.

Now, you could use Javascript’s find method to go through your array and find the first item that has the right ID. It’s very easy-to-use, very readable in your code, and most of all it lets you use your data as is. However, it’s not the most efficient way to search for a post.

If you have only a dozen of posts, you won’t have any issue. But if you’re compiling decades of archives and you have thousands and thousands of articles, you might face some loading time issues. This is because the find method is neat, but it has to go through all of the items in the list one by one and check your condition until one matches. So if your article happens to be the last one, you’ll literally go through thousands of checks before finally finding the right item.

Here is a small example of a JS script that creates arrays of blog posts of various sizes and then uses the find method to get the one with the biggest ID (so the last item in the list):

If we run it, we get those results that clearly show how the size of the collection impacts the computing time:

n = 10
Compute time: 0.078ms

n = 100
Compute time: 0.008ms

n = 1000000
Compute time: 14.524ms

n = 10000000
Compute time: 140.235ms

A general rule-of-thumb for API response time is to keep it under 1 second, otherwise the user will notice the delay (and remember that, here, we’ve already waited to wait the article page – now we’re on the page, we expect it to be loaded instantaneously). So clearly, our program wouldn’t make the cut if we had tens of millions of articles… (granted, that’s a large number of articles, but, hey, you have to be ready for everything!).

As I’ve pointed out in a recent article on Python iterables, no matter what programming language you use, choosing the right data structure can be key to fixing your performance issue.

In our blog post-iteration scenario, it would be way more interesting to have key-value pairs that map an ID to its corresponding post info. And, in Javascript, this is done using an object.

All this to finally introduce our reduce example! A very common technique to tackle this “data structure rearrangement” issue is to keep an “object version” of your blog posts in your website code so that whenever you need to access an article by its ID, you can very rapidly get it in this optimized mapping.

The reduce function needs you to define 3 things:

  • the array you are iterating on
  • the function to apply at each iteration: it takes in both your accumulator and the current item in your iterated collection
  • the initial value for the accumulator

Here’s an example of how to convert our blog posts array into an object, using the article’s ID as the key:

The initial conversion may be long but once it’s done, you’ll access everything in a flash!

Note: the field of algorithmics studies, among other things, the data structures and their associated complexity for various operations. Here, we are talking about accessing a specific item in the structure. With the array and its find method, this operation is said to be (worst-case scenario) in O(n), meaning that it grows linearly with the number of item in the list – if you have twice the number of items and your article is the last one, you’ll have to go through twice as many checks before you reach it. On the other hand, the object direct mapping is in O(1), meaning the access takes constant time and does not depend on the number of items.

Using reduce for computing a sum, a mean…

The incredible thing about reduce is that it’s not only capable of producing objects, but it can actually “accumulate” anything you want. This is particularly useful when you want to compute the sum of an array of values, or the mean, or even some funky concatenation of those values:

Note: I briefly mentioned the CodinGame challenges in a previous Quickie Dev, but you’ll probably see how useful it can be for solving some of their puzzles when working with Javascript! 😉

I need to point however that reduce, while very easy-to-read, is not necessarily the most performant option for computing sums, means, etc. A simple for-loop can be way better.

Using reduce for filtering

Another use of reduce can be for filtering. In my experience, it’s often combined with some other transformation (otherwise you can just use the filter function). Since you are accumulating things, you can also choose to “skip” an iteration and directly return your accumulator without modifying it for that specific item.

For example, suppose you have a list of numbers and you’re only interested in the square of the even ones. You could first apply a filter and then a map, but this would require n + t operations (where n is the initial number of items and t is the number of filtered items).

With a reduce, you reduce the number of operations to n since you do all at once:

Conclusion

This article introduced the really sweet reduce JS function which can be applied to lots of use cases and is more of a shapeshifter than I originally thought. You have to be aware of the fact that, if you’re looking for true performance, native loops are usually a faster method than JS new function such as mapfilter or reduce, as recalled in this article by Y. Kadishay. But those constructs are very readable and, sometimes, this is more precious than plain old computing time…

What about you? Do you have tips and tricks using Javascript’s reduce? Feel free to react in the comments! 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *