Trie (обычно произносится как «попытка») - это древовидная структура данных, оптимизированная для определенного типа поиска. Вы используете Trie, когда хотите взять частичное значение и вернуть набор возможных полных значений. Классическим примером этого является автозаполнение.

На изображении выше показано, как структурировано Trie, что намекает на его работу. Вы можете думать о Trie как о наборе связанных значений. Общее у ценностей - это их префикс.

По мере поиска более конкретного префикса вы получаете более конкретные возвращаемые значения. Используя Trie, показанный на картинке выше, поиск совпадений с префиксом «b» вернет 6 значений: быть, медведь, колокол, ставка, бык, покупка.

Поиск совпадений с префиксом «быть» вернет 2 значения: медведь, колокольчик.

Когда использовать попытки

Trie можно использовать всякий раз, когда вы хотите сопоставить префиксы с возможными полными значениями. Так ТРИ получил свое забавное название. Слово «Trie» является инфиксом слова «re trie val».

Попытки обычно используются для реализации таких вещей, как:

  • Автозаполнение / опережающий ввод
  • Поиск
  • Проверка орфографии
  • Сортировать

Вы не ограничены префиксом совпадающих слов. В попытках можно хранить:

  • IP-адреса,
  • Телефонные номера,
  • Объекты (вы можете искать свойства объекта),
  • и более…

Стоит ли использовать попытки в приложении Frontend?

Есть практические факторы, которые следует учитывать перед использованием структуры данных, которая не входит в состав JavaScript, например:

  • Эта структура дает мне прирост производительности? Стоит ли прирост производительности того?
  • Эта структура проще в использовании - или, по крайней мере, не сложнее?
  • Придает ли эта структура моим данным больше семантики? Делает ли мой код более понятным?
  • Насколько сильно эта структура повлияет на размер моей сборки? Стоит ли этого увеличения размера сборки?

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

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

Вот критерии, которые мы будем использовать для сравнения попыток и массивов:

  • Производительность (время выполнения и время загрузки)
  • Простота использования и читаемость
  • Размер сборки (массивы не добавляют лишнего кода. Мы проанализируем Trie.)

Настраивать

  • Я написал быстрое автозаполнение в React, используя create-react-app. Вот как это выглядит:

  • В качестве реализации Trie я использовал trie-search Джоша Юнга.
  • Я использовал faker для создания набора из 10 000 имен. Меня не волновало, уникальны ли имена.

Код

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

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

Вот код на основе TrieSearch:

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

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

  1. Загрузка элементов данных в структуру данных.
  2. Поиск элементов в структуре данных.

Все тесты проводились с использованием Chrome 65.x.

Загрузка элементов данных
При использовании Trie время инициализации будет больше, чем при использовании массива. Пытается инициализировать за время O (n * m). Чтобы дать вам практическое представление об этом, нужно в среднем 90 миллисекунд, чтобы добавить 10 000 элементов в Trie в тестовом коде. Это единовременная оплата. Инициализацию Trie можно (т.е. следует) отложить до загрузки страницы.

Чаще всего вы инициализируете Trie из массива. Если вам нужно добавить больше данных, вы можете добавлять элементы в Trie вручную.

Пытается повысить ценность, когда поиск - одна из основных задач приложения. Из-за затрат на инициализацию использование Trie может не подходить для вашего приложения, если ваши пользователи мало ищут.

Время выполнения
В каждом тесте я вводил «Кат» в поле автозаполнения и измерял, сколько времени занимает поиск.

TrieSearch превзошел Array.filter. Это было на 50% быстрее.

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

Как показывают приведенные выше примеры кода, использование TrieSearch не сложнее, чем использование массива. Однако следует помнить о различиях:

Подробнее об использовании TrieSearch см. В документации.

Размер

Размер TrieSearch - 7,4 КБ без миниатюр. Имеет 13 зависимостей. Общий размер производственной сборки составляет ~ 10 КБ. Вам решать, окажет ли это существенное влияние на ваше приложение.

Резюме

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

Использование Trie над массивом требует некоторых затрат производительности, например:

  • Инициализация Trie. (По этой причине рекомендуется отложить инициализацию Trie до тех пор, пока страница не загрузится).
  • Большой размер пачки.