Обзор: узнайте, что такое Big O популярных методов массивов JS и как они работают.

Обзор:

  1. Введение
  2. Обозначение Big O и работа следующих методов:

.at(), .copyWithin(), .concat(), .entries(), .every(), .fill(), .find(), .filter(), .forEach(), from( ), include(), indexOf(), .map(), .reduce(), … (оператор расширения), shift(), some(), slice(), splice(), sort(), push(), pop(), .toString(), unshift(), values()

Требования — нотация Big O, структуры данных JS.

Уровень — средний

Вступление:

Для всех JS-разработчиков, независимо от того, работаете ли вы профессионально или пытаетесь пройти собеседование по кодированию, которого так боятся, использование встроенных методов массива, таких как .filter(), .reduce(), .map() и т. д., является для нас второй натурой.

Эти методы вводят уровень абстракции, который упрощает чтение кода, а также упрощает и ускоряет его написание.

Но задумывались ли вы когда-нибудь, каковы наихудшие временные и пространственные сложности (большой O) таких методов или как они работают? Они могут выглядеть как простые остроты, но многое скрывается под капотом.

В этой статье мы углубимся в закулисную работу и эффективность этих методов.

Прежде чем мы продолжим…

Для любой операции с массивом не существует гарантии сложности время. Как работают массивы, зависит от базовой структуры данных, которую выбирает движок. Двигатели также могут иметь разные представления и переключаться между ними в зависимости от определенных эвристик. [4]

Операции с массивами почти всегда оптимизированы для работы в соответствии с механизмом выполнения, который он представляет.

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

.at()

Метод at() принимает целочисленное значение и возвращает элемент с этим индексом для положительных целых чисел. Для отрицательных целых чисел обратный отсчет начинается с последнего элемента массива.[6]

Большой О:

Временная сложность — O(1)

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

Сложность пространства — O(1)

Этот метод возвращает один элемент из массива.

.копировать внутри ()

Метод copyWithin() неглубоко копирует часть массива в другое место в том же массиве и возвращает его без изменения его длины.[5]

Большой О:

Временная сложность — O(n)

Этот метод похож на memmove[5] в C++, который используется для сдвига данных в массиве. В худшем случае n-1 элементов будут скопированы в новую позицию в массиве.

Сложность пространства — O(1)

Все изменения внесены, и после изменения возвращается исходный массив.

.concat()

Метод concat() используется для объединения двух или более массивов, что возвращает новый массив с поверхностным копированием.[7]

Большой О:

Временная сложность — O(n)

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

Сложность пространства — O(n)

Результатом этого метода является поверхностная копия обоих массивов. Следовательно, пространственная сложность составляет O(n).

.записи ()

Метод entries() возвращает новый объект Array Iterator, содержащий пары ключ/значение для каждого индекса в массиве. [19]

Большой О:

Временная сложность — O(n)

Все элементы должны быть просканированы линейно, а массив [index, element] должен быть включен в объект итератора.

Сложность пространства — O(n)

Возвращается новый объект итератора, который включает массив для каждого элемента. Один массив имеет постоянное пространство.

.каждый()

Метод every() проверяет, все ли элементы в массиве проходят тест, реализованный предоставленной функцией, и возвращает логическое значение.[20]

Большой О:

Временная сложность — O(n)

В худшем случае все элементы сканируются и сверяются с тестом.

Сложность пространства — O(1)

Метод возвращает одно логическое значение.

.наполнять()

Метод fill() изменяет все элементы массива на заданное статическое значение с начального индекса (по умолчанию 0) на конечный индекс (по умолчанию array.length) и возвращает измененный массив.[21]

Большой О:

Временная сложность — O(n)

Все элементы массива могут быть изменены за линейное время.

Сложность пространства — O(1)

Метод возвращает измененный массив.

.фильтр()

filter()method создает неглубокую копию, включающую все элементы, которые проходят функцию фильтра.[22]

Большой О:

Временная сложность — O(n)

Функция обратного вызова реализована для всех элементов массива линейно, чтобы проверить, проходят ли они проверку соответственно.

Сложность пространства — O(n)

Результаты метода фильтра сохраняются в новом массиве. В худшем случае все элементы могут пройти тест, следовательно, пространство будет равно размеру входного массива.

Примечание. Поверхностная копия — это копия, имеющая те же ссылки, что и источник. Это означает, что любые изменения в новой копии могут быть отражены и в исходном коде. Например: удаление значения 6 из массива «результат» в приведенном выше примере также удалит его из массива «значения».

