Какой самый быстрый способ узнать, существует ли что-то в массиве в Javascript?

Является ли [1,2,3,4].include(3) быстрее, чем выполнение цикла for? Чем Array.indexOf лучше?

Я измерил временную сложность и пространственную сложность наиболее распространенных методов определения существования значения в массиве.

Код, использованный в этом эксперименте, можно найти в этом репозитории Github. Если вы хотите воссоздать мои результаты, следуйте инструкциям в файле README.

В данном эксперименте были проверены следующие методы (ссылка на функции):

existsInArrayForOf, (используя простой for... of)
existsInArrayFor, (для)
existsInArrayWhile, (пока)
existsInArrayForIgnoreDataType, (цикл while, но сравнение производится с == вместо ===)
existsInArrayWhile, (делать... пока)
Массив.прототип.включает()
Массив.прототип.indexOf()
Array.prototype.findIndex()
Массив.прототип.некоторые()
Массив.прототип.найти()
"_.индекс чего-либо"
"_.включает в себя"

Тест на временную сложность

В этом тесте я использовал массив JSON с 1 миллионом строк, каждая строка будет иметь 500 случайно сгенерированных символов.

Я хочу измерить, сколько времени требуется тестируемой функции, чтобы определить, существует ли среднее значение массива (array[array.length/2]).

Мы используем среднее значение массива, чтобы не наказывать методы, которые начинают с поиска последнего элемента массива.

Каждая функция тестируется 25 раз для одного и того же массива. Окончательный результат представляет собой среднее значение измеренного времени (самое короткое и самое длинное время отбрасываются).

Используемый код можно найти здесь.
Время измеряется с помощью performance.now().

Это пример одной команды, которая использовалась для измерения временной сложности indexOf:

node --no-warnings src/bin/measure-time.mjs --file wordCount_1000000_wordSize_500 --function indexOf

Полный список используемых команд вы можете посмотреть здесь.

Для массива с 1 миллионом строк длиной 500 я получил следующие результаты:

Предполагается, что функции одного цвета имеют одинаковую производительность.

Результаты не слишком точны, любое изменение ниже 15% считается неважным.

Два последовательных прогона могут в некоторой степени давать различные результаты.

Например, проверка lodashIndexOf дважды:

> node --no-warnings src/bin/measure-time.mjs --file wordCount_1000000_wordSize_500 --function lodashIndexOf
Result:
lodashIndexOf took on average 12.226 milliseconds. (25x runs)
lodashIndexOf took on average 10.873 milliseconds. (25x runs)

Чтобы уменьшить вес сравнения строк в результатах, я повторил тест, но с 2 миллионами слов длины 20.

Были получены следующие результаты:

Для массива из 2,5 миллионов слов длины 9:

Обсуждение результатов теста на временную сложность

find, some и findIndex постоянно медленнее остальных.
методы lodash почти так же быстры, как и лучшие, и их следует учитывать из-за дополнительной функциональности, которую они предоставляют.
includes и indexOf быстрее всего работают с большими строками.
собственные циклы являются самыми быстрыми при работе с большими массивами
for…of — самый медленный собственный цикл с небольшим отрывом
при использовании собственных циклов сравнение с == дает тот же результат, что и ===

Тест космической сложности

Код, использованный для этого теста, можно найти здесь.

Я хочу измерить, сколько места в куче было выделено после того, как тестируемая функция успешно нашла значение в середине входного массива (array[array.length/2]).

Использование кучи было получено с помощью process.memoryUsage().

Этот тест не очень надежен. Я не могу контролировать сборку мусора, я не знаю, что импортированные библиотеки делают с памятью нашей системы, но это может дать нам подсказку, если некоторые из методов не такие «бережливые», как другие. Если да, то стоит ли компромисс?