Most efficient way to search a map of arrays in JavaScript

Question

I have a map of arrays of numbers in JavaScript. My goal is to get the key of the value that contains a certain number. I'm also open to a different data structure that might be more efficient.

let bookCategory = {
    "fantasy": [10064, 10066, 10071],
    "scifi": [10060, 10037, 10061],
    "history": [10001, 10003, 10004, 10005],
    "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
    "educational": [10025]
};

Each number will only ever appear once, but each array can contain close to a hundred numbers and it may grow substantially from there. The arrays could be immutable as my data is static.

Right now I have this, but it doesn't seem terribly efficient.

let category;
let keys = _.keys(categories);
let theNumber = 10032;

for(let j = 0; j < keys.length; j++) {
    if(_.includes(categories[keys[j]], theNumber)) {
        category = keys[j];
        break;
    }
}

@SalvadorDali those numbers aren't in any of the arrays so category would remain undefined. — diplosaurus
– diplosaurus, Commented Apr 21, 2016 at 4:50
If those are different - create a map from the value to the category. — zerkms
– zerkms, Commented Apr 21, 2016 at 4:57
@NinaScholz Nope. Each number only appears a single time, if at all. — diplosaurus
– diplosaurus, Commented Apr 21, 2016 at 6:48

Dmitri Pavlutin · Accepted Answer · 2016-04-21 07:30:35Z

lodash library has a lot of useful functions. Using it, you have the following options:

1. Binary search

Create a new structure with sorted array of numbers. When looking for a number, apply a binary search.
_.sortedIndexOf() method uses binary search in an array.

var bookCategory = {
 "fantasy": [10064, 10066, 10071],
 "scifi": [10060, 10037, 10061],
 "history": [10001, 10003, 10004, 10005],
 "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
 "educational": [10025]
};

var binaryMap = _.mapValues(bookCategory, function(category) {
  return category.sort(function(num1, num2) { 
    return num1 - num2; 
  });
});

//then search using binary algorithm    
var number = 10032;
var keyForNumber = _.findKey(binaryMap, function(numbers) {
  return _.sortedIndexOf(numbers, number) !== -1;
});

keyForNumber // prints "biography"

Check the working demo.

2. Create a map object

Because the numbers will appear only once, it's easy to create a big hash object, where the key is the number and value is the category. It requires a bit more memory because copies the categories string, but it works quite fast.
This solution doesn't require lodash.

var bookCategory = {
 "fantasy": [10064, 10066, 10071],
 "scifi": [10060, 10037, 10061],
 "history": [10001, 10003, 10004, 10005],
 "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
 "educational": [10025]
};

var map = _.reduce(bookCategory, function(result, numbers, key) {
  _.each(numbers, function(number) {
    result[number] = key;
  });
  return result;
}, {});

// or alternative without lodash
var mapAlternative = Object.keys(bookCategory).reduce(function(result, key) {
  bookCategory[key].forEach(function(number) {
    result[number] = key;
  });
  return result;
}, {});


var number = 10003;
map[number]; // prints "history"

Check the working demo.

Jeremy J Starcher · Accepted Answer · 2016-04-21 04:42:20Z

0

There are too many what-ifs to answer that question, the biggest one being: How often is the data going to be updated vs read.

If it is going to be read much more often, then iterate through the bookCategory first and create a sparse array/object that links the numbers back to the category.

(I'll go for object here):

// Generate this programatticly, of course.
bookCategoryLinkback = {
    10064: "fantasy",
    10066: "fantasy",
    10071: "fantasy"
};

answered Apr 21, 2016 at 4:42

Jeremy J Starcher

24k6 gold badges56 silver badges75 bronze badges

2 Comments

diplosaurus Over a year ago

My arrays are completely static. If I was using something like Immutable I could freeze them completely. No updates at all.

Jeremy J Starcher Over a year ago

Then I'd use a loop, similar to what you have, and just create a new backreference object like I show above.

ramon.liu · Accepted Answer · 2016-04-21 04:44:13Z

0

sort the array and use binary search. You can use lodash lib to do it easily.

answered Apr 21, 2016 at 4:44

ramon.liu

1863 silver badges5 bronze badges

2 Comments

diplosaurus Over a year ago

Wouldn't the sorting take longer than simply iterating through them looking for the answer? Or is sort a faster operation than I'm thinking.

zerkms Over a year ago

@diplosaurus we have no idea what you're thinking.

Nina Scholz · Accepted Answer · 2016-04-21 06:50:47Z

0

I suggest to use a hashtable for the numbers.

var bookCategory = {
        "fantasy": [10064, 10066, 10071],
        "scifi": [10060, 10037, 10061],
        "history": [10001, 10003, 10004, 10005],
        "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
        "educational": [10025]
    },
    numbers = function (data) {
        var r = Object.create(null);
        Object.keys(data).forEach(k => data[k].forEach(a => r[a] = k));
        return r;
    }(bookCategory)

document.write('<pre>' + JSON.stringify(numbers, 0, 4) + '</pre>');

answered Apr 21, 2016 at 6:50

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Collectives™ on Stack Overflow

Most efficient way to search a map of arrays in JavaScript

4 Answers 4

1 Comment

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related