В этой статье показано, как повысить производительность решений, реализованных с использованием массивов Javascript.

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

Ниже приведены примеры решений O (n ^ 2) (квадратичное время) общих задач с массивами. Мы рассмотрим другие варианты решения с целью повышения производительности.

Пример первый: возврат повторяющихся элементов в массив.

Проблема: для каждого элемента прокрутите массив, чтобы увидеть, есть ли другой подобный ему элемент. Если да, нажмите на другой массив, если нет - нет.

Вышеупомянутое решение - O (n ^ 2). Для каждого первого элемента в массиве мы проводим еще один цикл по массиву, чтобы определить, есть ли у него совпадение. Для некоторых элементов это может быть не медленным, но когда вы увеличиваете количество элементов (например, 100 тыс. Элементов), вы начинаете видеть медлительность.

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

Вышеупомянутое решение - O (n), то есть линейное, поскольку мы перебираем массив один раз. Поиск HashMap - это постоянное время, то есть O (1), поэтому мы не замедляем алгоритм с этим шагом, однако он имеет пространственную сложность O (n).

Примечание. Я использую Javascript. объект в качестве карты для этой статьи - Javascript имеет встроенную структуру данных Карта, которую вы можете просмотреть и использовать в своем решении :)

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

Пример второй: найти пару с такой суммой.

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

Вышеупомянутое решение - O (n ^ 2). Для каждого первого элемента в массиве мы проходим еще один цикл по массиву, чтобы определить, есть ли в нем пара, соответствующая сумме. Для некоторых элементов это может быть не медленно, но когда вы увеличиваете количество элементов (например, 100 тыс. Элементов), вы начинаете замечать медлительность.

Производительность: создайте хеш-карту и переберите массив. Проверьте, есть ли на карте элемент сумма минус. Если да, то у вас есть пара, если нет, добавьте элемент на карту.

Вышеупомянутое решение - O (n), то есть линейное, поскольку мы перебираем массив один раз. Поиск HashMap - это постоянное время, то есть O (1), поэтому мы не замедляем алгоритм с этим шагом, однако он имеет пространственную сложность O (n).

Примечание. Я использую Javascript. объект в качестве карты для этой статьи - Javascript имеет встроенную структуру данных Карта, которую вы можете просмотреть и использовать в своем решении :)

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

Пример третий: найти соответствующий элемент в двух массивах.

Проблема: переберите первый массив. Для каждого элемента выполните цикл по второму массиву для поиска совпадающих элементов.

Вышеупомянутое решение - O (n ^ 2). Для каждого первого элемента в массиве мы проходим еще один цикл по массиву, чтобы определить, есть ли в нем пара, соответствующая сумме. Для некоторых элементов это может быть не медленно, но когда вы увеличиваете количество элементов (например, 100 тыс. Элементов), вы начинаете замечать медлительность.

Производительность: создайте карту со всеми элементами массива. Найдите второй массив и посмотрите, сможете ли вы найти его на карте.

Как видите, все вышеперечисленные более производительные решения используют структуру данных, называемую хеш-картой / хеш-таблицей. Это вводит пространственную сложность O (n), но улучшает общие временные характеристики. Это объясняет / показывает, что компромиссы действительно случаются при стремлении улучшить алгоритмы.

Примечание. Я использую Javascript. объект в качестве карты для этой статьи - Javascript имеет встроенную структуру данных Карта, которую вы можете просмотреть и использовать в своем решении :)

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