algorithm - Filter a json data by another array in underscore.js

Question

I have a search field and I want to add some complex functionality using underscore.js.

Sometimes users search for a whole "sentence" like "Samsung galaxy A20s ultra". I want to filter JSON data using any of the words in the search string and sort by results that contain more of the words.

Sample data:

var phones = [
{name: "Samsung A10s", id: 845},
{name: "Samsung galaxy", id: 839},
{name: "Nokia 7", id: 814},
{name: "Samsung S20s ultra", id: 514},
{name: "Apple iphone ultra", id: 159},
{name: "LG S20", id: 854}];

What is the best way to do it in underscore?

Answer 1

In this answer, I'll be building a function searchByRelevance that takes two arguments:

1. a JSON array of phones with name and id properties, and
2. a search string,

and which returns a new JSON array, with only the phones of which the name has at least one word in common with the search string, sorted such that the phones with the most common words come first.

Let's first identify all the subtasks and how you could implement them with Underscore. Once we've done that, we can compose them into the searchByRelevance function. In the end, I'll also spend some words on how we might determine what is "best".

Subtasks

Split a string into words

You don't need Underscore for this. Strings have a builtin split method:

"Samsung galaxy A20s ultra".split(' ')
// [ 'Samsung', 'galaxy', 'A20s', 'ultra' ]

However, if you have a whole array of strings and you want to split them all, so you get an array of arrays, you can do so using _.invoke:

_.invoke([
    'Samsung A10s',
    'Samsung galaxy',
    'Nokia 7',
    'Samsung S20s ultra',
    'Apple iphone ultra',
    'LG S20'
], 'split', ' ')
// [ [ 'Samsung', 'A10s' ],
//   [ 'Samsung', 'galaxy' ],
//   [ 'Nokia', '7' ],
//   [ 'Samsung', 'S20s', 'ultra' ],
//   [ 'Apple', 'iphone', 'ultra' ],
//   [ 'LG', 'S20' ] ]

Find the words that two arrays have in common

If you have two arrays of words,

var words1 = [ 'Samsung', 'galaxy', 'A20s', 'ultra' ],
    words2 = [ 'Apple', 'iphone', 'ultra' ];

then you can get a new array with just the words they have in common using _.intersection:

_.intersection(words1, words2) // [ 'ultra' ]

Count the number of words in an array

This is again something you don't need Underscore for:

[ 'Samsung', 'A10s' ].length // 2

But if you have multiple arrays of words, you can get the word counts for all of them using _.map:

_.map([
    [ 'Samsung', 'A10s' ],
    [ 'Samsung', 'galaxy' ],
    [ 'Nokia', '7' ],
    [ 'Samsung', 'S20s', 'ultra' ],
    [ 'Apple', 'iphone', 'ultra' ],
    [ 'LG', 'S20' ]
], 'length')
// [ 2, 2, 2, 3, 3, 2 ]

Sort an array by some criterion

_.sortBy does this. For example, the phones data by id:

_.sortBy(phones, 'id')
// [ { name: 'Apple iphone ultra', id: 159 },
//   { name: 'Samsung S20s ultra', id: 514 },
//   { name: 'Nokia 7', id: 814 },
//   { name: 'Samsung galaxy', id: 839 },
//   { name: 'Samsung A10s', id: 845 },
//   { name: 'LG S20', id: 854 } ]

To sort descending instead of ascending, you can first sort ascending and then reverse the result using the builtin reverse method:

_.sortBy(phones, 'id').reverse()
// [ { name: 'LG S20', id: 854 },
//   { name: 'Samsung A10s', id: 845 },
//   { name: 'Samsung galaxy', id: 839 },
//   { name: 'Nokia 7', id: 814 },
//   { name: 'Samsung S20s ultra', id: 514 },
//   { name: 'Apple iphone ultra', id: 159 } ]

You can also pass a criterion function. The function receives the current item and it can do anything, as long as it returns a string or number to use as the rank of the current item. For example, this sorts the phones by the last letter of the name (using _.last):

_.sortBy(phones, function(phone) { return _.last(phone.name); })
// [ { name: 'LG S20', id: 854 },
//   { name: 'Nokia 7', id: 814 },
//   { name: 'Samsung S20s ultra', id: 514 },
//   { name: 'Apple iphone ultra', id: 159 },
//   { name: 'Samsung A10s', id: 845 },
//   { name: 'Samsung galaxy', id: 839 } ]

Group the elements of an array by some criterion

Instead of sorting directly, we might also first only group the items by a criterion. Here's grouping the phones by the first letter of the name, using _.groupBy and _.first:

_.groupBy(phones, function(phone) { return _.first(phone.name); })
// { S: [ { name: 'Samsung A10s', id: 845 },
//        { name: 'Samsung galaxy', id: 839 },
//        { name: 'Samsung S20s ultra', id: 514 } ],
//   N: [ { name: 'Nokia 7', id: 814 } ],
//   A: [ { name: 'Apple iphone ultra', id: 159 } ],
//   L: [ { name: 'LG S20', id: 854 } ] }

