Usuń zduplikowane wartości z tablicy JS

Mam bardzo prostą tablicę JavaScript, która może, ale nie musi zawierać duplikatów.

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

Muszę usunąć duplikaty i umieścić unikalne wartości w nowej tablicy.

Mógłbym wskazać wszystkie kody, które I've próbował, ale myślę, że to's bezużyteczne, ponieważ oni nie'działają. Akceptuję również rozwiązania jQuery.

Podobne pytanie:

John Slegers
Edytowane pytanie 1. maja 2018 в 10:47
Programowanie
arrays javascript unique duplicates
10. lutego 2012 в 2:53
25 opinie

TL;DR

Używając konstruktora Set i składni spread syntax:

uniq = [...new Set(array)];

"Smart", ale naïve sposób

uniqueArray = a.filter(function(item, pos) {
    return a.indexOf(item) == pos;
})

Zasadniczo iterujemy nad tablicą i dla każdego elementu sprawdzamy, czy pierwsza pozycja tego elementu w tablicy jest równa bieżącej pozycji. Oczywiście, te dwie pozycje są różne dla zduplikowanych elementów. Przy pomocy trzeciego ("ta tablica") parametru wywołania zwrotnego filtra możemy uniknąć zamknięcia zmiennej tablicowej:

uniqueArray = a.filter(function(item, pos, self) {
    return self.indexOf(item) == pos;
})

Choć zwięzły, algorytm ten nie jest szczególnie wydajny dla dużych tablic (czas kwadratowy). Hashtables na ratunek

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

Tak to się zwykle robi. Chodzi o to, aby umieścić każdy element w tablicy hashtable, a następnie natychmiast sprawdzić jego obecność. To daje nam czas liniowy, ale ma co najmniej dwie wady:

  • ponieważ klucze haszujące mogą być tylko łańcuchami w JavaScript, ten kod nie rozróżnia liczb i "łańcuchów numerycznych". To znaczy, uniq([1,"1"]) zwróci po prostu [1].

  • z tego samego powodu, wszystkie obiekty będą uważane za równe: uniq([{foo:1},{foo:2}]) zwróci tylko [{foo:1}]. To powiedziawszy, jeśli twoje tablice zawierają tylko prymitywy i nie dbasz o typy (np. to'zawsze liczby), to rozwiązanie jest optymalne. To, co najlepsze z dwóch światów

    Uniwersalne rozwiązanie łączy oba podejścia: używa hash lookups dla prymitywów i wyszukiwania liniowego dla obiektów.

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);
    });
}

sort | uniq

Inną opcją jest posortowanie tablicy jako pierwszej, a następnie usunięcie każdego elementu równego poprzedniemu:

function uniq(a) {
    return a.sort().filter(function(item, pos, ary) {
        return !pos || item != ary[pos - 1];
    })
}

Ponownie, to nie działa z obiektami (ponieważ wszystkie obiekty są równe dla sort). Dodatkowo, po cichu zmieniamy oryginalną tablicę jako efekt uboczny - nie jest to dobre! Jednakże, jeśli twoje dane wejściowe są już posortowane, to jest to droga do zrobienia (po prostu usuń sort z powyższego). Unikalne przez...

Czasami pożądane jest, aby zunifikować listę na podstawie innych kryteriów niż tylko równość, na przykład, aby odfiltrować obiekty, które są różne, ale mają wspólną właściwość. Można to zrobić w elegancki sposób, przekazując wywołanie zwrotne. Ten "klucz" jest stosowany do każdego elementu, a elementy z równymi "kluczami" są usuwane. Ponieważ oczekuje się, że key zwróci prymityw, tablica hash będzie działać dobrze tutaj:

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

Szczególnie użytecznym key() jest JSON.stringify, który usunie obiekty, które są fizycznie różne, ale "wyglądają" tak samo:

a = [[1,2,3], [4,5,6], [1,2,3]]
b = uniqBy(a, JSON.stringify)
console.log(b) // [[1,2,3], [4,5,6]]

