Фильтр массива - избавьтесь от O (n ^ 2)

Question

Мне нужно выполнить 2 фильтра для массива объектов, который очень большой (более 200 тыс. Элементов), поэтому я хочу, чтобы мой код был максимально быстрым в javascript.

Первый фильтр прост, потому что мне просто нужночтобы удалить пустые элементы: (null):

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

Второй фильтр должен проверить, равен ли validArr[i].name одному из элементов из другого массива.В настоящее время я делаю это так:

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

В цикле у меня микрооптимизация, но есть O (n ^ 2), которую я хочу реорганизовать, но я не знаю, как.

Answer 1

Превратите otherArr в Set, затем поиск займет O (1), и общий цикл будет O (n):

  const names = new Set(otherArr);

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

Answer 2

Вы можете использовать Set и has метод с O (1) временной сложностью

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

Вы можете очистить свой код, используя forEach()

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