skone skone - 1 year ago 64
Node.js Question

Javascript filter is slow

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 Source

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; 
}