Уникальный () для массивов в JavaScript

Как все знают, в javascript нет встроенной функции для удаления дубликатов из массива. Я заметил, что этого также не хватает в jQuery (который имеет уникальную функцию только для выбора DOM), и наиболее распространенный фрагмент, который я нашел, проверяет весь массив и его подмножество для каждого элемента (я думаю, не очень эффективный), например:

for (var i = 0; i < arr.length; i++)
    for (var j = i + 1; j < arr.length; j++)
        if (arr[i] === arr[j])
            //whatever

поэтому я сделал свой собственный:

function unique (arr) {
    var hash = {}, result = [];
    for (var i = 0; i < arr.length; i++)
        if (!(arr[i] in hash)) { //it works with objects! in FF, at least
            hash[arr[i]] = true;
            result.push(arr[i]);
        }
    return result;
}

Интересно, есть ли какой-либо другой алгоритм, принятый как лучший для этого случая (или если вы видите какой-либо очевидный недостаток, который можно исправить), или что вы делаете, когда вам это нужно в javascript (я знаю, что jQuery не является только рамки и некоторые другие могут иметь это уже покрыто).

Источник

5 ответов

Решение

Использование литерала объекта - это именно то, что я хотел бы сделать. Многие люди часто пропускают эту технику, вместо этого выбирая типичные обходы массивов в качестве исходного кода, который вы показали. Единственной оптимизацией было бы избежать arr.length искать каждый раз. Кроме того, O(n) примерно так же хорош, как вы получаете за уникальность и намного лучше, чем оригинальный пример O(n^2).

function unique(arr) {
    var hash = {}, result = [];
    for ( var i = 0, l = arr.length; i < l; ++i ) {
        if ( !hash.hasOwnProperty(arr[i]) ) { //it works with objects! in FF, at least
            hash[ arr[i] ] = true;
            result.push(arr[i]);
        }
    }
    return result;
}

// * Edited to use hasOwnProperty per comments

Время сложностей, чтобы подвести итог

  f()    | unsorted | sorted | objects | scalar | library
____________________________________________________________
unique   |   O(n)   |  O(n)  |   no    |  yes   |    n/a
original |  O(n^2)  | O(n^2) |   yes   |  yes   |    n/a
uniq     |  O(n^2)  |  O(n)  |   yes   |  yes   | Prototype
_.uniq   |  O(n^2)  |  O(n)  |   yes   |  yes   | Underscore

Как и в большинстве алгоритмов, есть компромиссы. Если вы сортируете только скалярные значения, ваши модификации исходного алгоритма дают наиболее оптимальное решение. Тем не менее, если вам нужно отсортировать нескалярные значения, используйте или имитируйте uniq метод любой из обсуждаемых библиотек будет вашим лучшим выбором.

Источник

Веселье с удовольствием (ction)

function uniqueNum(arr) {
    return Object.keys(arr.reduce(
        function(o, x) {o[x]=1; return o;}, {})).map(Number);
}
Источник

Я думаю, что ваша версия не будет работать, когда у вас есть объекты или функции в массиве, которые дают строковое представление, как [Object object], Потому что у вас могут быть только строки в качестве ключей в объектах (здесь в объекте "хэш"). Вам нужно будет зацикливаться на массиве результатов, чтобы узнать, существует ли новая запись. Это все равно будет быстрее, чем первый метод.

У прототипа JS есть метод " uniq", вы можете получить от него вдохновение.

Источник

Я ни в коем случае не эксперт по алгоритмам, но я слежу за underscore.js. У них есть это как функция с именем uniq:

http://documentcloud.github.com/underscore/

Я посмотрел код в их библиотеке и скопировал его сюда для справки (не мой код, этот код принадлежит underscore.js):

// Produce a duplicate-free version of the array. If the array has already
// been sorted, you have the option of using a faster algorithm.
_.uniq = function(array, isSorted) {
    return _.reduce(array, [], function(memo, el, i) {
        if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el);
        return memo;
    });
};

РЕДАКТИРОВАТЬ: вам нужно пройтись по остальной части кода underscore.js, и я чуть не вынул этот код из-за него. Я оставил фрагмент кода на всякий случай, если он все еще был полезен.

Источник

К сожалению, у объектов JS нет идентификатора, доступного из языка - как упоминали другие авторы, использование объектов в качестве ключей в словаре не удастся, если разные объекты имеют одинаковые строковые представления и нет id() функция на языке.

Есть способ избежать проверки всех пар O(n^2) для === идентичность, если вы можете изменить объекты. Выберите случайную строку, обойдите массив один раз, чтобы убедиться, что ни у одного объекта нет свойства с таким именем, затем просто выполните arr[i][randomPropertyName]=1 для каждого i, Если следующий объект в массиве уже имеет это свойство, то он является дубликатом.

К сожалению, вышесказанное будет работать только для изменяемых объектов. Сбой для значений массива, которые не позволяют устанавливать свойства (например, целые числа, 42['random']=1 просто не работает:()

Источник
Другие вопросы по тегам