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?

It would use native code for the iteration rather than an interpreted for loop. — Heretic Monkey, Jun 20 '16 at 16:36
@MikeMcCaughan Does not make it faster, see http://stackoverflow.com/questions/21748670/why-are-native-array-functions-are-so-much-slower-then-loop — Ruan Mendes, Jun 20 '16 at 16:40
Two-year old questions pointing to proof from a website that's offline... Not the greatest relevance, but I'll concede the point. I asked the question since it seemed obvious to use the thing called "filter" when you want to filter. — Heretic Monkey, Jun 20 '16 at 16:47

Ruan Mendes · Accepted Answer · 2016-06-20T17:02:27.083

8

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

edited Jun 20 '16 at 17:02

answered Jun 20 '16 at 16:34

Ruan Mendes

90,375
31
153
217

Little type though. styleNumMap[styleNum].push(style); should be styleNumMap[style.styleNum].push(style); – Sonu Kapoor Jun 20 '16 at 16:50
1

Lovely, transferring from array to keyed object improved my loading time by 12 seconds on an array of 1600 elements. – Djov May 30 '22 at 16:54

Javascript filter is slow

1 Answers1