Кратко — анализ и рекомендации.
1) Ассимптотика исходного алгоритма
- Код: `function uniq(a){ return a.filter((v,i)=>a.indexOf(v)===i); }`
- Каждый вызов `indexOf` — поиск по массиву длины $n$ в среднем за $O(n)$. `filter` вызывает это для каждого из $n$ элементов → время $O(n^2)$.
- Доп. память: только выходной массив (результат) плюс постоянные служебные переменные → дополнительная память $O(1)$ (без учёта результата).
- Особенности равенства: `indexOf` использует строгое сравнение (===), поэтому `NaN` не считается равным самому себе — этот алгоритм не удалит дубликаты `NaN` (каждый `NaN` останется).
2) Когда этот подход плох
- Большие массивы (например, $n$ десятки тысяч и выше) — квадратичная сложность слишком медленная.
- При частых операциях удаления дубликатов в реальном‑времени.
- Для массивов объектов алгоритм использует сравнение по ссылке; если нужен глубокий эквивалент — он не годится.
3) Более эффективные варианты (минимум два), с компромиссами
Вариант A — Set (рекомендуемый для большинства случаев)
- Код: `const uniq = a => [...new Set(a)];` или `Array.from(new Set(a))`
- Время: в среднем $O(n)$ (вставка/поиск в Set амортизированно $O(1)$ → суммарно $O(n)$).
- Память: $O(n)$ дополнительной памяти для Set + результата.
- Компромиссы:
- Сохраняет порядок первых вхождений (Set сохраняет порядок вставки) — значит поведение аналогично исходному в плане порядка.
- Сравнение значений по алгоритму SameValueZero: `NaN` считается равным `NaN`, `+0` и `-0` считаются одинаковыми.
- Не выполняет глубокое сравнение объектов — объекты сравниваются по ссылке.
Вариант B — ручный проход с Set/Map (контроль и возможность подсчёта)
- Код:
const uniq = a => {
const seen = new Set();
const out = [];
for (const v of a) {
if (!seen.has(v)) { seen.add(v); out.push(v); }
}
return out;
};
- Время: амортизированно $O(n)$.
- Память: $O(n)$.
- Плюсы: тот же порядок вставки (устойчивость по первой встрече), гибкость (можно считать вхождения с Map, фильтровать по условиям и т.д.).
Вариант C — сортировка + один проход (если порядок не важен)
- Код: `const uniq = a => { const b = a.slice().sort(); return b.filter((v,i)=>i===0||v!==b[i-1]); };`
- Время: $O(n\log n)$ (сортировка доминирует).
- Память: можно избежать дополнительного места, работая in-place (`a.sort()`), либо копия при необходимости — от $O(1)$ до $O(n)$.
- Компромиссы:
- Портит исходный порядок (если делать in-place) — нельзя сохранить порядок первых вхождений.
- Подходит, когда память критична и $O(n\log n)$ приемлемо.
- Сравнение элементов зависит от используемого компаратора; объекты нужно как‑то сравнивать/проецировать.
Вариант D — удаление по «глубокому» значению (если нужно считать объекты равными по содержимому)
- Подход: сериализация (например, `JSON.stringify`) → Map/Set по строковым ключам, или крипто‑хеш.
- Время: примерно $O(n\cdot s)$, где $s$ — средний размер сериализации; память $O(n)$.
- Компромиссы:
- Нежелательные коллизии/порядок полей в объектах могут приводить к ошибкам; сериализация медленнее; не все значения корректно сериализуются (функции, циклические ссылки).
4) Другие замечания по практике
- Для примитивов и ссылочных уникальностей чаще всего лучший компромисс — `new Set`.
- Если важна строгая семантика `===` с тем, чтобы `NaN` считался уникальным — исходный метод сохраняет все `NaN`, Set — нет; выбор зависит от требований.
- Map/Set в JS имеют амортизированную сложность; в худших теоретических случаях реализации могут деградировать, но на практике это надежно и быстро.
- Для очень больших данных и функций сравнения/хеширования стоит профилировать и выбирать подходящий метод.
Если нужно — могу привести короткие примеры кода для каждого варианта и сравнить на конкретных данных.