Лучший способ удалить повторяющиеся данные в массиве JavaScript
Предположим, у вас есть такой список:
[1, 1, 2, 2, 1, 2, 2, 2]
Какой наиболее эффективный способ удалить повторяющиеся данные (а не дубликаты), чтобы ни один элемент не появлялся после себя? Для этого примера результат должен быть:
[1, 2, 1, 2]
Например, это можно решить с помощью filter или цикла for, запоминающего последний элемент. Но есть ли что-то более элегантное? Или какой вариант наиболее эффективен?
for цикл:
const arr = [1, 1, 2, 2, 1, 2, 2, 2];
const result = [arr[0]];
let lastElement = arr[0];
for (let i = 1, n = arr.length; i < n; ++i) {
if (arr[i] !== lastElement) {
lastElement = arr[i];
result.push(lastElement);
}
}
filter:
const result = [1, 1, 2, 2, 1, 2, 2, 2].filter((element, index, arr) => element !== arr[index - 1]);
Не уверен, что понимаю, почему за этот идентификатор проголосовали против... есть несколько вариантов сделать это, речь идет не о дублировании, и проблема существует на практике. Рад удалить вопрос, если он воспринят так негативно.
я не делал, но попытка необходима. что пошло не так?
Пользуюсь этим уже давно, никогда не знал, что попытка необходима. Я могу добавить решение, которое я написал здесь, но меня больше всего интересовало, как другие люди решат эту проблему. Я чувствую, что попытка искажает ответы, но я могу дать один. Однако я думаю, что, возможно, мне лучше удалить вопрос. Ответы на вопрос типа «Как лучше всего удалить дубликаты» помогли мне больше всего, поэтому я подумал, что это интересно.
Попробуйте jsperf и убедитесь сами - в противном случае это будет мнение, которое вы запрашиваете, и это противоречит рекомендациям SO.
@mplungjan: Я не думаю, что вопрос о том, как лучше всего делать что-то в программировании, всегда попадает в категорию «основанных на мнении». Есть масса объективных преимуществ, которые не всегда можно предусмотреть заранее.
кстати, почему бы не начать с индекса 1? для непустых массивов значение нулевого индекса всегда уникально.
@NinaScholz Его код пока самый быстрый. Можете ли вы сделать быстрее? jsperf.app/popose/2
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 3
Просто отфильтруйте со сравнением с предыдущим пунктом:
const result = [1, 1, 2, 2, 1, 2, 2, 2].filter((item, idx, arr) => !idx || item !== arr[idx - 1]);
console.info(result);Если вы хотите, чтобы это было быстро и с большим количеством элементов, вы можете предварительно выделить массив результатов:
const data = [1, 1, 2, 2, 1, 2, 2, 2];
const result = Array(data.length);
let j = 1;
let lastElement = result[0] = data[0];
for (let i = 1, n = data.length; i < n; ++i) {
if (data[i] !== lastElement) {
result[j++] = lastElement = data[i];
}
}
result.length = j;
console.info(result);И эталон:
` Chrome/123
--------------------------------------------------------------------------------------------------------
> n=8 | n=80 | n=800 | n=8000
Alexander for+preallocate 1.23x x10m 311 | ■ 1.00x x1m 125 | ■ 1.00x x1m 1004 | ■ 1.00x x100k 1035
Thorben Croisé (OP) ■ 1.00x x10m 253 | ■ 1.00x x1m 125 | 1.62x x100k 163 | 1.37x x10k 142
mplungjan for loop 1.19x x10m 302 | 1.36x x1m 170 | 1.88x x100k 189 | 1.86x x10k 192
Alexander 1.01x x10m 255 | 1.18x x1m 147 | 2.12x x100k 213 | 2.69x x10k 278
--------------------------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `
const $chunk = [1, 1, 2, 2, 1, 2, 2, 2];
const $input = [];
const data = $input;
// @benchmark mplungjan for loop
const removeRepeated = (data) => {
const result = [];
for (let i = 0, len = data.length; i < len; i++) {
if (i === 0 || data[i] !== data[i - 1]) {
result.push(data[i]);
}
}
return result;
};
removeRepeated(data);
// @benchmark Alexander
data.filter((item, idx, arr) => !idx || item !== arr[idx - 1]);
// @benchmark Alexander for+preallocate
{
const result = Array(data.length);
let j = 1;
let lastElement = result[0] = data[0];
for (let i = 1, n = data.length; i < n; ++i) {
if (data[i] !== lastElement) {
result[j++] = lastElement = data[i];
}
}
result.length = j;
result;
}
// @benchmark Thorben Croisé (OP)
{
const result = [data[0]];
let lastElement = data[0];
for (let i = 1, n = data.length; i < n; ++i) {
if (data[i] !== lastElement) {
lastElement = data[i];
result.push(lastElement);
}
}
result;
}
/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));Пожалуйста, попробуйте также использовать 10000 элементов.
@mplungjan, я думаю, разница между 10 000 и 8 000 будет минимальной, это не порядок
Извините, я не заметил. Я видел только [1, 1, 2, 2, 1, 2, 2, 2] Итак, 8000 — это 8000 раз или элементов?
@mplungjan нет, это общее количество элементов, оно контролируется const $chunks = [1, 10, 100, 1000] (по умолчанию, поэтому не объявлено), если вы добавите 10 000 к $chunks, последний контрольный показатель будет 80 000 элементов. это описано в документации. количество элементов равно количеству кусков * $chunk.length
Значит, зеленые квадраты лучше?
@mplungjan да, лучшее, лучшим решением считается наибольшее количество элементов (последний столбец, отсортированный первым)
Не могли бы вы добавить пример тринкота?
@mplungjan trincots требует особого обращения. Я поддерживаю функцию $clone() для клонирования данных перед циклом, но не уверен, работает ли она как с внутренними, так и с чистыми тестами. это сложный случай (смешайте оба подхода). в противном случае нет смысла запускать следующие циклы на уже мутированном массиве.
Вы указали мое имя в неправильном коде
@mplungjan лол, тогда ОП выиграл битву)
Ага. Кажется, да, и тринкот в целом.
@mplungjan я заранее выделил результат, это еще быстрее))
Сокращение и фильтрация обычно выполняются медленнее для больших массивов, чем для циклов.
JSPerf на моем коде, коде Александра, Trinco't и OP: https://jsperf.app/popose/5
Ваш цикл for быстрее моего (но ненамного)
10000 элементов
const removeRepeated = (data) => {
const result = [];
for (let i = 0, len = data.length; i < len; i++) {
if (i === 0 || data[i] !== data[i - 1]) {
result.push(data[i]);
}
}
return result;
};
// Example usage
const data = [1, 1, 2, 2, 1, 2, 2, 2];
const result = removeRepeated(data);
console.info(result); // Expected output: [1, 2, 1, 2]я ошибался насчет jsperf, так как вы тестировали 10000 элементов, результаты кажутся одинаковыми, но я предпочитаю свой тест, так как могу внедрить его здесь)
Ваш код кажется вполне оптимальным. Только одно замечание: он не будет работать с пустым массивом в качестве входных данных, поэтому я бы предложил добавить для этого защиту.
Если допустимо выполнить действие на месте, мутируя входной массив вместо создания нового, вы все равно можете получить некоторый выигрыш во времени:
function removeRepetitionsInplace(arr) {
if (arr.length < 2) return;
let k = 0;
let lastElement = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] !== lastElement) {
lastElement = arr[++k] = arr[i];
}
}
arr.length = k + 1;
}
См. тесты производительности по адресу https://jsperf.app/popose/3 (добавлен тестовый пример в mplungjan's).
А если измените for (let i=1, n=data.length; i<n;i++), вы сохраните расчет jsperf.app/popose/4
mplugjan, я считаю, что этот тип оптимизации уже выполняется JS-движками, поэтому повторных вычислений на самом деле не происходит. См. Производительность цикла for: сохранение длины массива в переменной
Что ж, НЕКОТОРЫЕ специалисты в этом вопросе, похоже, со мной согласны jsben.ch/y3SpC
Кроме того, я ДОВОЛЬНО уверен, что разница будет больше, если перебрать коллекцию DOM.
Да, я ОЧЕНЬ уверен в этом, особенно если это живая коллекция. Но мы здесь обсуждаем массивы.
Я использую его, когда вспоминаю. Это ничего не стоит и достаточно защитно, чтобы я мог его использовать.
какой на самом деле твой путь?