DEV Community

Alex Parra
Alex Parra

Posted on

filterMap - JavaScript filter and map in O(n)

It's common that we need to get a subset of items from an array. For example, get only the users that are subscribed to the newsletter from the list of all users. This is commonly a job for Array.filter.

/**
 * Get list of subscribed users
 * @param {User[]} users The list of all users
 * @retuns {User[]} Only users that are subscribed
 */
const getSubscribedUsers = users => {
  return users.filter(user => user.is_subscribed);
}
Enter fullscreen mode Exit fullscreen mode

It's also common that we need to apply some transformation to a set of data. For example, get a list of full names from a list of users by concatenating each user's first_name and last_name.

/**
 * Get list of users full names
 * @param {User[]} users The list of all users
 * @retuns {string[]} Users full names
 */
const getUsersFullNames = users => {
  return users.map(user => `${user.first_name} ${user.last_name}`);
}
Enter fullscreen mode Exit fullscreen mode

*But what if we need the full names of the subscribed users only?
Frequently we'll see:

const subscribedUsers = getSubscribedUsers(users);
const subscribedUsersNames = getUsersFullNames(subscribedUsers);
Enter fullscreen mode Exit fullscreen mode

The problem with this approach, which might not be too significant on a small set of users but is when dealing with large sets, is that it requires two loops: the first across every user and the second across every subscribedUser.

The method I'm sharing with you here accomplishes the same result but looping just once over the data set – O(n) – thus making it more performant:

const isFn = f => typeof f === 'function';

/**
 * Filter and Map an Array in a single loop
 * @param {array} arr The list to process
 * @param {function} filterFn The filtering logic
 * @param {function} mapFn The transforming logic
 */
const filterMap = (arr, filterFn = null, mapFn = null) => {
  return arr.reduce((acc, item, i) => {
    if (isFn(filterFn) && filterFn(item, i) === false) return acc;
    const newItem = isFn(mapFn) ? mapFn(item, i) : item;
    return [...acc, newItem];
  }, []);
};

Enter fullscreen mode Exit fullscreen mode

And an example usage would be:

const isSubscribed = user => user.is_subscribed;
const getFullName = user => `${user.first_name} ${user.last_name}`;

const subscribedUsersNames = filterMap(users, isSubscribed, getFullName);
Enter fullscreen mode Exit fullscreen mode

In the example above, isSubscribed is a utility function that will be used to evaluate if the item (each user) should be kept or excluded, and getFullName is a utility function that will determine the data we get back in the new list.

Check it out at CodeSandbox with tests:
https://codesandbox.io/embed/js-array-filtermap-mvi1q?fontsize=14&hidenavigation=1&module=%2Findex.ts&previewwindow=tests&theme=dark

Spotted a mistake? Let me know!

Top comments (3)

Collapse
 
vonheikemen profile image
Heiker

If you can put the arr argument last then it would be easier to do partial application.

const isSubscribed = user => user.is_subscribed;
const getFullName = user => `${user.first_name} ${user.last_name}`;
const getSubscribed = filterMap.bind(null, isSubscribed, getFullName);

const subscribedUsersNames = getSubscribed(users);

// then you could also use it as a callback

fetch('some-url')
  .then(res => res.json())
  .then(getSubscribed)
Collapse
 
martynaskadisa profile image
Martynas Kadiša

This is essentially what transducers are used for. When you have a large data set and want to process it in a single pass with small utility functions. Here's an example codesandbox:
codesandbox.io/embed/peaceful-maye...

And here's an article about them that explains them better than I ever could:
medium.com/javascript-scene/transd...

Collapse
 
gustav profile image
Gustav

You should learn more about Big-O notation. O(n) does not mean you loop over the array just once. It means you loop over the array k*n+d times for some constants k and d. Both calling map and filter in order or doing what you do is O(n).