Какой самый быстрый порядок величины, что вычитание массива может быть реализовано в JavaScript?

Question

Мне нужна функция вычитания, которая будет принимать два массива и возвращать все элементы массива 1, которых нет в массиве 2.

что самое быстрое, что это может быть реализовано в js? Это о (п)?

Answer 1

Другим вариантом, более быстрым временем O (n), но с двойной памятью (все еще линейной), является создание собственной реализации хеш-карты.Выполните цикл по одному массиву и хэшируйте все элементы.Сохраните (hash, object) пару в другом массиве, назовите его hash array.Теперь переберите массив 2 и хэшируйте каждый элемент.Пусть хеш будет позицией в массиве хешей, чтобы вы могли видеть, есть ли у вас коллизия.Если у вас есть проверка столкновений, совпадает ли объект в массиве хэшей с объектом в текущем массиве (над которым вы зацикливаетесь).

Answer 2

Вот реализация хэш-таблицы (с использованием объекта javascript в качестве хэша), которая более чем в 100 раз быстрее (в Chrome) с массивами большего размера, чем поиск методом перебора, используя indexOf().

function subtract3(one, two) {
    var hash = {}, result = [], i, len;
    // fill hash with members of second array for easy lookup
    for (i = 0, len = two.length; i < len; i++) {
        hash[two[i]] = true;
    }

    // cycle through first array and find ones that are not in two
    for (i = 0, len = one.length; i < len; i++) {
        if (!(one[i] in hash)) {
            result.push(one[i]);
        }
    }
    return(result);
}

Вот тест jsperf, сравнивающий эту опцию с парой других опций: http://jsperf.com/array-subtraction

Answer 3

Вы не можете в общем случае решить эту проблему для O (n), если не хотите ограничить свои массивы объектами, которые можно сериализовать в строки

function substract(one, two) {
    var result = []
    for (var i = 0, len = one.length; i < len; i++) {
        var value = one[i]
        if (two.indexOf(value) === -1) {
            result.push(value)
        }
    }
    return result
}

Или если вы хотите использовать итераторы массива

function substract(one, two) {
    return one.filter(function (value) {
        return two.indexOf(value) === -1
    })
}