CODEWITHSUNDEEP
javascriptarraysfilter
BT101
BT101

Reputation: 3836

Array filter - get rid of O(n^2)

I need to perform 2 filters on array of objects which is very big (over 200k elements) so I want my code to be as fast as possible in javascript.

First filter is simple because I just need to delete elements which are empty (null):

let validArr = originalArr.filter(el => { return el != null });

Second filter is to check if validArr[i].name is equal to one of elements from other array. Currently I do it like this:

for(let i = 0, l = validArr.length; i < l; i++) {
    if (findInArray(validArr[i].name, otherArr)) {
        finalArr.push({
            name: validNpc[i].nick,
            id: validNpc[i].id
        });
    }
}

const findInArray = (val, arr) => {
    for(let i = 0, l = arr.length; i < l; i++) {
        if(arr[i] === val) return true;
    }
    return false;
};

In loop I have micro optimization but there is O(n^2) which I want to refactor but I don't know how.

Upvotes: 3

Views: 270

Answers (2)

Maheer Ali
Maheer Ali

Reputation: 36594

You can use Set and has method which have O(1) time complexity

otherArr = new Set(otherArr);
for(let i = 0, l = validArr.length; i < l; i++) {
    if (findInArray(validArr[i].name, otherArr)) {
        finalArr.push({
            name: validNpc[i].nick,
            id: validNpc[i].id
        });
    }
}

const findInArray = (val, arr) => {
    return arr.has(val)
};

You can clean up your code using forEach()

otherArr = new Set(otherArr)
const finalArr = [];
validArr.forEach(x => {
    if(otherArr.has(x.name)){
       finalArr.push({ name:x.nick, id:x.id })
    }
})

Upvotes: 2

Jonas Wilms
Jonas Wilms

Reputation: 138457

Turn otherArr into a Set, then lookup takes O(1) and the overall loop is O(n):

  const names = new Set(otherArr);

  const result = validArr
    .filter(it => names.has(it.name))
    .map(({ nick, id }) => ({ name: nick, id }));

Upvotes: 6

Related Questions