Поиск значения в массиве js. Задача поиска элемента в массиве стоит перед всеми достаточно часто и хорошо бы расписать, как это можно сделать

Ищут обычно в массиве элементы типа Number , String или Object . Естественно, самый быстрый способ поиска - по элементам типа Number , сравнение числа, даже очень большого, происходит очень быстро, гораздо проще проверить один элемент, чем лексиграфически сравнивать строки, а с объектами вообще другая история. Если мы ищем именно тот объект, который мы добавили в массив, то есть сравниваем ссылки - это так же быстро, как и сравнивать числа, а вот если же надо искать по свойствам объекта, то это может весьма и весьма затянуться. В особо сложных случаях, советую составлять какой-нибудь хэш объекта и строить отдельным массив-карту, в которой уже спокойно искать всё, что надо найти.

Разберем 6 способов сделать это на нативном JS разной новизны и 3 способа с их разбором на популярных фреймворках: jQuery , underscore и lodash .

Часть первая, нативная, в стиле аллегро

Для начала надо пройтись по родным возможностям языка и посмотреть, что можно сделать самим.

Поиск в лоб

Попробуем просто идти по элементам массива, пока мы не встретим то, что нам нужно. Как всегда самое простое решение является в среднем самым быстрым.

Function contains(arr, elem) { for (var i = 0; i < arr.length; i++) { if (arr[i] === elem) { return true; } } return false; }

Работает везде. Сравнивает строго, с помощью === . Легко можно заменить на == , бывает полезно, когда элементы массива разных типов, но может замедлить поиск. Его можно и модифицировать, добавив возможность начинать поиск элемента с конца. Шикарно ищет цифры, строки. Немного расширив, можно добавить возможность поиска элемента по своему условию (это поможет нам искать по свойствам объекта или, например, первый элемент, который больше 100500):

Function contains(arr, pred) { for (var i = 0; i < arr.length; i++) { if (typeof pred == "function" && pred(arr[i], i, arr) || arr[i] === elem) { return true; } } return false; }

Array.prototype.indexOf()

Array.prototype.indexOf(searchElement[, fromIndex = 0]) - старый добрый метод, заставляющий всех мучиться со своей -1 в случае, когда элемента нет.

Function contains(arr, elem) { return arr.indexOf(elem) != -1; }

Поддерживается он везде, кроме IE i === elem) != -1; }

Возвращает элемент или -1 , если ничего не найдено. Ищет с помощью callback(elem, index, arr) , то есть, если эта функция вернет true , то это именно тот самый, искомый элемент. Конечно, эту функцию можно задавать самому, поэтому метод универсален.

Array.prototype.findIndex()

Array.prototype.findIndex(callback[, thisArg]) - полностью аналогичный предыдущему метод, за исключением того, что функция возвращает не элемент, а индекс. Забавы ради сделаю её с возможностью передать свою функцию:

Function contains(arr, pred) { var f = typeof pred == "function" ? pred: (i => i === pred); return arr.findIndex(f) != -1; }

Array.prototype.includes()

Array.prototype.includes(searchElement[, fromIndex]) - а это уже ES7, с ещё пока оочень сырой поддержкой. Наконец-то у нас будет специальный метод, чтобы узнать, есть ли элемент в массиве! Поздравляю!

Arr.includes(elem);

Это всё, что нужно, чтобы найти элемент. Аргументы у этой функции полностью аналогичны Array.prototype.indexOf() . А вот вернет он true в случае успеха и false в обратном. Естественно искать по свойствам объектов нельзя, для этого есть Array.prototype.find() . Должен быть самым быстрым, но... Возможно, что он и станет со временем самым быстрым.

Часть вторая, со вниманием, но чужая и в стиле сонаты

Теперь, наконец, можно поговорить об этой же теме, но в контексте парочки фреймворков! Говорят, что всегда хорошо посмотреть сначала, как делают другие, перед тем, как начнешь делать это сам. Может это откроет нам глаза на что-нибудь интересное!

jQuery

jQuery.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()).

Форма взаимодействия с пользователем будет такой же, как в Листинге 3.15. Изменим функционал (Листинг 3.17). На этот раз будет задан массив целочисленных значений. Необходимо проверить введённое пользователем число с теми значениями, которые записаны в массиве. Если совпадение произошло, необходимо вывести порядковый номер элемента. Если совпадение не произошло, необходимо вывести сообщение об ошибке.

Листинг 3.17. Файл myscript.js - Поиск в массиве

var array = ;

$("#ok").click(function() {

var object = parseInt($("#string").val());

var answer = $.inArray(object, array);

if (answer == "-1") alert("Массив [" +array + "]. Значения "+object+ " нет в массиве");

else alert("Массив [" +array + "]. Значение " + object + " под номером " + answer)

});

});

В Листинге 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 - Поиск в массиве «ключ-значение»

$(document).ready(function() {

var array = {"one":"это значение по ключу one", "two":"это значение по ключу two", "three":"это значение по ключу three"};

$("#ok").click(function() {

var key = $("#key").val();

var value = $("#value").val();

var in_array = false;

var keys = Object.keys(array);

for (var index=0; index>> 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).