We have seen that we can pass keys to sort or group by, or a function that returns something to use as a criterion. There is a third option which we can use here instead of the function above:

_.groupBy(phones, ['name', 0])
// { S: [ { name: 'Samsung A10s', id: 845 },
//        { name: 'Samsung galaxy', id: 839 },
//        { name: 'Samsung S20s ultra', id: 514 } ],
//   N: [ { name: 'Nokia 7', id: 814 } ],
//   A: [ { name: 'Apple iphone ultra', id: 159 } ],
//   L: [ { name: 'LG S20', id: 854 } ] }

Getting the keys of an object

This is what _.keys is for:

_.keys({name: "Samsung A10s", id: 845}) // [ 'name', 'id' ]

You can also do this with the standard Object.keys. _.keys works in old environments where Object.keys doesn't. Otherwise, they are interchangeable.

Turn an array of things into other things

We have previously seen the use of _.map to get the lengths of multiple arrays of words. In general, it takes an array or object and something that you want to be done with each element of that array or object, and it will return an array with the results:

_.map(phones, 'id')
// [ 845, 839, 814, 514, 159, 854 ]
_.map(phones, ['name', 0])
// [ 'S', 'S', 'N', 'S', 'A', 'L' ]
_.map(phones, function(phone) { return _.last(phone.name); })
// [ 's', 'y', '7', 'a', 'a', '0' ]

Note the similarity with _.sortBy and _.groupBy. This is a general pattern in Underscore: you have a collection of something and you want to do something with each element, in order to arrive at some sort of result. The thing you want to do with each element is called the "iteratee". Underscore has a function that ensures you can use the same iteratee shorthands in all functions that work with an iteratee: _.iteratee.

Sometimes you may want to do something with each element of a collection and combine the results in a way that is different from what _.map, _.sortBy and the other Underscore functions already do. In this case, you can use _.reduce, the most general function of them all. For example, here's how we can create a mixture of the names of the phones, by taking the first letter of the name of the first phone, the second letter of the name of the second phone, and so forth:

_.reduce(phones, function(memo, phone, index) {
    return memo + phone.name[index];
}, '')
// 'Sakse0'

The function that we pass to _.reduce is invoked for each phone. memo is the result that we've built so far. The result of the function is used as the new memo for the next phone that we process. In this way, we build our string one phone at a time. The last argument to _.reduce, '' in this case, sets the initial value of memo so we have something to start with.

Concatenate multiple arrays into a single one

For this we have _.flatten:

_.flatten([
    [ 'Samsung', 'A10s' ],
    [ 'Samsung', 'galaxy' ],
    [ 'Nokia', '7' ],
    [ 'Samsung', 'S20s', 'ultra' ],
    [ 'Apple', 'iphone', 'ultra' ],
    [ 'LG', 'S20' ]
])
// [ 'Samsung', 'A10s', 'Samsung', 'galaxy', 'Nokia', '7',
//   'Samsung', 'S20s', 'ultra', 'Apple', 'iphone', 'ultra',
//   'LG', 'S20' ]

Putting it all together

We have an array of phones and a search string, we want to somehow compare each of those phones to the search string, and finally we want to combine the results of that so we get the phones by relevance. Let's start with the middle part.

Does "each of those phones" ring a bell? We are creating an iteratee! We want it to take a phone as its argument, and we want it to return the number of words that its name has in common with the search string. This function will do that:

function relevance(phone) {
    return _.intersection(phone.name.split(' '), searchTerms).length;
}

This assumes that there is a searchTerms variable defined outside of the relevance function. It has to be an array with the words in the search string. We'll deal with this in a moment; let's address how to combine our results first.

While there are many ways possible, I think the following is quite elegant. I start with grouping the phones by relevance,

_.groupBy(phones, relevance)

but I want to omit the group of phones that have zero words in common with the search string:

var groups = _.omit(_.groupBy(phones, relevance), '0');

Note that I'm omitting the string key '0', not the number key 0, because the result of _.groupBy is an object, and the keys of an object are always strings.

Now we need to order the remaining groups by the number of matching words. We know the number of matching words for each group by taking the keys of our groups,

_.keys(groups)

and we can sort these ascending first, but we must take care to cast them back to numbers, so that we will sort 2 before 10 (numerical comparison) instead of '10' before '2' (lexicographical comparison):

_.sortBy(_.keys(groups), Number)

then we can reverse this in order to arrive at the final order of our groups.

var tiers = _.sortBy(_.keys(groups), Number).reverse();

Now we just need to transform this sorted array of keys into an array with the actual groups of phones. To do this, we can use _.map and <a href="https://underscorejs.org/#propertyOf" rel="nofollow noreferrer"