Премахване на дублиращи се стойности от масив JS

Имам много прост масив на JavaScript, който може да съдържа или да не съдържа дубликати.

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

Трябва да премахна дубликатите и да поставя уникалните стойности в нов масив.

Бих могъл да посоча всички кодове, които съм'пробвал, но мисля, че е'безполезно, защото не работят. Приемам и решения на jQuery.

Подобен въпрос:

John Slegers
Редактиран въпрос Направете май 2018 в 10:47
Програмиране
arrays javascript unique duplicates
Направете февруари 2012 в 2:53
19 изгледи

TL;DR

Използване на конструктора 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;
})

Въпреки че е кратък, този алгоритъм не е особено ефективен за големи масиви (квадратично време). Hashtables на помощ

function uniq(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    });
}

Обикновено това се прави по този начин. Идеята е всеки елемент да се постави в хаштабъл и след това да се проверява незабавно за наличието му. Това ни дава линейно време, но има поне два недостатъка:

  • тъй като хеш ключовете могат да бъдат само низове в JavaScript, този код не прави разлика между числа и "числови низове". Това означава, че 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);
    });
}

сортиране | uniq

Друг вариант е първо да сортирате масива и след това да премахнете всеки елемент, равен на предходния:

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

ES6 предоставя обекта Set, който прави нещата много по-лесни:

function uniq(a) {
   return Array.from(new Set(a));
}

или

let uniq = a => [...new Set(a)];

Обърнете внимание, че за разлика от питон, в ES6 множествата се итерират в реда на вмъкване, така че този код запазва реда на оригиналния масив. Въпреки това, ако имате нужда от масив с уникални елементи, защо да не използвате множества от самото начало? Генератори

На същата основа може да се изгради "мързелива", базирана на генератори версия на 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
georg
Редактиран отговор Направете април 2019 в 10:14
Коментари (38)
Решение

Бързо и мръсно използване на 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);
});
Martijn Pieters
Редактиран отговор Направете декември 2016 в 10:53
Коментари (15)

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"]
Casey Kuball
Редактиран отговор Направете октомври 2016 в 5:11
Коментари (7)