Set vs pętla w pętli w filtracji - performance

Question

Robię filtracje tablicy obiektów A na zasadzie jeśli A.name zawiera się w tablicy stringów B to go usuwam.

Skoro ten kod jest O(1):

const input = [ 
  { nick: 'Some name1', x: 19, y: 24, grp: 4, id: '19340' },
  { nick: 'Some name2', x: 20, y: 27, grp: 11, id: '19343' },
  { nick: 'Some name1', x: 22, y: 27, grp: 11, id: '19344' },
  { nick: 'Some name3', x: 22, y: 30, grp: 11, id: '19350' },
  { nick: 'Some name4', x: 22, y: 12, grp: 23, id: '19374' },
  { nick: 'Some name5', x: 22, y: 29, grp: 23, id: '19377' } 
];

const nameToOmit = ['Some name1', 'Some name4'];
const namesToOmitSet = new Set(nameToOmit);

const finalArr = input.filter(it => (!namesToOmitSet.has(it.nick)));
console.log(finalArr)

a ten kod jest O(n):

const input = [ 
  { nick: 'Some name1', x: 19, y: 24, grp: 4, id: '19340' },
  { nick: 'Some name2', x: 20, y: 27, grp: 11, id: '19343' },
  { nick: 'Some name1', x: 22, y: 27, grp: 11, id: '19344' },
  { nick: 'Some name3', x: 22, y: 30, grp: 11, id: '19350' },
  { nick: 'Some name4', x: 22, y: 12, grp: 23, id: '19374' },
  { nick: 'Some name5', x: 22, y: 29, grp: 23, id: '19377' } 
];
const nameToOmit = ['Some name1', 'Some name4'];
const finalArr = [];

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

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

console.log(finalArr)

To jakim cudem ta pętla w pętli jest szybsza wg jsperf? Czy może się myle i ten 1 kod defacto nie jest O(1)? Istnieje jakiś inny, szybszy sposób na przefiltrowanie tej tablicy obiektów w ten sposób jak w przykładach?

Comments

Oba algorytmy mają chyba klasę złożoności O(n), gdzie n to rozmiar wejścia. Zauważ, że w obu przypadkach iterujemy po tablicy wejść bez zagnieżdżeń tej iteracji.

A że jeden sposób jest szybszy od drugiego, może być spowodowane narzutem metody `filter`.

---

Właśnie czytałem gdzieś w necie, że ten 1 sposób jest liniowy ale nie wiem na 100%, bo w końcu skąd ta metoda `.has` by wiedziała czy zawiera się w tej kolekcji bez przelecenia po niej. Może @Comandeer się wypowie :-)

---

Ale metoda `has` nie ma tutaj zbyt wiele do powiedzenia, gdyż nie zależy od rozmiaru wejścia.

---

Mi chodzi o to, że 1 pętla zawsze powinna być szybsza od pętli w pętli. W tym przykładzie drugim zagnieżdżam pętle w pętli a w pierwszym pętle są "ukryte" pod metodami z javascriptu i nie wiem do końca jak to działa.

---

Znalazłem teraz ciekawy wpis na SO, szczególnie zainteresował mnie ten fragment:

 it was about three times faster to remove items from the set (2.6 ms vs 7.1 ms) but things changed drastically for the "big" test

Sprawdziłem swój kod zmieniając tablice input na taką zawierającą kolejno 200 a potem 5k elementów i faktycznie przykład nr 1 zaczyna wygrywać już od tablicy zawierającej 200 elementów.