.находить()

Метод find() возвращает первый элемент предоставленного массива, который удовлетворяет предоставленной функции тестирования.[23]

Большой О:

Временная сложность — O(n)

Функция тестирования может потребовать проверки всех элементов массива за линейное время.

Сложность пространства — O(1)

Из массива возвращается первый прошедший проверку элемент.

.для каждого()

Метод forEach() выполняет предоставленную функцию один раз для каждого элемента массива.[24]

Большой О:

Временная сложность — O(n)

Функция обратного вызова применяется ко всем элементам массива линейно, а изменения вносятся на месте.

Сложность пространства — O(1)

Тот же массив возвращается после того, как все элементы подверглись функции обратного вызова, поэтому дополнительное пространство не используется.

.от()

Метод Array.from() static создает новый, sполностью скопированный экземпляр Array из итерируемого или похожего на массив объекта, такого как строки, массивы, карта или набор.[25]

Большой О:

Временная сложность — O(n)

Функция обратного вызова применяется ко всем элементам массива линейно, а изменения вносятся на месте.

Сложность пространства — O(n)

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

.включает в себя()

Метод includes() проверяет наличие значения или элемента в массиве и возвращает true или false соответственно.[26]

Большой О:

Временная сложность — O(n)

В худшем случае метод должен перебирать и проверять все значения в массиве.

Сложность пространства — O(1)

Метод возвращает логическое значение true или false, для которого не требуется дополнительное пространство.

.индекс чего-либо()

Метод indexOf() возвращает первый индекс, по которому данный элемент может быть найден в массиве, или -1, если он отсутствует.[18]

Большой О:

Временная сложность — O(n)

Метод должен проанализировать все элементы в худшем случае, чтобы определить, существует ли элемент или нет.

Сложность пространства — O(1)

Метод возвращает индекс элемента или -1.

.присоединиться()

Метод join() создает и возвращает новую строку путем объединения всех элементов в массиве (или массивоподобном объекте), разделенных запятыми или заданной строкой-разделителем.[17]

Большой О:

Временная сложность — O(n)

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

Сложность пространства — O(n*m)

Метод возвращает строку, где n — количество узлов, а m — длина наибольшей строки.

.карта()

Метод map() создает новый массив, заполненный результатами вызова предоставленной функции для каждого элемента в вызывающем массиве.

Большой О:

Временная сложность — O(n)

Этот метод использует функцию обратного вызова для индивидуальной и линейной обработки каждого элемента и сохранения в новом массиве.

Сложность пространства — O(n)

Метод создает новый массив с измененными значениями функции обратного вызова исходного массива.

.уменьшать()

Метод reduce() выполняет функцию обратного вызова, известную как «редуктор», для каждого элемента массива, передавая возвращаемое значение из вычисления предыдущего элемента. Конечным результатом выполнения редуктора для всех элементов массива является одно значение.

Большой О:

Временная сложность — O(n)

Этот метод возвращает кумулятивное вычисленное значение, запуская функцию обратного вызова по одному для каждого элемента.

Сложность пространства — O(1)

Метод возвращает одно значение из совокупных вычислений для всех элементов.

… (распространенный синтаксис)

Синтаксис расширения (...) позволяет расширять итерируемый объект, такой как массив или строка, в местах, где ожидается ноль или более аргументов (для вызовов функций) или элементов (для литералов массива).

Большой О:

Временная сложность — O(n)

Для массивов он последовательно вызывает метод .next() итератора массива, пока итератор не будет исчерпан.

Сложность пространства — O(n)

O(n) -›Если используется при создании нового массива, как в приведенном выше примере, синтаксис распространения создаст глубокую копию исходного массива.

O(1) -›Если используется только для итерации по массиву или для передачи аргументов в функцию.

.некоторый()

Метод some() проверяет, проходит ли по крайней мере один элемент в массиве тест (обратный вызов Fn), реализованный предоставленной функцией, если да, то возвращает true, иначе возвращает false.

Большой О:

Временная сложность — O(n)

Этот метод линейно выполняет итерацию по массиву, чтобы определить, соответствует ли тесту хотя бы 1 элемент. В худшем случае приходится проверять все элементы.

Сложность пространства — O(1)

Метод возвращает логическое значение.

.толкать()

Метод push() добавляет один или несколько элементов в конец массива и возвращает новую длину массива.

Большой О:

Временная сложность — O(1)

Этот метод напрямую использует свойство текущей длины для добавления элемента в конец массива и увеличения длины на 1.

Сложность пространства — O(1)

Метод возвращает обновленную длину массива.

.поп()

Метод pop() удаляет элемент last из массива и возвращает этот элемент. Этот метод изменяет длину массива.

Большой О:

Временная сложность — O(1)

Этот метод напрямую использует свойство текущей длины для удаления элемента в конец массива и уменьшения длины на 1.

Сложность пространства — O(1)

Метод возвращает удаленный элемент массива.

.обеспечить регресс()

Метод reverse() переворачивает массив на месте. Первый элемент массива становится последним, а последний элемент массива становится первым.[16]

Большой О:

Временная сложность — O(n)

Замена первого и последнего элементов массива происходит линейно до тех пор, пока массив не станет обратным.

Сложность пространства — O(1)

Метод переворачивает массив на месте, который занимает постоянное пространство.

.сдвиг()

Метод shift() удаляет первый элемент из массива и возвращает этот удаленный элемент.[15]

Временная сложность — O(n)

Чтобы удалить элемент из начала массива, все последующие элементы должны быть соответствующим образом сдвинуты.

Сложность пространства — O(1)

Удаленный элемент возвращается.

.кусочек()

Метод slice() возвращает поверхностную копию части массива в новый объект массива, выбранный из начальногоиндекса в конечныйиндекс. Исходный массив не изменяется.[14]

Большой О:

Временная сложность — O(n)

Запись в неглубокую копию будет линейной, если необходимо получить доступ ко всем элементам.

Сложность пространства — O(n)

Если индексы не заданы, возвращается новая поверхностная копия массива.

.Сортировать()

Метод sort() сортирует элементы массива на месте и возвращает ссылку на тот же массив, теперь отсортированный.[12]

Большой О:

Временная сложность — O(nlogn)

Для больших массивов обычно используется быстрая сортировка. [13]

Сложность пространства — O(logn)

Для быстрой сортировки требуется пространство стека журналов для реализации сортировки.

.сращивание()

Метод splice() изменяет содержимое массива, удаляя или заменяя существующие элементы и/или добавляя новые элементы на место.[11]

Большой О:

Временная сложность — O(n)

В худшем случае необходимо переместить n-1 элементов, если к массиву добавляется один элемент.

Пространственная сложность — O(n + k) ~ O(n)

Если к массиву добавить k элементов, то новая длина будет равна предыдущей длине + k ~ n.

.нанизывать()

Метод toString() возвращает строку, представляющую указанный массив и его элементы.[10]

Большой О:

Временная сложность — O(n)

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

Сложность пространства — O(n*m)

Метод возвращает строку, где n — количество узлов, а m — длина наибольшей строки.

.unshift()

Метод unshift() добавляет один или несколько элементов в начало массива и возвращает новую длину массива.[9]

Большой О:

Временная сложность — O(n)

Чтобы добавить элемент в начало массива, все последующие элементы должны быть соответствующим образом сдвинуты.

Пространственная сложность — O(n + k) ~ O(n)

В массив добавляются k новых элементов вместе с предыдущими n элементами.

.ценности()

Метод values() возвращает новый объект итератора массива, который содержит значения для каждого индекса в массиве.[8]

Большой О:

Временная сложность — O(n)

Все элементы должны добавляться в объект линейно.

Сложность пространства — O(n)

Метод возвращает объект итератора массива, который содержит все элементы массива.

Заключение:

В этой статье мы увидели наихудшие временные и пространственные сложности, а также внутреннюю работу методов массива JS.

До скорого. Ваше здоровье!

Использованная литература:

  1. Веб-документы MDN
  2. Временная сложность Big 0 для методов и примеров Javascript Array.
  3. Большая нотация О
  4. Большой O массивов Javascript.
  5. Метод copyWithin()
  6. Метод at()
  7. Метод concat()
  8. метод значений ()
  9. метод unshift()
  10. метод toString()
  11. метод сращивания()
  12. метод sort()
  13. Большое O в V8. Реализация sort()
  14. метод среза()
  15. метод shift()
  16. обратный () метод
  17. метод соединения()
  18. метод indexOf()
  19. метод записей ()
  20. каждый() метод
  21. метод заполнения()
  22. метод filter()
  23. метод найти()
  24. метод forEach()
  25. метод from()
  26. включает() метод

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn и Discord.