У меня есть очень простой массив JavaScript, который может содержать или не содержать дубликаты.
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
Мне нужно удалить дубликаты и поместить уникальные значения в новый массив.
Я мог бы указать на все коды, которые я'пробовал, но я думаю, что это бесполезно, потому что они'не работают. Я также принимаю решения на jQuery.
Используя конструктор Set и синтаксис spread syntax:
uniq = [...new Set(array)];
uniqueArray = a.filter(function(item, pos) {
return a.indexOf(item) == pos;
})
По сути, мы выполняем итерации по массиву и для каждого элемента проверяем, равна ли первая позиция этого элемента в массиве текущей позиции. Очевидно, что для дублирующихся элементов эти две позиции различны. Используя 3-й ("этот массив") параметр обратного вызова фильтра, мы можем избежать закрытия переменной массива:
uniqueArray = a.filter(function(item, pos, self) {
return self.indexOf(item) == pos;
})
function uniq(a) {
var seen = {};
return a.filter(function(item) {
return seen.hasOwnProperty(item) ? false : (seen[item] = true);
});
}
Вот как это обычно делается. Идея заключается в том, чтобы поместить каждый элемент в хэш-таблицу и затем мгновенно проверить его наличие. Это дает нам линейное время, но имеет по крайней мере два недостатка:
uniq([1,"1"])
вернет просто [1]
.uniq([{foo:1},{foo:2}])
вернет только [{foo:1}]
.
Тем не менее, если ваши массивы содержат только примитивы и вам не важны типы (например, это всегда числа), то такое решение будет оптимальным.
Лучшее из двух мировУниверсальное решение объединяет оба подхода: для примитивов используется хэш-поиск, а для объектов - линейный поиск.
function uniq(a) {
var prims = {"boolean":{}, "number":{}, "string":{}}, objs = [];
return a.filter(function(item) {
var type = typeof item;
if(type in prims)
return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
else
return objs.indexOf(item) >= 0 ? false : objs.push(item);
});
}
Другой вариант - сначала отсортировать массив, а затем удалить каждый элемент, равный предыдущему:
function uniq(a) {
return a.sort().filter(function(item, pos, ary) {
return !pos || item != ary[pos - 1];
})
}
sort
все объекты равны). Кроме того, мы молча изменяем исходный массив в качестве побочного эффекта - нехорошо! Однако, если ваши входные данные уже отсортированы, то этот способ подходит (просто удалите sort
из приведенного выше).
Уникальный по...Иногда требуется уникализировать список по каким-то критериям, отличным от равенства, например, отфильтровать объекты, которые отличаются друг от друга, но имеют общее свойство. Это можно сделать элегантно, передав обратный вызов. Этот обратный вызов "ключа" применяется к каждому элементу, и элементы с одинаковыми "ключами" удаляются. Поскольку ожидается, что key
будет возвращать примитив, здесь отлично подойдет хэш-таблица:
function uniqBy(a, key) {
var seen = {};
return a.filter(function(item) {
var k = key(item);
return seen.hasOwnProperty(k) ? false : (seen[k] = true);
})
}
Особенно полезным key()
является JSON.stringify
, который удалит объекты, которые физически отличаются, но "выглядят" одинаково:
a = [[1,2,3], [4,5,6], [1,2,3]]
b = uniqBy(a, JSON.stringify)
console.log(b) // [[1,2,3], [4,5,6]]
Если ключ
не является примитивным, приходится прибегать к линейному поиску:
function uniqBy(a, key) {
var index = [];
return a.filter(function (item) {
var k = key(item);
return index.indexOf(k) >= 0 ? false : index.push(k);
});
}
В ES6 вы можете использовать Set
:
function uniqBy(a, key) {
let seen = new Set();
return a.filter(item => {
let k = key(item);
return seen.has(k) ? false : seen.add(k);
});
}
или Map
:
function uniqBy(a, key) {
return [
...new Map(
a.map(x => [key(x), x])
).values()
]
}
При удалении объектов по ключу вы можете захотеть оставить первый из "одинаковых" объектов или последний.
Для сохранения первого используйте вариант Set
, описанный выше, а для сохранения последнего - Map
:
function uniqByKeepFirst(a, key) {
let seen = new Set();
return a.filter(item => {
let k = key(item);
return seen.has(k) ? false : seen.add(k);
});
}
function uniqByKeepLast(a, key) {
return [
...new Map(
a.map(x => [key(x), x])
).values()
]
}
//
data = [
{a:1, u:1},
{a:2, u:2},
{a:3, u:3},
{a:4, u:1},
{a:5, u:2},
{a:6, u:3},
];
console.log(uniqByKeepFirst(data, it => it.u))
console.log(uniqByKeepLast(data, it => it.u))
И Undererscore, и Lo-Dash предоставляют методы uniq
. Их алгоритмы в основном похожи на первый фрагмент выше и сводятся к следующему:
var result = [];
a.forEach(function(item) {
if(result.indexOf(item) < 0) {
result.push(item);
}
});
Это квадратично, но есть приятные дополнительные возможности, такие как обертывание родного indexOf
, возможность унификации по ключу (iteratee
на их языке), и оптимизация для уже отсортированных массивов.
Если вы используете jQuery и не выносите ничего без доллара перед ним, то это выглядит следующим образом:
$.uniqArray = function(a) {
return $.grep(a, function(item, pos) {
return $.inArray(item, a) === pos;
});
}
Вызовы функций в JavaScript очень дороги, поэтому приведенные выше решения, какими бы лаконичными они ни были, не являются особенно эффективными. Для достижения максимальной производительности замените filter
на цикл и избавьтесь от других вызовов функций:
function uniq_fast(a) {
var seen = {};
var out = [];
var len = a.length;
var j = 0;
for(var i = 0; i < len; i++) {
var item = a[i];
if(seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
Этот кусок уродливого кода делает то же самое, что и фрагмент #3 выше, но на порядок быстрее (по состоянию на 2017 год он'только в два раза быстрее - ребята из JS core проделали огромную работу!)
function uniq(a) {
var seen = {};
return a.filter(function(item) {
return seen.hasOwnProperty(item) ? false : (seen[item] = true);
});
}
function uniq_fast(a) {
var seen = {};
var out = [];
var len = a.length;
var j = 0;
for(var i = 0; i < len; i++) {
var item = a[i];
if(seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
/////
var r = [0,1,2,3,4,5,6,7,8,9],
a = [],
LEN = 1000,
LOOPS = 1000;
while(LEN--)
a = a.concat(r);
var d = new Date();
for(var i = 0; i < LOOPS; i++)
uniq(a);
document.write('<br>uniq, ms/loop: ' + (new Date() - d)/LOOPS)
var d = new Date();
for(var i = 0; i < LOOPS; i++)
uniq_fast(a);
document.write('<br>uniq_fast, ms/loop: ' + (new Date() - d)/LOOPS)
ES6 предоставляет объект Set, который значительно упрощает работу:
function uniq(a) {
return Array.from(new Set(a));
}
или
let uniq = a => [...new Set(a)];
На этой же основе можно построить "ленивую", основанную на генераторах версию uniq
:
function* uniqIter(a) {
let seen = new Set();
for (let x of a) {
if (!seen.has(x)) {
seen.add(x);
yield x;
}
}
}
// example:
function* randomsBelow(limit) {
while (1)
yield Math.floor(Math.random() * limit);
}
// note that randomsBelow is endless
count = 20;
limit = 30;
for (let r of uniqIter(randomsBelow(limit))) {
console.log(r);
if (--count === 0)
break
}
// exercise for the reader: what happens if we set `limit` less than `count` and why
Быстрое и грязное использование jQuery:
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
var uniqueNames = [];
$.each(names, function(i, el){
if($.inArray(el, uniqueNames) === -1) uniqueNames.push(el);
});
Устали видеть все плохие примеры с петель или jQuery. JavaScript имеет идеальные инструменты для этого ныне: сортировка, map и reduce.
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
var uniq = names.reduce(function(a,b){
if (a.indexOf(b) < 0 ) a.push(b);
return a;
},[]);
console.log(uniq, names) // [ 'Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Carl' ]
// one liner
return names.reduce(function(a,b){if(a.indexOf(b)<0)a.push(b);return a;},[]);
Есть, вероятно, более быстрыми способами, но этот довольно неплохой.
var uniq = names.slice() // slice makes copy of array before sorting it
.sort(function(a,b){
return a > b;
})
.reduce(function(a,b){
if (a.slice(-1)[0] !== b) a.push(b); // slice(-1)[0] means last item in array without removing it (like .pop())
return a;
},[]); // this empty array becomes the starting value for a
// one liner
return names.slice().sort(function(a,b){return a > b}).reduce(function(a,b){if (a.slice(-1)[0] !== b) a.push(b);return a;},[]);
В ЕС6 у вас есть наборы и распространения, что делает его очень легким и эффективным, чтобы удалить все дубликаты:
var uniq = [ ...new Set(names) ]; // [ 'Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Carl' ]
Кто-то спрашивал про заказ результатов на основе того, сколько уникальных имен есть:
var names = ['Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Nancy', 'Carl']
var uniq = names
.map((name) => {
return {count: 1, name: name}
})
.reduce((a, b) => {
a[b.name] = (a[b.name] || 0) + b.count
return a
}, {})
var sorted = Object.keys(uniq).sort((a, b) => uniq[a] < uniq[b])
console.log(sorted)
Vanilla JS: Удаление дубликатов с помощью объекта типа Set.
Вы всегда можете попробовать поместить его в объект, а затем выполнить итерацию по его ключам:
function remove_duplicates(arr) {
var obj = {};
var ret_arr = [];
for (var i = 0; i < arr.length; i++) {
obj[arr[i]] = true;
}
for (var key in obj) {
ret_arr.push(key);
}
return ret_arr;
}
Vanilla JS: Удаление дубликатов путем отслеживания уже просмотренных значений (безопасно для порядка).
Или, для безопасной для порядка версии, используйте объект для хранения всех ранее просмотренных значений, и проверяйте значения по нему перед добавлением в массив.
function remove_duplicates_safe(arr) {
var seen = {};
var ret_arr = [];
for (var i = 0; i < arr.length; i++) {
if (!(arr[i] in seen)) {
ret_arr.push(arr[i]);
seen[arr[i]] = true;
}
}
return ret_arr;
}
ECMAScript 6: использование новой структуры данных Set (порядок-безопасность).
ECMAScript 6 добавляет новую структуру данных Set
, которая позволяет хранить значения любого типа. Функция Set.values
возвращает элементы в порядке вставки.
function remove_duplicates_es6(arr) {
let s = new Set(arr);
let it = s.values();
return Array.from(it);
}
Пример использования:
a = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
b = remove_duplicates(a);
// b:
// ["Adam", "Carl", "Jenny", "Matt", "Mike", "Nancy"]
c = remove_duplicates_safe(a);
// c:
// ["Mike", "Matt", "Nancy", "Adam", "Jenny", "Carl"]
d = remove_duplicates_es6(a);
// d:
// ["Mike", "Matt", "Nancy", "Adam", "Jenny", "Carl"]
Он'ь библиотека с множеством функций для обработки массивов.
Это'ы галстук, чтобы идти вместе с jQuery'ы смокинг, и позвоночник.Яш'ы подтяжки.
_.уник(массив, [пользователь], [итератор])
псевдоним: уникальный производит дубликат-бесплатная версия массив, используя === для тестирования объекта равенство. Если вы заранее знаете, что массива сортируется, передает правда на сортировка будет работать гораздо быстрее алгоритма. Если вы хотите вычислять уникальных предметов на основе трансформации, передачи итераторы функция.
[Пример][3]
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
alert(_.uniq(names, false));
Примечание: Ло-тире (с подчеркивание конкурент) предлагает сопоставимы .уник реализация.
Вы можете просто сделать это в JavaScript, с помощью второй - индекс - параметр метод фильтр
:
var a = [2,3,4,5,5,4];
a.filter(function(value, index){ return a.indexOf(value) == index });
или в короткие рука
a.filter((v,i) => a.indexOf(v) == i)
Самым кратким способом, чтобы удалить дубликаты из массива, используя собственные функции JavaScript является использование последовательности, как показано ниже:
vals.sort().reduce(function(a, b){ if (b != a[0]) a.unshift(b); return a }, [])
там's нет необходимости для срез
, ни помощи indexOf
в функцию reduce, как я'вэ видел в других примерах! имеет смысл использовать ее вместе с функцией фильтра:
vals.filter(function(v, i, a){ return i == a.indexOf(v) })
Еще один ЕС6(2015) способ сделать это, что уже работает на нескольких браузерах:
Array.from(new Set(vals))
или даже используя оператор распространение:
[...new Set(vals)]
ура!
время использования.фильтр ()`, как это
в
var actualArr = ['Apple', 'Apple', 'Banana', 'Mango', 'Strawberry', 'Banana'];
console.log('Actual Array: ' + actualArr);
var filteredArr = actualArr.filter(function(item, index) {
if (actualArr.indexOf(item) == index)
return item;
});
console.log('Filtered Array: ' + filteredArr);
в
это может быть сделано короче в ЕС6 в
actualArr.filter((item,index,self) => self.indexOf(item)==index);
Здесь хорошее объяснение выбора.фильтр()`
Простой один я'вэ столкнуться до сих пор. В ЕС6.
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl", "Mike", "Nancy"]
var noDupe = Array.from(new Set(names))
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
Я сделал подробное сравнение простофили удаления в какой-то другой вопрос, но заметив, что это реальное место, я просто хотел поделиться им здесь.
Я считаю, что это лучший способ, чтобы сделать это
в
var myArray = [100, 200, 100, 200, 100, 100, 200, 200, 200, 200],
reduced = Object.keys(myArray.reduce((p,c) => (p[c] = true,p),{}));
console.log(reduced);
в
Ок .. пусть Вам это о(н) и другие, О(П^2) мне было любопытно увидеть тест сравнения между этим уменьшение / таблица и комбинированный фильтр/метод indexOf (я выбираю Jeetendras очень хорошая реализация https://stackoverflow.com/a/37441144/4543207). Я готовлю массива 100к элементов заполняется случайными целыми положительными числами в диапазоне 0-9999 и удаляет дубликаты. Повторяю тест на 10 раз, а средние результаты показывают, что они не подходят по производительности.
Ну ок, пока все хорошо. Но позвольте'ы сделать это правильно на этот раз в стиле ЕС6. Это выглядит так здорово..! Но теперь, как он будет противостоять мощное решение лут для меня загадка. Давайте сначала посмотрим на код, а затем сравнивать его.
в
var myArray = [100, 200, 100, 200, 100, 100, 200, 200, 200, 200],
reduced = [...myArray.reduce((p,c) => p.set(c,true),new Map()).keys()];
console.log(reduced);
в
Вау, это было короткое..! Но как насчет производительности..? Это'красивый... с тяжелым грузом фильтр / помощи indexOf поднял теперь за плечами, я могу проверить массив 1М случайные предметы из положительных целых чисел в диапазоне 0..99999 получить в среднем из 10 последовательных испытаний. Я могу сказать на этот раз это's в реальном матче. Вижу результат по себе :)
в
var ranar = [],
red1 = a => Object.keys(a.reduce((p,c) => (p[c] = true,p),{})),
red2 = a => reduced = [...a.reduce((p,c) => p.set(c,true),new Map()).keys()],
avg1 = [],
avg2 = [],
ts = 0,
te = 0,
res1 = [],
res2 = [],
count= 10;
for (var i = 0; i<count; i++){
ranar = (new Array(1000000).fill(true)).map(e => Math.floor(Math.random()*100000));
ts = performance.now();
res1 = red1(ranar);
te = performance.now();
avg1.push(te-ts);
ts = performance.now();
res2 = red2(ranar);
te = performance.now();
avg2.push(te-ts);
}
avg1 = avg1.reduce((p,c) => p+c)/count;
avg2 = avg2.reduce((p,c) => p+c)/count;
console.log("reduce & lut took: " + avg1 + "msec");
console.log("map & spread took: " + avg2 + "msec");
в
Что бы вы использовать..? Ну не так быстро...! Дон'т быть обманутым. Карты смещения. Теперь посмотрим... во всех вышеперечисленных случаях мы заполняем массив размера n с номерами &ЛТ диапазон; Н. Я имею в виду, у нас есть массив размером 100 и мы заполняем случайными числами 0..9, так что есть определенные дубликаты и "почти" и наверняка каждый номер имеет дубликат. Как насчет того, если мы заполняем массив размером 100 случайными числами 0..9999. Позвольте's теперь смотреть карту играя дома. В этот раз массив из 100к элементов, но случайный диапазон 0..100м. Мы будет сделать 100 последовательных тестов в среднем результаты. Ок, давайте's смотреть ставки..! <- не опечатка
в
var ranar = [],
red1 = a => Object.keys(a.reduce((p,c) => (p[c] = true,p),{})),
red2 = a => reduced = [...a.reduce((p,c) => p.set(c,true),new Map()).keys()],
avg1 = [],
avg2 = [],
ts = 0,
te = 0,
res1 = [],
res2 = [],
count= 100;
for (var i = 0; i<count; i++){
ranar = (new Array(100000).fill(true)).map(e => Math.floor(Math.random()*100000000));
ts = performance.now();
res1 = red1(ranar);
te = performance.now();
avg1.push(te-ts);
ts = performance.now();
res2 = red2(ranar);
te = performance.now();
avg2.push(te-ts);
}
avg1 = avg1.reduce((p,c) => p+c)/count;
avg2 = avg2.reduce((p,c) => p+c)/count;
console.log("reduce & lut took: " + avg1 + "msec");
console.log("map & spread took: " + avg2 + "msec");
в
Сейчас это впечатляющий камбэк на карте()..! Может быть, теперь вы можете сделать лучшее решение, когда вы хотите удалить дубликаты.
Ну ок, теперь мы все счастливы. Но главную роль всегда приходит с некоторым аплодисменты. Я уверен, что некоторые из вас задавались вопросом, что объект будет делать. Теперь, поскольку мы открыты для ES6 и мы знаем, что карта является победителем предыдущих игр давайте сравним карту с установить в качестве окончательной. Типичный Реал игре против Барселоны на этот раз... или это? Позвольте'посмотрим, кто победит в Эль-Классико :)
в
var ranar = [],
red1 = a => reduced = [...a.reduce((p,c) => p.set(c,true),new Map()).keys()],
red2 = a => Array.from(new Set(a)),
avg1 = [],
avg2 = [],
ts = 0,
te = 0,
res1 = [],
res2 = [],
count= 100;
for (var i = 0; i<count; i++){
ranar = (new Array(100000).fill(true)).map(e => Math.floor(Math.random()*10000000));
ts = performance.now();
res1 = red1(ranar);
te = performance.now();
avg1.push(te-ts);
ts = performance.now();
res2 = red2(ranar);
te = performance.now();
avg2.push(te-ts);
}
avg1 = avg1.reduce((p,c) => p+c)/count;
avg2 = avg2.reduce((p,c) => p+c)/count;
console.log("map & spread took: " + avg1 + "msec");
console.log("set & A.from took: " + avg2 + "msec");
в
Ух ты.. человек!.. Ну неожиданно это не't поворачивайте на Эль-Классико на все. Больше похоже на ФК Барселона против Осасуна ка :))
Решения 1
Array.prototype.unique = function() {
var a = [];
for (i = 0; i < this.length; i++) {
var current = this[i];
if (a.indexOf(current) < 0) a.push(current);
}
return a;
}
Решение 2 (с использованием набора)
Array.prototype.unique = function() {
return Array.from(new Set(this));
}
Тест
var x=[1,2,3,3,2,1];
x.unique() //[1,2,3]
Производительность
Когда я тестировал обе реализации (С и без) для работы в Chrome, я обнаружил, что один комплект-это гораздо быстрее!
в
Array.prototype.unique1 = function() {
var a = [];
for (i = 0; i < this.length; i++) {
var current = this[i];
if (a.indexOf(current) < 0) a.push(current);
}
return a;
}
Array.prototype.unique2 = function() {
return Array.from(new Set(this));
}
var x=[];
for(var i=0;i<10000;i++){
x.push("x"+i);x.push("x"+(i+1));
}
console.time("unique1");
console.log(x.unique1());
console.timeEnd("unique1");
console.time("unique2");
console.log(x.unique2());
console.timeEnd("unique2");
в
Ниже приводится более 80% быстрее, чем у перечисленных метод jQuery (см. тесты ниже). Это ответ на подобный вопрос несколько лет назад. Если я наткнусь на человека, который изначально предлагал я буду размещать кредит. Чистом JavaScript.
var temp = {};
for (var i = 0; i < array.length; i++)
temp[array[i]] = true;
var r = [];
for (var k in temp)
r.push(k);
return r;
Мое сравнение теста: http://jsperf.com/remove-duplicate-array-tests
Лучшие ответы имеют сложность О(Н²), но это может быть сделано только с `О(Н) с помощью объекта в качестве хэш:
function getDistinctArray(arr) {
var dups = {};
return arr.filter(function(el) {
var hash = el.valueOf();
var isDup = dups[hash];
dups[hash] = true;
return !isDup;
});
}
Это будет работать для строк, чисел и дат. Если Ваш массив содержит объекты, указанные выше меры выиграл'т работу, потому что когда приводится к строке, они будут иметь значение в "[Object объект]" У
(или нечто подобное) и это'т подходят в качестве значения подстановки. Вы можете получить `О(N) - реализация объектов путем установки флага на сам объект:
function getDistinctObjArray(arr) {
var distinctArr = arr.filter(function(el) {
var isDup = el.inArray;
el.inArray = true;
return !isDup;
});
distinctArr.forEach(function(el) {
delete el.inArray;
});
return distinctArr;
}
2019 редактировать: современные версии JavaScript сделать это гораздо проще решать проблемы. Используя "набор" будет работать, независимо от того, Ваш массив содержит объекты, строки, числа, или любого другого типа.
function getDistinctArray(arr) {
return [...new Set(arr)];
}
Реализация настолько проста, определяя функция больше не требуется.
В ECMAScript 6 (ака в ECMAScript 2015), установить
может использоваться, чтобы отфильтровать дубликаты. Затем его можно преобразовать обратно в массив, используя оператор распространение.
var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"],
unique = [...new Set(names)];
Вот простой ответ на вопрос.
var names = ["Alex","Tony","James","Suzane", "Marie", "Laurence", "Alex", "Suzane", "Marie", "Marie", "James", "Tony", "Alex"];
var uniqueNames = [];
for(var i in names){
if(uniqueNames.indexOf(names[i]) === -1){
uniqueNames.push(names[i]);
}
}
Простой, но эффективный метод, чтобы использовать метод фильтр
в сочетании с функцией фильтра(индекс, значение){ возвращение этого.метод indexOf(значение) == индекс }`.
в
в
Варе данных = [2,3,4,5,5,4]; функция фильтра ВАР = (индекс, значение){ возвращение этого.метод indexOf(значение) == индекс }; ВАР filteredData = данные.фильтр(фильтр данных );
документ.тела.innerHTML будет = '<заранее>' + в формате JSON.преобразовать в строки(filteredData, значение null, '\т') + '</до>';
в
См. Также [эта скрипка][4].
Так что варианты есть:
let a = [11,22,11,22];
let b = []
b = [ ...new Set(a) ];
// b = [11, 22]
b = Array.from( new Set(a))
// b = [11, 22]
b = a.filter((val,i)=>{
return a.indexOf(val)==i
})
// b = [11, 22]