Оператор для проверки членства в коллекции в Javascript

Question

как я мог эффективно выполнять проверки членства в коллекции в Javascript? У меня есть потенциально большой массив строк, и мне нужно проверить, является ли данная строка членом массива.

Изначально я думал, что оператор in может помочь, но после прочтения документов в Mozilla Developer Network я обнаружил, что его назначение отличается . В Javascript он проверяет, находится ли указанное свойство в указанном объекте.

По причинам, связанным с производительностью, я бы предпочел использовать встроенную js, но если такой функции не существует, я, вероятно, в конце концов выполню одно из следующих действий:

1. использовать массив для создания объекта, содержащего элементы массива в качестве ключей, а затем использовать in
2. перебирает элементы массива и выполняет сравнение элементов по элементам
3. реализовать бинарный поиск

Есть мнение? Или лучшие идеи?

Спасибо

Answer 1

Достаточно ли хорошего исполнения?

var inArray = function(array, value) {
    var i = array.length;

    while (i--) {
        if (array[i] == value) {
            return true;
        }
    }

    return false;

}

jsFiddle .

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

Answer 2

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

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

Пример внедрения HashSet можно найти здесь .

Answer 3

Я бы порекомендовал вам использовать как объект, так и массив.

Таким образом, вы можете очень быстро выполнить тесты членства на объекте и использовать массив, когда вам нужно, чтобы ваши элементы оставались отсортированными.

Это единственный способ эмулировать тип поведения "отсортированный словарь".

Answer 4

Вы должны использовать массивы? Вы можете просто использовать объект с самого начала? Если вам нужно перебрать элементы, вы можете использовать цикл for для объекта.

Двоичный поиск работает, только если он отсортирован. Это может быть хорошей идеей, если вы знаете, что собираетесь многократно выполнять поиск в массиве. В противном случае вариант 2 будет быстрее.