Jeśli klucz nie jest prymitywny, trzeba uciec się do wyszukiwania liniowego:

function uniqBy(a, key) {
    var index = [];
    return a.filter(function (item) {
        var k = key(item);
        return index.indexOf(k) >= 0 ? false : index.push(k);
    });
}

W ES6 możesz użyć 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);
    });
}

lub Map:

function uniqBy(a, key) {
    return [
        ...new Map(
            a.map(x => [key(x), x])
        ).values()
    ]
}

które również działają z kluczami nieprymitywnymi. Pierwszy czy ostatni?

Podczas usuwania obiektów według klucza, możesz chcieć zachować pierwszy z "równych" obiektów lub ostatni. Użyj powyższego wariantu Set aby zachować pierwszy, oraz Map aby zachować ostatni:

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))

Biblioteki

Zarówno underscore jak i Lo-Dash dostarczają metod uniq. Ich algorytmy są w zasadzie podobne do pierwszego powyższego snippetu i sprowadzają się do tego:

var result = [];
a.forEach(function(item) {
     if(result.indexOf(item) < 0) {
         result.push(item);
     }
});

To jest quadratic, ale są tam miłe dodatkowe bajery, jak owijanie natywnego indexOf, możliwość uniqify przez klucz (iteratee w ich języku), i optymalizacje dla już posortowanych tablic. Jeśli używasz jQuery i nie możesz znieść niczego bez dolara przed nim, to idzie to tak:

  $.uniqArray = function(a) {
        return $.grep(a, function(item, pos) {
            return $.inArray(item, a) === pos;
        });
  }

co jest, ponownie, wariacją pierwszego snippetu. Wydajność

Wywołania funkcji są drogie w JavaScript, dlatego powyższe rozwiązania, tak zwięzłe jak są, nie są szczególnie wydajne. Aby uzyskać maksymalną wydajność, zastąp filter pętlą i pozbądź się innych wywołań funkcji:

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;
}

Ten kawałek brzydkiego kodu robi to samo, co snippet #3 powyżej, ale o rząd wielkości szybciej (od 2017 roku jest'tylko dwa razy szybszy - ludzie z JS core robią świetną robotę!)

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 dostarcza obiekt Set, który znacznie ułatwia sprawę:

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

lub

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

Zauważ, że w przeciwieństwie do pythona, zestawy ES6 są iterowane w kolejności wstawiania, więc ten kod zachowuje kolejność oryginalnej tablicy. Jednakże, jeśli potrzebujesz tablicy z unikalnymi elementami, dlaczego nie użyć zestawów od samego początku? Generatory

Na tej samej zasadzie można zbudować "leniwą", opartą na generatorach wersję uniq:

  • weź następną wartość z argumentu
  • jeśli jest już widziana, pomiń ją
  • w przeciwnym razie, zwróć ją i dodaj do zbioru już widzianych wartości
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
Edytowana odpowiedź 9. kwietnia 2019 в 10:14
Komentarze (38)
Rozwiązanie

Szybkie i brudne użycie 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
Edytowana odpowiedź 26. grudnia 2016 в 10:53
Komentarze (15)

Vanilla JS: Usuń duplikaty używając obiektu jak zbioru.

Zawsze możesz spróbować umieścić go w obiekcie, a następnie iterować po jego kluczach:

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: Usuń duplikaty poprzez śledzenie już widzianych wartości (order-safe).

Lub, dla wersji bezpiecznej dla porządku, użyj obiektu do przechowywania wszystkich wcześniej widzianych wartości i sprawdź wartości z nim przed dodaniem do tablicy.

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: Użyj nowej struktury danych Set (order-safe).

ECMAScript 6 dodaje nową strukturę danych Set, która pozwala na przechowywanie wartości dowolnego typu. Struktura Set.values zwraca elementy w kolejności wstawiania.

function remove_duplicates_es6(arr) {
    let s = new Set(arr);
    let it = s.values();
    return Array.from(it);
}

Przykładowe użycie:

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
Edytowana odpowiedź 18. października 2016 в 5:11
Komentarze (7)