Полезные структуры данных

Сегодня мы поговорим про структуры данных и алгоритмы, которые действительно могут пригодиться в работе программиста. Но о которых вы скорее всего не слышали.

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

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

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

Для разогрева начнем с простых вещей, а в конце поговорим про вероятностные структуры данных.

Давайте начнем с деревьев.

Я не думаю, что удивлю кого-либо сказав, что программисты работают с деревьями почти каждый день. Тот самый JSON, который мы перекладываем с одного места на другое – древоподобная структура данных. Что такое дерево? Дерево – это граф без циклов. Соответственно полезно знать алгоритмы обхода графов. Поиск в ширину и поиск в глубину. 

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

Где еще могут пригодиться деревья?

Можно вспомнить префиксное дерево для автодополнения или проверки правописания. Если же у вас в распоряжении мало памяти, то можно посмотреть на тернарное дерево, которое подходит для тех же задач, работает медленнее, но требует меньше памяти для самого дерева.

Следующая структура – это двунаправленный список или двусвязный список. Doubly linked list.

Несмотря на то, что это тоже одна из базовых структур данных у нее есть одно интересное применение, которое может пригодиться даже форнтенщикам. С помощью двусвязного списка можно легко реализовать сохранение истории операций с возможностью отмены или повтора действия. Те самые undo-redo. В реакте для этого вам просто нужно сохранять предыдущее состояние системы как узел списка и потом кнопками отмена и повтор – ходить по этому списку. Если же вы откатываетесь на несколько действий назад и начинаете делать новые изменения, то они перетрут прошлые действия и у вас будет новая история изменений.

Так же с помощью двунаправленного списка принято делать Least recent used cache и Most recent used cache – кеш с ограниченным выделением памяти. Может программисты уже начнут ограничивать выделение памяти наконец? Я себе комп купил с 32 гигабайтами, хватит ли этого, чтобы открыть 5 вкладок в хроме я даже не знаю. Если вам нужен кеш – пожалуйста подумайте насколько большим имеет смысл его делать.

Следующая структура в списке – кольцевой буфер или Circular Buffer.

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

С помощью такого буфера можно, например, делать лог ограниченного размера. Представьте, что ваша программа может неожиданно свалиться и вы хотите, чтобы у вас были хоть какие-то логи для последующей отладки? Понятное дело, что вы заботитесь о дисковой памяти и об оперативной памяти, поэтому вы ограничиваете размер буфера используя кольцо. 

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

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

Следующая группа – это вероятностные структуры данных или probabilistic data structure.

Про вероятностные структуры можно прямо отдельное видео снимать. Я постараюсь кратко. Самое главное их свойство – это неточность. То есть, в отличие от детерминированных структур данных, вы получаете приблизительный ответ. Что значит приблизительный ответ будет понятно из примеров. Это конечно недостаток. Однако этот недостаток с лихвой покрывается компактностью, скоростью исполнения и масштабированием.

Первая структура это фильтр Блума.

Фильтр Блума позволяет определять присутствует элемент в выборке или нет. Так как это вероятностная структура данных, то точный ответ фильтр дать не может. Поэтому ответ будет либо “элемент точно отсутствует в выборке”, либо “элемент, возможно, присутствует в выборке”.

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

Понятное дело, feature флагов очень много и все их хранить и регулярно синхронизировать эту базу будет затратно. Поэтому если есть возможность заранее определить, что флаг для клиента выключен это очень большое дело! Таким образом можно избежать необходимости делать сетевой запрос к сервису флагов.

Как я уже сказал, фильтр Блума занимает очень мало места. По сути это битовый массив и несколько хеш функций перед ним. Размер массива можно регулировать. Чем меньше массив вы сделаете, тем чаще фильтр будет давать неточный ответ. Тот самый “элемент, возможно, присутствует в выборке”. У классического фильтра Блума есть один недостаток. Он не позволяет удалять элементы из выборки. Если вам необходимо делать все то же самое, но еще и удалять элементы – почитайте про Cuckoo filter.

Еще одна структура, о которой я бы хотел рассказать – это HyperLogLog

HyperLogLog это одна из структур, которая помогает считать мощность множества или cardinality. Представьте, что у вас есть множество из миллиардов событий. Вам нужно быстро посчитать сколько типов этих событий у вас есть. События же могут повторяться. Конечно можно сделать хеш и просто все пересчитать. Но, во-первых, это будет дольше, во-вторых, займет на порядки больше места. 

Если у вас база данных с парой миллиардов строк, то HyperLogLog позволит посчитать мощность множества почти в 1000 раз быстрее, чем SQL Count distinct. 

Я нарочно не делал полный разбор структур и алгоритмов. Это заняло бы слишком много времени и легко гуглится. Тот же HyperLogLog вообще одна из структур данных Рэдиса. Моя цель – показать, что алгоритмы и структуры данных не так уж и бесполезны. И что их можно и нужно применять в работе. 

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