Searching data structures with JavaScript

12 Jul 2016 • javascript • programming

enter map reduce and then some

Concept of map reduce and other functional approaches to data processing is usually tightly connected to other programming languages than JavaScript. Maybe JS is not most optimal language to use for sorting through gigantic data sets, but in lots of cases there is a benefit of being able to put yourself in this kind of mindset, especially when FRP is getting more and more popular for UI handling.

So, here is quick guide through data oriented thinking and FRP approaches using the example of searching complex dataset…

Filter array by content of specific part of its items - step one

/**
* Here we have a method that searches through particular data structure of sets of DC graphic novels returning universes (string names) of sets that containing certain issue number (I know it is hardly real life use case)
*/
    var data = [
    { issues: [1, 2, 3], universe: ‘new52’ },
    { issues:[66, 77, 88], universe: ‘earth one’ },
    { issues:[2,11,22,33], universe: ‘earth two’ },
    { issues:[1,223,334], universe: ‘silver age’ }
    ];
    var SearchByIssue = function(lookForNumber) {
    return data.filter((set) => {
    return set.issues.some((number) => {
        return number === lookForNumber;
    });
    }).map((set) => set.universe); 
    };

Above example gives us the list of names of sets in which there is issue with number we are looking for… I know :)

Now, what is super optimal with this kind of approach is that .some() stops as soon as it hits one result that gives true, so here is where it shines a lot more:

Filter collection (array) by content of specific part of its items — step two

Content you search by is array of strings inside of an object (issue) inside of an array (set of issues) that is part of a bigger collection in set of collections.

In other words, imagine that there is tons of boxes with tons of issues, and each issue is not just a number in database, but it is more informative structure like:

//each collection minimally contains array of issues and collection name 
//(it may contain other descriptive data beside name)
    [{ issues: [{
        id: 32,
        name:”Kingdom Come”,
        authors: [“Mark Waid”, “Alex Ross”],
        characters: [“Superman, Batman, Diana Prince, Captain Marvel, Spectre, Norman McCay”]
    }...], 
    universe: "alternatives"
    },
    ...]

Ultimately, task is searching for all graphic novels with appearance of character, giving us name of the box in which to look and ID of an issue in it.

Talk is cheap - show me the code

var SearchByCharacter = function(complexData, searchForName) {
 /**
 * Filter filters out array members for which callback returns true,
 * so, we touch the box using .some() and see if it has 
 * stuff that we are looking for inside (some returns true with callback that returns true)
 **/
 return complexData.filter((item) => {
        return item.issues.some((issue) => {
            return (issue.characters.indexOf(searchForName) !== -1);
        });
    })
    /**
    * Now we have all the boxes that have character we are looking for 
    * in any of issues inside.
    *
    * Next we map through the boxes that we found contain some issues
    * we are looking for.
    **/
    .map((box) => {
    /**
    * inside of a box, we are mapping through issues returning
    * array of addresses inside of our big collection,
    * with any other needed info
    */
    return box.issues.map((issue) => {
                           return {
                              box: box.universe,
                              id: issue.id,
                              characters: issue.characters
                           };
                        })
    /**
    * we filter these by character appearance
    * and that is what gets returned per box
    * (array of locations of issues with character appearance in this particular box)
    */
        .filter((issue) => {
            return (issue.characters.indexOf(searchForName) !== -1);
        });
    })
    /**
    * Result is array of arrays of graphic novels with character we are looking for
    * We then reduce these to single array containing them all.
    * 
    * And those are our search results
    **/
    .reduce((a, b) => a.concat(b)); 
};

Looking at the example above, you can see that there is not too much code involved — it is all simple and straight forward. There are only higher order functions and callbacks performing data evaluations.

Using higher order functions which are building blocks of functional programming, you are able to think of any computation, or any data related task at all, as series of data evaluations and computations, returning desired result. In addition it does it without changing data we are starting with, which effectively gives us simpler and more readable code structure and ultimate pattern to work with data sets.

Patterns described here and in my last article easily apply to working with streams of data, aka observables, which makes it your entry point to reactive programming.

Here is the JSbin which you can use to get/test the code http://jsbin.com/vapitux/edit?js,console

Comments

Related Posts