[1,2,3,4].includes(3) по-бързо ли е от извършването на цикъл for? Array.indexOf по-добър ли е?

Измерих „времевата сложност“ и „пространствената сложност“ на най-често срещаните методи за намиране дали дадена стойност съществува в масив.

Кодът, използван в този експеримент, може да бъде намерен в това хранилище на Github. Ако искате да пресъздадете моите резултати, следвайте инструкциите във файла README.

В този експеримент бяха тествани следните методи („връзка към функциите“):

Тест за времева сложност

В този тест използвах 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 е най-бавният естествен цикъл с малка разлика
  • когато се използват естествени цикли, сравнението с == изглежда дава същия резултат като ===

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

Кодът, използван за този тест, може да бъде намерен тук.

В този тест използвах JSON масив с 1 милион низа, всеки низ ще има 500 произволно генерирани знака.

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

Използването на паметта беше извлечено чрез process.memoryUsage().

Този тест не е много надежден. Не мога да контролирам събирането на боклук, не знам какво правят импортираните библиотеки с паметта на нашата система, но може да ни подскаже дали някои от методите не са толкова „слаби“ като другите. Ако е така, струва ли си компромисът?

За масив с 1 милион низове с дължина 500 постигнах следните резултати:

Обсъждане на резултатите от теста за космическа сложност

  • за…от използва 2,5% повече памет от останалите.

Заключителни бележки

  • Резултатите не са твърде различни за всеки от методите както по отношение на времето, така и по отношение на пространството. В повечето сценарии от реалния живот трябва да дадете приоритет на четимостта на кода пред производителността.
  • Вероятно ще продължа да използвам include, когато мога.
  • Въпреки че разликата е малка, аз съм изненадан от леката недостатъчна производителност на for…of в сравнение с други естествени цикли. Вероятно ще го използвам по-рядко.
  • Ако основната ви грижа е скоростта, помислете дали да използвате Карта всеки път, когато създавате масив. Те са итерируеми, поддържат реда на вмъкване, използват почти същата памет и проверяват за съществуващи разходи O(1). Те са по-трудни за манипулиране 🥲.
  • Използвах Node.js v18.7.0 в Macbook Pro 2,6 GHz Quad-Core Intel Core i7 от 2016 г.