Algorytmy i struktury danych · Senior · Pytanie 75 z 75
Dlaczego Array.prototype.indexOf wewnątrz filter to częste ukryte O(n²) na code review?
const unique = items.filter((x, i) => items.indexOf(x) === i);- 1
indexOfsortuje tablicę przed wyszukiwaniem - ✓Poprawna odpowiedź:
indexOfprzegląda tablicę dla każdego elementufilter - 3
filterkopiuje całą tablicę dla każdego elementu
Wyjaśnienie
Każdy z n callbacków robi wyszukiwanie liniowe, więc 10 000 elementów to do 100 milionów porównań. [...new Set(items)] robi to samo w O(n). Wyłapywanie takich zagnieżdżonych przejść to typowa umiejętność seniora na review.