Прежде всего, существует некоторая фундаментальная путаница в том, какие структуры данных доступны в 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 может быть намного дороже, чем проходить, хотя теоретически это должно быть наоборот. Однако, учитывая достаточно высокое дерево наследования и достаточное количество унаследованных свойств, в конечном итоге, 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Если вам нужен быстрый поиск ключей для объектов с короткой цепочкой наследования прототипов, используйте.
Если вы хотите то же самое, но для объектов с обширной цепочкой наследования, используйте Object.prototype.hasOnwProperty
Если вам нужен быстрый поиск, используйте Array.prototype.indexOf для Array .
В хэш-таблицах нет встроенной функции для поиска значений. Вы можете, конечно, сворачивать свои собственные, но есть много библиотек, которые уже предоставляют их. Например, Underscore предоставляет один (он называет его indexOf).
Форма взаимодействия с пользователем будет такой же, как в Листинге 3.15. Изменим функционал (Листинг 3.17). На этот раз будет задан массив целочисленных значений. Необходимо проверить введённое пользователем число с теми значениями, которые записаны в массиве. Если совпадение произошло, необходимо вывести порядковый номер элемента. Если совпадение не произошло, необходимо вывести сообщение об ошибке.
Листинг 3.17. Файл myscript.js - Поиск в массиве
В Листинге 3.17 поиск осуществляется по массиву array. По нажатию на кнопку с id=ok , в переменную object записывается значение, введённое в текстовое поле с id=string , преобразованное к типу int (целое число). Затем осуществляется проверка вхождения числа в массив. Для этого используется функция $.inArray() . Результат выполнения функции может быть либо «-1» - введённого значения в массиве нет, либо порядковый номер найденного элемента (напомним, что нумерация в массиве начинается с 0). Теперь достаточно проверить равен ли результат поиска «-1». Если да - вывести сообщение об ошибке. Если нет - вывести порядковый номер. В обоих случаях формируется строка для большей наглядности.
Конечно, пример (Листинг 3.17) далёк от совершенства. Пользователь может вводить в текстовое поле не только цифры, но и строки. Для анализа только числовых значений можно запретить ввод символов или осуществить проверку введённого значения есть ли в нём символы. Первый вариант уже оговаривался в этой главе. На наш взгляд он является более уместным, если вводимые значения всегда должны быть целыми числами.
Результат выполнения JS-кода похож на Рис. 3.7.
Рис. 3.7. Поиск в массиве
Усложним задачу. Пусть дан массив «ключ-значение». Пользователь может ввести в текстовые поля формы ключ и значение (Листинг 3.18). Необходимо проверить существует ли введённый ключ в массиве. Также необходимо сверить введённое пользователем значение с уже заданным (Листинг 3.19).
Листинг 3.18. Файл 1.html - Форма для ввода значений
Листинг 3.19. Файл myscript.js - Поиск в массиве «ключ-значение»
Array.prototype.includes(searchElement[, fromIndex]) - а это уже ES7, с ещё пока оочень сырой поддержкой. Наконец-то у нас будет специальный метод, чтобы узнать, есть ли элемент в массиве! Поздравляю!
Arr.includes(elem);
Это всё, что нужно, чтобы найти элемент. Аргументы у этой функции полностью аналогичны Array.prototype.indexOf() . А вот вернет он true в случае успеха и false в обратном. Естественно искать по свойствам объектов нельзя, для этого есть Array.prototype.find() . Должен быть самым быстрым, но... Возможно, что он и станет со временем самым быстрым.
Часть вторая, со вниманием, но чужая и в стиле сонатыТеперь, наконец, можно поговорить об этой же теме, но в контексте парочки фреймворков! Говорят, что всегда хорошо посмотреть сначала, как делают другие, перед тем, как начнешь делать это сам. Может это откроет нам глаза на что-нибудь интересное!
jQueryjQuery.inArray(value, array [, fromIndex ]) - между прочим весьма быстрый метод, по тестам.
Использует внутри строгое равенство === и возвращает -1 , если ничего не нашел, а если все таки нашёл, то вернет его индекс. Для удобства и одинаковости обернем её в функцию:
Function contains(arr, elem) { return jQuery.inArray(elem, arr) != -1; }
А теперь поговорим, как она работает. Вот, что она представляет из себя в версии 2.1.3:
InArray: function(elem, arr, i) { return arr == null ? -1: indexOf.call(arr, elem, i); }
Где indexOf это вот это:
// Use a stripped-down indexOf as it"s faster than native // http://jsperf.com/thor-indexof-vs-for/5 indexOf = function(list, elem) { var i = 0, len = list.length; for (; i < len; i++) { if (list[i] === elem) { return i; } } return -1; }
Забавный комментарий говорит, что так быстрее, чем родной Array.prototype.indexOf() (могу предположить, что из-за отсутствия всех проверок) и предлагает посмотреть тесты производительности.
По сути - это самый первый способ из первой части.
Underscore_.contains(list, value) - вот такой метод предлагает нам популярная библиотека для работы с коллекциями. То же самое, что и _.include(list, value) .
Использует === для сравнения. Вернёт true , если в list содержится элемент, который мы ищем. Если list является массивом, будет вызван метод indexOf.
Contains = _.include = function(obj, target) { if (obj == null) return false; if (nativeIndexOf && obj.indexOf === nativeIndexOf) return obj.indexOf(target) != -1; return any(obj, function(value) { return value === target; }); };
Где nativeIndexOf - штука, которая говорит, что Array.prototype.indexOf() существует, а obj.indexOf === nativeIndexOf говорит, что list - массив. Теперь понятно, почему этот метод медленнее, чем jQuery.inArray() , просто обертка над Array.prototype.indexOf() . Ничего интересного.
Lodash_.includes(collection, target, ) - вот последняя надежда на новые мысли, от второй знаменитейшей библиотеки для работы с коллекциями. То же самое, что _.contains() и _.include() .
Возвращает true , если содержит и false если нет. fromIndex индекс элемента, с которого начинаем поиск.
Function includes(collection, target, fromIndex, guard) { var length = collection ? getLength(collection) : 0; if (!isLength(length)) { collection = values(collection); length = collection.length; } if (typeof fromIndex != "number" || (guard && isIterateeCall(target, fromIndex, guard))) { fromIndex = 0; } else { fromIndex = fromIndex < 0 ? nativeMax(length + fromIndex, 0) : (fromIndex || 0); } return (typeof collection == "string" || !isArray(collection) && isString(collection)) ? (fromIndex -1) : (!!length && getIndexOf(collection, target, fromIndex) > -1); }
guard - служебный аргумент. Сначала находится длина коллекции, выбирается fromIndex , а потом... нет, не Array.prototype.indexOf() ! Для поиска в строке используется String.prototype.indexOf() , а мы идем дальше в _.getIndexOf() и в результате попадём в ло-дашскую имплементацию indexOf() :
Function indexOf(array, value, fromIndex) { var length = array ? array.length: 0; if (!length) { return -1; } if (typeof fromIndex == "number") { fromIndex = fromIndex < 0 ? nativeMax(length + fromIndex, 0) : fromIndex; } else if (fromIndex) { var index = binaryIndex(array, value); if (index < length && (value === value ? (value === array) : (array !== array))) { return index; } return -1; } return baseIndexOf(array, value, fromIndex || 0); }
Она интересна тем, что fromIndex может принимать значения как Number , так и Boolean и если это всё таки значение булевого типа и оно равно true , то функция будет использовать бинарный поиск по массиву! Прикольно. Иначе же выполнится indexOf() попроще:
Function baseIndexOf(array, value, fromIndex) { if (value !== value) { return indexOfNaN(array, fromIndex); } var index = fromIndex - 1, length = array.length; while (++index < length) { if (array === value) { return index; } } return -1; }
Интересный ход для случая, когда мы ищем NaN (напомню, что из-за досадной ошибки он не равен сам себе). Выполнится indexOfNaN() , и действительно ни один из всех способов описанных ранее не смог бы найти NaN , кроме тех, естественно, где мы могли сами указать функцию для отбора элементов.
Можно предложить просто обернуть _.indexOf() для поиска элемента:
Function contains(arr, elem, fromIndex) { return _.indexOf(arr, elem, fromIndex) != -1; }
Где fromIndex будет либо индексом откуда начинаем искать, либо true , если мы знаем, что arr отсортирован.
Заключение, хотя и в стиле интермеццоИ да, все эти варианты имеют смысл, только если момент с поиском данных част в вашем алгоритме или поиск происходит на очень больших данных. Вот приведу ниже несколько тестов на поиск элементов типа Number и String в массивах длинной 1000000 (миллион) элементов для трех случаев, когда элемент находится вначале массива, в середине (можно считать за среднюю по палете ситуацию) и в конце (можно считать за время поиска отсутствующего элемента, кроме метода с Array.prototype.lastIndexOf()).
