Как узнать, есть ли элемент в массиве?
1,00
р.
Есть массив: ['dog', 'cat', 'hamster', 'bird', 'fish'], нужно вывести в консоль true, если массив содержит dog и false — если такой элемент отсутствует, но насколько я понимаю доступ к элементу в массиве проходит по номеру array[..], каким образом можно проверить наличие того или иного элемента?
Ответ
Маленькая интродукция
Задача поиска элемента в массиве стоит перед всеми достаточно часто и хорошо бы расписать, как это можно сделать.
Ищут обычно в массиве элементы типа 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 <= 7, но это уже давно забытая шутка. Данный метод выполняет поиск элемента строго от меньшего индекса к большему, применяя при сравнении ===. Увы, по свойствам объекта мы так искать не сможем. arr.indexOf(searchElement, fromIndex) принимает два аргумента, первый searchElement - это элемент который ищем, а второй, fromIndex, индекс с которого начнем искать (отрицательный говорит интерпретатору начинать поиск с arr.length + fromIndex индекса). Аккуратней, если вы укажете fromIndex больше длины массива, метод нераздумывая вернёт -1.<br>function contains(arr, elem, from) { return arr.indexOf(elem, from) != -1 }
Array.prototype.lastIndexOf()
Array.prototype.lastIndexOf(searchElement[, fromIndex = arr.length - 1]) - справедливости ради надо рассказать и про него. Работает полностью аналогично Array.prototype.indexOf(), но только полностью наоборот (поиск идет в обратном порядке и fromIndex изначально отсчитывается с конца). Заменил конструкцию ret != -1 на !!~ret ради забавы.
function contains(arr, elem, from) { return !!~arr.lastIndexOf(elem, from) }
Array.prototype.find()
Array.prototype.find(callback[, thisArg]) - модный стильный и молодежный ES6, со всеми вытекающими:
function contains(arr, elem) { return arr.find((i) => 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, [fromIndex=0]) - вот последняя надежда на новые мысли, от второй знаменитейшей библиотеки для работы с коллекциями. То же самое, что _.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 <= length && collection.indexOf(target, 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[index]) : (array[index] !== array[index]))) { 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[index] === 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()).
Number, 1000000 элементов, искомый элемент в начале Number, 1000000 элементов, искомый элемент в середине Number, 1000000 элементов, искомый элемент в конце String, 1000000 элементов, искомый элемент в начале String, 1000000 элементов, искомый элемент в середине String, 1000000 элементов, искомый элемент в конце.
Результаты тестов могут сильно зависеть от версии браузера, да и от самих браузеров, как этого избежать не знаю, но рекомендую протестить на нескольких.
Видно, что в среднем везде выигрывает первый способ из первой части (написанный собственноручно), а второе место обычно делят lоdash и Array.prototype.includes().
Да, прошу заметить, что если взбредёт в голову искать NaN, то это может не получиться почти во всех методах, так как NaN !== NaN.
Ответ
Маленькая интродукция
Задача поиска элемента в массиве стоит перед всеми достаточно часто и хорошо бы расписать, как это можно сделать.
Ищут обычно в массиве элементы типа 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 <= 7, но это уже давно забытая шутка. Данный метод выполняет поиск элемента строго от меньшего индекса к большему, применяя при сравнении ===. Увы, по свойствам объекта мы так искать не сможем. arr.indexOf(searchElement, fromIndex) принимает два аргумента, первый searchElement - это элемент который ищем, а второй, fromIndex, индекс с которого начнем искать (отрицательный говорит интерпретатору начинать поиск с arr.length + fromIndex индекса). Аккуратней, если вы укажете fromIndex больше длины массива, метод нераздумывая вернёт -1.<br>function contains(arr, elem, from) { return arr.indexOf(elem, from) != -1 }
Array.prototype.lastIndexOf()
Array.prototype.lastIndexOf(searchElement[, fromIndex = arr.length - 1]) - справедливости ради надо рассказать и про него. Работает полностью аналогично Array.prototype.indexOf(), но только полностью наоборот (поиск идет в обратном порядке и fromIndex изначально отсчитывается с конца). Заменил конструкцию ret != -1 на !!~ret ради забавы.
function contains(arr, elem, from) { return !!~arr.lastIndexOf(elem, from) }
Array.prototype.find()
Array.prototype.find(callback[, thisArg]) - модный стильный и молодежный ES6, со всеми вытекающими:
function contains(arr, elem) { return arr.find((i) => 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, [fromIndex=0]) - вот последняя надежда на новые мысли, от второй знаменитейшей библиотеки для работы с коллекциями. То же самое, что _.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 <= length && collection.indexOf(target, 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[index]) : (array[index] !== array[index]))) { 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[index] === 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()).
Number, 1000000 элементов, искомый элемент в начале Number, 1000000 элементов, искомый элемент в середине Number, 1000000 элементов, искомый элемент в конце String, 1000000 элементов, искомый элемент в начале String, 1000000 элементов, искомый элемент в середине String, 1000000 элементов, искомый элемент в конце.
Результаты тестов могут сильно зависеть от версии браузера, да и от самих браузеров, как этого избежать не знаю, но рекомендую протестить на нескольких.
Видно, что в среднем везде выигрывает первый способ из первой части (написанный собственноручно), а второе место обычно делят lоdash и Array.prototype.includes().
Да, прошу заметить, что если взбредёт в голову искать NaN, то это может не получиться почти во всех методах, так как NaN !== NaN.
