Поиск баланса между временем и сложностью памяти – иллюстрированный пример.

1656654850 poisk balansa mezhdu vremenem i slozhnostyu pamyati – illyustrirovannyj primer

от Anmol Uppal

ne6CrMuGNG4SPfSALCfn6GJun8qoaDxSPkAC

Как программистам нам часто приходится искать компромисс между временем и сложностью памяти. Управление одним частенько значит компромисс с другим. Трудно найти правильную сладкую точку между ними.

Проблема становится более актуальной для устройств Android и iOS, имеющих относительно ограниченные ресурсы.

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

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

Структуры данных, часто применяемых для этой проблемы, включают:

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

Понимание Три

Скажем, у нас есть всего четыре слова в словаре, например: «привет», «мир», «он» и «выиграть».

Мы можем визуализировать Trie для этого словаря как:

PPLPKmyFAnoPnxQoc9ob4IuLtZ0iAXUXl8Gn
Образец попытки визуализации

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

TrieNode {    char            character;  // a, b, c, d, ... y, z    boolean         isTerminal; // If this node ends in a valid word    List<TrieNode>  children;   // List of children nodes.}

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

YiPnUv0Hp9U7qLalllTFdVewHDGApfZ6OMdh
Визуализация поискового слова в Trie

Скажем, в приведенном выше Trie (только с четырьмя действительными словами) нам нужно найти, является ли слово «ад» действительным.

Мы начнем с корневого узла и возьмем h, первый символ слова hell, а затем переберем дочерние элементы корневого узла. Если «h» найден, мы повторим потомков «h» и проигнорируем других потомков корневого узла.

Этот процесс продолжается до тех пор, пока мы не добьемся последнего символа поискового слова. Для последнего символа «l» мы также проверяем этот узел isTerminal поле. Это есть false в этом случае действительными словами в этом словаре были только «он», «привет», «победа» и «мир».

Представляем MagicDict

MagicDict использует преимущества специфических для языка свойств, которые Три не заметил:

  • Все символы (az) можно представить как непрерывный диапазон (0–26).

Поскольку все дочерние символы (az) для данного узла могут быть реализованы как непрерывный диапазон целых чисел, мы можем использовать массив Boolean ценности для представления детей

Мы будем использовать a Boolean массив размером 26, со всеми элементами False как начальное значение. Нам также нужен еще один массив из 26 Boolean значение для представления isTerminal так же.

7C63nuYNYz-IBMbJxAqhvTyrP-ENpkqBrPGp
Magic Dict визуализация отношений между родителями и детьми

Этот единственный 2D-массив представляет лишь 1 уровень родительско-начерных отношений. Для английского с 26 символами размер двумерного массива будет: 26 x 52.

Мы можем складывать их друг на друга. Это значит, что дети 1-го уровня становятся родителями во 2-м уровне, дети 2-го уровня становятся родителями в 3-м… и так далее. Это образует цепную структуру и основные элементы MagicDict.

Вставка в MagicDict

Мы создаем стек двумерных слоев, где указано количество слоев, необходимых для создания стека. longest_word_length — 1 .

Для предварительного набора слов: «он», «привет», «победа» и «мир» longest_word_length равно 5. Следовательно, нам нужно зарезервировать размер стека 4.

Скажем, мы хотим вставить «привет» в эту структуру данных. Начинаем с первой пары {«h» и «e»}, и включаем соответствующую isChildren логическое знамя в слое 1.

Затем берем следующую пару {«e», «l»}, аналогично включая соответствующую isChildren логическое знамя на уровне 2. Этот процесс повторяется, пока мы не достигнем конечной пары {«l» и «o»}, где также включаем соответствующий isTerminal логический флаг.

Весь процесс можно визуализировать, как показано на рисунке:

yRWRIGSB3v379RL0esoaPcHvDJhVn-ed53BH

Поиск в MagicDict

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

Последнее магическое прикосновение

Теперь у нас есть структура данных, которая сохраняет п 2D-массивы размером 26 x 52. Каждый 2D-массив сохраняет 1352 логических значения (true/false).

Мы также знаем тот факт, что булевые значения занимают максимум 1 байт памяти (поскольку наименьшей адресной единицей памяти является байт). Потребление 1 байта для хранения a Boolean флаг не является идеальным сценарием.

Что, если бы мы могли найти тип данных, достаточно велик, чтобы удерживать логические флаги 2D-массива как непрерывный битовый шаблон?

Оказывается, их нет! Примитивные типы данных имеют 8-битные, 16-битные, 32-битные, 64-битные, 128-битные представления… но ни один примитивный тип данных не достаточно велик, чтобы сохранять 1352 последовательных бита.

Ближайшим доступным непрерывным битовым шаблоном является 64-битный, который также известен как long в некоторых языках. Мы заменяем строки в нашем двумерном массиве на a long хранение значения 64-бит.

QlewRRyDy1IM0Ed27NRKgs0zctAE2jRPsuiI
Визуализация логического массива как непрерывного битового шаблона

Для словаря с максимальной длиной слова 21 и каждым слоем, занимающим 26 x 8 байт, общий размер структуры данных будет составлять 4160 байт.

Бенчмаркинг

Мы проанализировали 370 000 английских слов из этого хранилища Github и зафиксировали время, необходимое для:

  • Вставка 370 000 слов
  • Удаление 100 000 слов
  • Запрос 100 000 слов (50 000 существующих слов, 50 000 несуществующих слов

Мы также рассмотрели примерное потребление памяти разными структурами данных.

LDFj948LxO02P9vN-GfgN0tQmPH59yePR8qd
Практические тесты для основных структур данных

Заключительные мнения

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *