skone skone - 5 months ago 19
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

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