[1,2,3,4].includes(3) по-бързо ли е от извършването на цикъл for? Array.indexOf по-добър ли е?
Измерих „времевата сложност“ и „пространствената сложност“ на най-често срещаните методи за намиране дали дадена стойност съществува в масив.
Кодът, използван в този експеримент, може да бъде намерен в това хранилище на Github. Ако искате да пресъздадете моите резултати, следвайте инструкциите във файла README.
В този експеримент бяха тествани следните методи („връзка към функциите“):
- existsInArrayForOf, (използвайки просто за... от)
- съществува ВМасивЗа, (за)
- existsInArrayWhile, (докато)
- existsInArrayForIgnoreDataType, (while цикъл, но сравнението се прави с == вместо ===)
- existsInArrayWhile, (направи ... докато)
- Array.prototype.includes()
- Array.prototype.indexOf()
- Array.prototype.findIndex()
- Array.prototype.some()
- Array.prototype.find()
- "_.индекс на"
- "_.включва"
Тест за времева сложност
В този тест използвах 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 г.