Объектов javascript js id - Быстрый способ найти строку в массиве. Задача поиска элемента в массиве стоит перед всеми достаточно часто и хорошо бы расписать, как это можно сделать

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

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

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

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

Ищут обычно в массиве элементы типа 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(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(callback[, thisArg]) - полностью аналогичный предыдущему метод, за исключением того, что функция возвращает не элемент, а индекс. Забавы ради сделаю её с возможностью передать свою функцию:

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

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

Arr.includes(elem);

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

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

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() (могу предположить, что из-за отсутствия всех проверок) и предлагает посмотреть тесты производительности.

По сути - это самый первый способ из первой части.

_.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() . Ничего интересного.

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