Имам много прост масив на 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;
})
В общи линии претърсваме масива и за всеки елемент проверяваме дали първата позиция на този елемент в масива е равна на текущата позиция. Очевидно е, че тези две позиции са различни за дублиращи се елементи. Използвайки третия ("this array") параметър на обратната връзка на филтъра, можем да избегнем затварянето на променливата на масива:
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" се прилага към всеки елемент и елементите с еднакви "keys" се премахват. Тъй като се очаква ключ
да връща примитив, хеш-таблицата ще работи добре тук:
function uniqBy(a, key) {
var seen = {};
return a.filter(function(item) {
var k = key(item);
return seen.hasOwnProperty(k) ? false : (seen[k] = true);
})
}
Особено полезен ключ()
е 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))
Както underscore, така и Lo-Dash предоставят методите uniq
. Техните алгоритми са в общи линии подобни на първия фрагмент по-горе и се свеждат до следното:
var result = [];
a.forEach(function(item) {
if(result.indexOf(item) < 0) {
result.push(item);
}
});
Това е квадратично, но има хубави допълнителни екстри, като например обвиване на native indexOf
, възможност за uniqify по ключ (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 вършат страхотна работа!)
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);
});
Vanilla JS: Премахване на дубликати с помощта на обект като множество
Винаги можете да опитате да го поставите в обект и след това да итерирате през ключовете му:
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"]