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

Что такое дерево сегментов

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

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

Когда использовать деревья сегментов

Деревья сегментов полезны, когда вы часто работаете с диапазонами числовых данных. Наиболее распространенные варианты использования деревьев сегментов:

  1. Просуммируйте все элементы в диапазоне.
  2. Найдите минимальное или максимальное значение элементов в диапазоне.
  3. Обновить все элементы в диапазоне.

Это не означает, что использование деревьев сегментов ограничивается работой с числами. Вы можете работать с деревьями сегментов, например, чтобы найти все интервалы (или диапазоны), которые соответствуют определенным критериям. Классическим примером этого является Проблема скобок.

Использование деревьев сегментов в приложении Frontend

ПРИМЕЧАНИЕ. Различные движки JavaScript реализуют спецификацию JavaScript. иначе. Таким образом, в зависимости от среды результаты производительности могут отличаться.

Самый распространенный способ представления коллекций в JavaScript - это массивы. Чтобы выяснить, имеет ли смысл использовать дерево сегментов в приложении Frontend, давайте сопоставим использование дерева сегментов и массива для одной и той же задачи. Вот критерии, которые мы будем использовать для их оценки:

  • Производительность (время выполнения и время загрузки)
  • Простота использования и читаемость

Настраивать

  • Я быстро написал сетку ставок на Vue, используя vue cli. Вот как это выглядит:

  • Мне не удалось найти в JavaScript реализацию дерева сегментов, которая мне понравилась. Итак, с небольшой помощью с сайта Книга алгоритмов я свернул сам.
  • Я использовал faker для создания набора из 10 000 ставок.

Код

Вот базовый код сетки. Обратите внимание, что он не использует какую-либо конкретную структуру данных коллекции. Подробности реализации для дерева сегментов и массива приведены ниже.

Вот код на основе массива:

Вот код на основе дерева сегментов:

Представление

Я проверил три вещи на производительность:

  1. Загрузка элементов данных в структуру данных.
  2. Поиск в структуре данных минимального значения в диапазоне.
  3. Суммирование значений в диапазоне.

Все тесты проводились с использованием Chrome 65.x. Диапазон данных, используемых для каждого запроса, составлял 1–3000.

Загрузка элементов данных
Деревья сегментов инициализируются за время O (n * log (n)). Чтобы дать вам практическое представление об этом, нужно в среднем 2,6 секунды, чтобы добавить 10 000 элементов в дерево сегментов.

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

Запрос о минимальном диапазоне:
Этот запрос находит наименьшее значение в диапазоне.

Запрос на основе дерева сегментов был невероятно быстрее, чем запрос на основе массива. Это было на 2250% быстрее.

Сумма диапазона:
Этот запрос суммирует все значения в диапазоне.

И снова дерево сегментов было потрясающим. Это было на 2140% быстрее, чем метод Array.

Примечание. В приведенном выше тесте запрос начальной суммы занял около 1 секунды. Все последующие запросы суммирования занимали примерно 0,25 секунды - даже при изменении диапазона запроса.

Легкость использования

Использовать дерево сегментов для этой задачи было проще, чем использовать массив. Не было необходимости создавать filter или reduce методы, чтобы получить желаемый результат. В дереве сегментов были встроены все методы запросов.

Приведенный ниже фрагмент кода контрастирует с кодом, необходимым для дерева сегментов и массива:

Заключение

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

Использование дерева сегментов вместо массива может привести к некоторым потерям производительности, например:

  • Инициализация дерева сегментов. Это единовременная стоимость для каждого Дерева Сегментов. По этой причине рекомендуется отложить инициализацию дерева сегментов до загрузки страницы.