Быстрый способ найти строку в массиве

Ответ 1

Прежде всего, есть некоторая фундаментальная путаница в том, какие структуры данных доступны в JavaScript.

JavaScript не имеет массивов

По сути, JavaScript имеет только хэш-таблицы. Стандартная функция Array создает хэш-таблицы (я буду называть эти целые хэш-таблицы или int-hash-tables), где ключи являются целыми числами в дополнение к строковым клавишам. Они работают аналогично массивам, но они различаются определенным образом. Есть минусы и профи. Например, удаление элемента из int-hash-table является операцией O (1), а удаление элемента из массива - это операция O (n) (потому что вам нужно скопировать остальные элементы в новый массив). Вот почему функция Array.prototype.splice в JavaScript очень быстро. Недостатком является сложность реализации.

Итак, когда вы говорите Array в контексте JavaScript, это понимается как int-hash-table и вся связанная с ним асимптотическая сложность. Это означает, что если вы хотите найти строковое значение внутри таблицы int-hash, то это будет операция O (n). Для этого есть стандартная функция: Array.prototype.indexOf. Однако, если вы хотите найти ключ, то есть две функции: in и Object.prototype.hasOwnProperty.

Несколько противоречиво:

[1, 2, 3].hasOwnProperty(0); // true
0 in [1, 2, 3]; // true

Различие между двумя требует дальнейшего объяснения. Это связано с тем, что все объекты в JavaScript являются объектами и, следовательно, имеют некоторые объекты-y. Один из таких функций имеет prototype, связь между объектом и его прототипом. Это иерархическая структура хеш-таблиц, каждая из которых содержит свойства объектов.

• in просматривает немедленную хеш-таблицу объекта, а затем рекурсивно ищет хэш-таблицы прототипов этих объектов.

• В то время как Object.prototype.hasOwnProperty только просматривает непосредственную таблицу хэша. Вы можете подумать, что это должно быть быстрее, но подождите, пока вы не перейдете к выводам.

Благодаря динамическому характеру JavaScript все вызовы функций являются динамическими, и среда должна очень заботиться о том, чтобы обеспечить выполнение отказобезопасного кода. Это означает, что вызовы функций JavaScript очень дороги. Итак, переход через Object.prototype.hasOwnProperty может быть намного дороже, чем через in, хотя теоретически это должно быть наоборот. Однако, учитывая достаточно высокое дерево наследования и достаточное количество унаследованных свойств, в конечном итоге, Object.prototype.hasOwnProperty возьмет верх.

Некоторые примеры для лучшей интуиции:

>>> var array = [1, 2, 3];
undefined
>>> 3 in array;
false
>>> array.hasOwnProperty(3);
false
>>> 3 in array;
false
>>> array.__proto__ = [1, 2, 3, 4];
[1, 2, 3, 4]
>>> 3 in array;
true
>>> array.hasOwnProperty(3);
false

TL; DR

• Если вы хотите быстрый поиск ключей для объектов с короткой цепочкой наследования прототипа, используйте in.

• Если вы хотите то же самое, но для объектов с обширной цепочкой наследования используйте Object.prototype.hasOnwProperty

• Если вы хотите быстрый поиск по параметрам, используйте Array.prototype.indexOf для Array.

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

Ответ 2

Из @nnnnnn в комментариях:

Преобразуйте массив в объект, что-то вроде этого:

object = {}
array.forEach(function(string) { // Not cross-browser compatible, it just an example
  object[string] = 1;
}

Затем выполните поиск следующим образом:

if (string in object) {