Javascript filter is slow

Question

I have two large arrays in my node application.

var styles = [{itemID:..., styleID:..., styleNum:..., otherFields...}]; // 42455 items
var products = [{productID:..., styleNum:..., otherFields...}]; // 72K items

I need to loop through the products and get the associated styleID from the styles array and add a new item into a new array. The styles array is sorted by styleNum. Here is what I have tried:

var i=0, len = products.length, items = new Array(products.length);
for (i = 0; i < len; i++)
{
    var workingItem = products[i];
    var styleID = filterStyles(workingItem.styleNum)[0].styleID; 
    var item = {styleID:..., other fields};
    items[i]=item; 
}

...

function filterStyles(styleNum) 
{
    var results = [];
    var item;
    for (var i = 0, len = createdStyles.length; i < len; i++) 
    {
        item = createdStyles[i];
        if (item.styleNum == styleNum) results.push(item);
    }
    return results;
}

This is very slow, it takes 1 second to iterate over 100 items from my products array. I tried the same using asyc.each, but get the same response time. When I remove the filter function, it's lighting fast. Is there any way for me to improve my filter function?

Answer 1

To avoid scanning the array every time O(n2), you could create a map keyed by styleNum.

var styleNumMap = Object.create(null);
styles.forEach(function(style) {
    if (!styleNumMap[style.styleNum]) {
        styleNumMap[style.styleNum] = [];
    }
    styleNumMap[style.styleNum].push(style);
});

Then you can just do

var i=0, len = products.length, items = new Array(products.length);
for (i = 0; i < len; i++)
{
    var workingItem = products[i];
    var styleID = styleNumMap[workingItem.styleNum][0].styleID; 
    var item = {styleID:..., other fields};
    items[i]=item; 
}