Часто мы решаем проблемы с javascript, используя нативные методы массива. Однако каковы затраты? Можете ли вы сказать, какова временная сложность использования Array.push() или array.unshift()?
Давайте обсудим это.
Во-первых, зачем это вообще? Ну, это не так, если мы имеем дело с относительно небольшим объемом данных, это не имеет значения. Но по мере того, как мы увеличиваем масштабы, оптимизация становится важной проблемой, которую мы должны принимать во внимание. Использование очень неэффективного метода может стоить нам времени и повлиять на нашу производительность.
Как мы можем измерить эффективность этого времени?
Будет ли достаточно разместить performance.now() до и после строк кода? Это определенно нет.
Вы не можете полагаться на то, что разные машины будут работать одинаково, даже если речь идет об одних и тех же входных данных и вычислениях. На самом деле, даже если это делается на одном компьютере с разницей в пять минут. Это зависит от различных параметров, таких как характеристики компьютера и какие другие программы работают в фоновом режиме, перегружая ЦП в данный момент.
Вот тут-то и появляется временная сложность, и в этой статье мы будем говорить, в частности, о нотации Big O. Обозначение Big O — это средство для сравнения эффективности различных подходов к проблеме. Это не единственный способ проверить, сколько времени требуется алгоритму для работы, но он самый распространенный, и мы будем придерживаться его в этой статье.
Как мы объяснили, нотация Big O — это способ измерения времени, которое потребуется для запуска алгоритма, и места в памяти, которое займет вычисление, которое остается согласованным независимо от устройства пользователя.
Как мы утверждаем временную сложность?
Вместо того, чтобы измерять время с помощью секундомера или устанавливать функцию тайм-аута, мы сосредотачиваемся на подсчете количества шагов или математических операций, необходимых для завершения определенного алгоритма, потому что это всегда будет оставаться фиксированным.
Давайте поговорим об этом расчете, который мы упоминали. Подсчета шагов недостаточно. Количество элементов, которые мы итерируем, может повлиять на количество действий, которые мы предпримем, и, следовательно, на сам подсчет. По мере роста входных данных увеличивается и время выполнения алгоритма.
Постоянная временная сложность O(1) означает, что учитывается только один шаг. Ну, не обязательно один, любое постоянное число может быть 1, 5 или 30. Важно то, что оно остается постоянным независимо от размера входных данных, независимо от того, насколько они велики или малы.
Линейная временная сложность O(n) означает, что нам нужно будет производить вычисления постоянное количество раз для каждого элемента (когда n — количество элементов), чтобы по мере роста входных данных увеличивалось время выполнения. Давайте посмотрим на пример массива зоопарка, заполненного животными, чтобы лучше понять это.
Пример: Добро пожаловать в зоопарк
У меня здесь небольшой зоопарк, множество животных:
let zoo = [🦒, 🦍, 🐘, 🦁, 🦓, 🐼];
Хочу понять сложность выполнения разных действий над массивом.
Доступ или изменение элемента
Доступ к элементу с известным индексом занимает время O(1). Нам нужна только одна операция для доступа к массиву — получить элемент по его индексу. Например, если я хочу получить доступ к панде из моего массива зоопарка, я могу сделать это просто с помощью зоопарка [5], поскольку панда 🐼 является шестым элементом, и я могу обратиться к ней напрямую с ее индексом в массиве.
А как насчет вставки нового элемента в массив?
Вставка и удаление элемента
Допустим, у нас в зоопарке появился новый тигр 🐯, и мы хотим вставить тигра. В javascript мы можем сделать это с помощью метода push, который добавит тигра в массив в качестве последнего элемента, или с помощью метода unshift, который вставит его в качестве первого элемента массива.
zoo.push( 🐯) [🦒, 🦍, 🐘, 🦁, 🦓, 🐼, 🐯]; zoo.unshift( 🐯) [🐯,🦒, 🦍, 🐘, 🦁, 🦓, 🐼];
Можете ли вы угадать сложность метода push и метода unshift? Как вы думаете, это то же самое?
Итак, короткий ответ: они не одинаковы. Сложность Array.push() — O(1), а Array.unshift() — O(n).
Array.push() против Array.unshift()
Вставка элемента в конец массива с помощью метода push() означает, что вы можете перейти непосредственно к последнему элементу по его индексу и добавить свой элемент в качестве нового последнего элемента.
[🦒, 🦍, 🐘, 🦁, 🦓, 🐼, 🐯];
zoo[3] по-прежнему будет разрешаться в льва до и после вставки льва с помощью метода push().
Неважно, 8 животных в зоопарке или 5000 животных. Количество операций, которые необходимо выполнить, не изменится (в большинстве случаев вы можете прочитать больше о распределении памяти в JavaScript здесь). Тигр получит последний индекс текущего массива плюс 1.
То же самое касается Array.pop(), который удалит элемент прямо из последнего индекса массива, и его временная сложность также равна O(1).
array.unshift() — это другая история. Если мы вставим тигра в начало массива в качестве первого элемента, нам теперь нужно выполнить итерацию по массиву и изменить индекс для каждого элемента. 🦒 теперь будет в зоопарке [1] вместо зоопарка [0], поэтому 🦍 переместится из зоопарка [1] в зоопарк [2] и т. д.
array.unshift(🐯) [ 🐯,🦒, 🦍, 🐘, 🦁, 🦓, 🐼];
эта операция повлияет на все элементы массива. Все животные получат новый индекс. Если, как в нашем зоопарке, будет 7 животных, то это ненадолго, а если у нас в зоопарке 5000 животных? или 50000? все элементы сместятся на 1 позицию вправо и их индекс изменится. Таким образом, это операция со сложностью O(n), поскольку ее выполнение займет больше времени по мере увеличения размера массива.
То же самое касается Array.shift(), который удалит элемент прямо из первого индекса массива, и его временная сложность также равна O(n).
Как насчет вставки и удаления элемента из определенного индекса массива?
Допустим, лев 🦁 не уживается с зеброй 🦓 и мы хотим переместить его на новое место между гориллой и слоном. В чем сложность этого? Вы можете подумать, ну, я точно знаю, где он находится — теперь он перемещается в индекс 3, так что zoo[3] = 🦁. Это только один оперант, поэтому его сложность должна быть O(1). Ну, вы что-то упустили — теперь это индекс 3, но слон, который был в позиции zoo[3], больше не может занимать эту ячейку, которую теперь занимает лев. Его позиция обновляется до zoo[4], а затем обновляются позиции всех остальных животных, пока существует массив, поэтому сложность будет O(n).
Заключение
Цель этой статьи состояла в том, чтобы ознакомиться со скрытыми методами обработки массивов Javascript в отношении временной сложности. Это очень большая тема, и мы не коснулись всего, даже близко. Я надеюсь, вам понравилось читать, и я призываю вас больше узнать о сложности времени и пространства и подумать о применении новых знаний при написании на Javascript. Спасибо за чтение!
Дайте мне знать ваши мысли в разделе комментариев.
Дополнительные примечания
Вдохновение на использование массива эмодзи-животных на примере отличной лекции Анджаны Вакил Неизменяемые структуры данных для функционального JS. Анджана замечательный лектор, и я очень рекомендую ее лекцию и курс Frontend Masters, посвященный функциональному программированию.
Спасибо, Элла Шир, Мири Йехезкель и Дана Арад за ваши содержательные замечания.
