От чего зависит выбор структуры данных

Массив

Когда вам нужен один объект, вы создаёте один объект. Когда нужно несколько объектов, тогда есть несколько вариантов на выбор. Я видел, как многие новички в коде пишут что-то типа такого:

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

Будет создан буфер из 5 элементов, вот такой:

Заметьте, что индекс массива начинается с нуля. Если в массиве пять элементов, то они будут иметь индексы от нуля до четырёх.

Недостатки простого массива

Если вам нужно неизменное количество объектов, то массив вполне подходит. Но, допустим, вам нужно добавить в массив ещё один элемент. В простом массиве этого сделать невозможно. Допустим, вам нужно удалить элемент из массива. В простом массиве это так же невозможно. Вы привязаны к одному количеству элементов. Нам нужен массив, размер которого можно менять. Поэтому нам лучше выбрать…

Динамический массив

Динамический массив — это массив, который может менять свой размер. Основные языки программирования в своих стандартных библиотеках поддерживают динамические массивы. В C++ это vector. В Java это ArrayList. В C# это List. Все они являются динамическими массивами. В своей сути динамический массив — это простой массив, однако имеющий ещё два дополнительных блока данных. В них хранятся действительный размер простого массива и объём данных, который может на самом деле храниться в простом массиве. Динамический массив может выглядеть примерно так:

Элемент internalArray указывает на динамически размещаемый буфер. Действительный массив буфера хранится в maxCapacity. Количество использовуемых элементов задаётся currentLength.

Добавление к динамическому массиву

При добавлении объекта к динамическому массиву происходит несколько действий. Класс массива проверяет, достаточно ли в нём места. Если currentLength < maxCapacity, то в массиве есть место для добавления. Если места недостаточно, то размещается больший внутренний массив, и всё копируется в новый внутренний массив. Значение maxCapacity увеличивается до нового расширенного значения. Если места достаточно, то добавляется новый элемент. Каждый элемент после точки вставки должен быть скопирован на соседнее место во внутреннем массиве, и после завершения копирования пустота заполняется новым объектом, а значение currentLength увеличивается на единицу.

Поскольку необходимо перемещать каждый объект после точки вставки, то наилучшим случаем будет добавление элемента к концу. При этом нужно перемещать ноль элементов (однако внутренний массив всё равно требует расширения). Динамический массив лучше всего работает при добавлении элемента в конец, а не в середину.

Удаление из динамического массива

Удаление объектов требует меньше работы, чем добавление. Во-первых, уничтожается сам объект. Во-вторых, каждый объект после этой точки сдвигается на один элемент. Наконец, currentLength уменьшается на единицу.

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

Недостатки динамических массивов

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

Связные списки

Массив — это непрерывный блок памяти, и каждый элемент его расположен после другого. Связанный список — это цепочка объектов. Связанные списки тоже присутствуют в стандартных библиотеках основных языков программирования. В C++ они называются list. В Java и C# это LinkedList. Связанный список состоит из серии узлов. Каждый узел выглядит примерно так:

Он создаёт структуру такого типа:

Каждый узел соединяется со следующим.

Добавление к связанному списку

Добавление объекта к связанному списку начинается с создания нового узла. Данные копируются внутрь узла. Затем находится точка вставки. Указатель нового узла на следующий объект изменяется так, чтобы указывать на следующий за ним узел. Наконец, узел перед новым узлом изменяет свой указатель, чтобы указывать на новый узел.

Удаление из связанного списка

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

Преимущества связанного списка

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

Недостатки связанного списка

Вспомните, что динамический массив — это непрерывный блок памяти.

Если вам нужно получить пятисотый элемент массива, то достаточно просто посмотреть на 500 «мест» вперёд. В связанном списке память соединена в цепочку. Если вам нужно найти пятисотый элемент, то придётся начинать с начала цепочки и следовать по её указателю к следующему элементу, потом к следующему, и так далее, повторяя пятьсот раз.

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

Ещё один серьёзный недостаток связанного списка не особо очевиден. Каждому узлу необходимо небольшое дополнительное место. Сколько ему нужно места? Можно подумать, что для него нужен только размер указателя, но это не совсем так. При динамическом создании объекта всегда существует небольшой запас. Некоторые языки программирования, например, C++, работают со страницами памяти. Обычно страница занимает 4 килобайта. При использовании операторы добавления и удаления, размещается целая страница памяти, даже если вам нужно использовать только один байт.

В Java и C# всё устроено немного иначе, в них есть специальные правила для небольших объектов. Для этих языков не требуется вся 4-килобайтная страница памяти, но всё равно у них есть небольшой запас. Если вы используете стандартные библиотеки, то о втором недостатке волноваться не нужно. Они написаны таким образом, чтобы минимизировать занимаемое впустую место.

Заключение

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

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

Часть 2. Линейные структуры данных с конечными точками

Представьте, что у вас есть куча листов бумаги.

Мы кладём один лист в стопку. Теперь мы можем получить доступ только к верхнему листу.

Мы кладём ещё один лист в стопку. Предыдущий лист теперь скрыт и доступ к нему невозможен, мы можем использовать верхний лист. Когда мы закончим с верхним листом, мы можем убрать его со стопки, открыв доступ к лежащему под ним.

В этом заключается идея стека. Стек — это структура LIFO. Это расшифровывается как Last In First Out («последним вошёл, первым вышел»). При добавлении и удалении из стека последний добавленный элемент будет первым удаляемым.

Для стека нужно всего три операции: Push, Pop и Top.

Push добавляет объект в стек. Pop удаляет объект из стека. Top даёт самый последний объект в стеке. Эти контейнеры в большинстве языков являются частью стандартных библиотек. В C++ они называются stack. В Java и C# это Stack. (Да, единственная разница в названии с заглавной буквы.) Внутри стек часто реализуется как динамический массив. Как вы помните из этой структуры данных, самыми быстрыми операциями на динамических массивах являются добавление и удаление элементов из конца. Поскольку стек всегда добавляет и удаляет с конца, обычно push и pop объектов в стеке выполняется невероятно быстро.

Очередь

Представьте, что вы стоите в очереди за чем-то.

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

Очередь — это структура FIFO (First In First Out, «первым зашёл, первым вышел»).

При добавлении и удалении из очереди первый добавляемый элемент будет первым извлекаемым. Очереди нужно только несколько операций: Push_Back, Pop_Front, Front и Back. Push_Back добавляет элемент к концу очереди. Pop_Front удаляет элемент из начала очереди. Front и Back позволяют получить доступ к двум концам очереди.

Программистам часто нужно добавлять или удалять элементы из обоих концов очереди. Такая структура называется двухсторонней очередью (double ended queue, deque). В этом случае добавляется ещё пара операций: Push_Front и Pop_Back. Эти контейнеры тоже включены в большинство основных языков. В C++ это queue и deque. Java определяет интерфейсы для очереди и двухсторонней очереди, а затем реализует их через LinkedList. В C# есть класс Queue, но нет класса Deque.

Внутри очередь и двухсторонняя очередь могут быть устроены довольно сложно. Поскольку объекты могут поступать и извлекаться с любого конца, внутренний контейнер должен уметь наращивать и укорачивать очередь с начала и с конца. Во многих реализациях используются множественные страницы памяти. Когда любой из концов разрастается за пределы текущей страницы, добавляется дополнительная страница. Если страница больше не нужна, то она удаляется. В Java используется следующий способ: для связанного списка требуется немного дополнительной памяти, а не страниц памяти, но для этого языка такая реализация вполне работает.

Очередь с приоритетом

Это очень распространённая вариация очереди. Очередь с приоритетом очень похожа на обычную очередь.

Программа добавляет элементы с конца и извлекает элементы из начала. Разница в том, что можно задавать приоритеты определённым элементам очереди. Все самые важные элементы обрабатываются в порядке FIFO. Потом в порядке FIFO обрабатываются элементы с более низким приоритетом. И так повторяется, пока не будут обработаны в порядке FIFO элементы с самым низким приоритетом.

При добавлении нового элемента с более высоким приоритетом, чем остальная часть очереди, он сразу же перемещается в начало очереди. В C++ эта структура называется priority_queue. В Java это PriorityQueue. В стандартной библиотеке C# очереди с приоритетом нет. Очереди с приоритетом полезны не только для того, чтобы встать первым на очереди к принтеру организации. Их можно использовать для удобной реализации алгоритмов, например, процедуры поиска A*. Наболее вероятным результатам можно отдать более высокий приоритет, менее вероятным — более низкий. Можно создать собственную систему для сортировки и упорядочивания поиска A*, но намного проще использовать встроенную очередь с приоритетом.

Заключение

Стеки, очереди, двухсторонние очереди и очереди с приоритетом можно реализовать на основе других структур данных. Это не фундаментальные структуры данных, но их часто используют. Они очень эффективны, когда нужно работать только с конечными элементами данных, а серединные элементы не важны.

Часть 3. Деревья и кучи.

Структуры данных «деревья»

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

Простое дерево

Дерево — это… дерево. У настоящего дерева есть корень, ветви, а на концах ветвей есть листья.

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

Одним из первых возникает вопрос: сколько каждый узел может иметь дочерних элементов?

Многие деревья имеют не больше двух дочерних узлов. Они называются двоичными деревьями. На примере выше показано двоичное дерево. Обычно дочерние элементы называются левым и правым дочерними узлами. Ещё одним распространённым в играх типом деревьев является дерево с четырьмя дочерними узлами. В дереве квадрантов (quadtree), которое можно использовать для покрытия сетки, дочерние узлы обычно называются по закрываемому ими направлению: NorthWest (северо-запад) или NW, NorthEast (северо-восток) или NE, SouthWest (юго-запад) или SW и SouthEast (юго-восток) или SE.

Деревья используются во многих алгоритмах (я уже упоминал о двоичных деревьях). Существуют сбалансированные и несбалансированные деревья. Бывают красно-чёрные деревья, АВЛ-деревья, и многие другие.

Хотя теория деревьев и удобна, она страдает от серьёзных недостатков: места для хранения и скорости доступа. Каким способом лучше всего хранить дерево? Наиболее простым способом является построение связанного списка, он же оказывается самым худшим. Предположим, что нам нужно построить сбалансированное двоичное дерево. Мы начинаем со следующей структуры данных:

Достаточно просто. Теперь представим, что в нём нужно хранить 1024 элемента. Тогда для 1024 узлов придётся хранить 2048 указателей.

Это нормально, указатели малы и можно обойтись небольшим пространством.

Вы можете помнить, что при каждом размещении объекта он занимает небольшую часть дополнительных ресурсов. Точное количество дополнительных ресурсов зависит от библиотеки используемого вами языка. Многие популярные компиляторы и инструменты могут использовать различные варианты — от всего лишь нескольких байтов для хранения данных до нескольких килобайтов, позволяющих упростить отладку. Я работал с системами, в которых размещение занимает не меньше 4 КБ памяти. В этом случае 1024 элементов потребуют около 4 МБ памяти. Обычно ситуация не настолько плоха, но дополнительные затраты на хранение множества мелких объектов нарастают очень быстро.

Вторая проблема — скорость. Процессорам «нравится», когда объекты находятся в памяти рядом друг с другом. У современных процессоров есть участок очень быстрой памяти — кэш — который очень хорошо справляется с большинством данных. Когда программе требуется один фрагмент данных, кэш загружает этот элемент, а также элементы рядом с ним. Когда данные не загружены в очень быструю память (это называется «промахом кэша»), программа приостанавливает свою работу, и ждёт загрузки данных. В самом очевидном формате, когда каждый элемент дерева хранится в собственном участке памяти, ни один из них не находится рядом с другим. Каждый раз при обходе дерева программа приостанавливается.

Если создание дерева напрямую связано с такими проблемами, то стоит выбрать структуру данных, работающую как дерево, но не обладающую его недостатками. И эта структура называется…

Чтобы вас запутать, скажу, что существует два вида куч.

Первая — это куча в памяти. Это большой блок памяти, в котором хранятся объекты. Но я буду говорить о другой куче.

Структура данных «куча» — это, в сущности, то же самое, что и дерево. У неё есть корневой узел, у каждого узла есть дочерние узлы, и так далее. Куча добавляет ограничения, её сортировка всегда должна выполняться в определённом порядке. Необходима функция сортировки — обычно оператор «меньше чем».

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

Кучи можно хранить в простом или динамическом массиве, то есть на её размещение тратится мало места. В C++ есть такие функции, как push_heap() и pop_heap(), позволяющие реализовать кучи в собственном контейнере разработчика. В стандартных библиотеках Java и C# нет похожего функционала. Вот дерево и куча с одинаковой информацией:

Почему их нет в стандартных библиотеках

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

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

Заключение

Важно знать о структурах данных «дерево», потому что в работе вам часто придётся их использовать. Также важно знать, что эти структуры данных при прямой реализации имеют недостатки. Вы можете реализовывать собственные структуры деревьев, просто знайте, что существуют более компактные типы. Зачем же я рассказал о них, если они на самом деле не используются в стандартных библиотеках? Они применяются в качестве внутренних структур в нашей следующей теме:

Часть 4. Нелинейные структуры данных.

Эти структуры данных отличаются от массивов и списков. Массивы — это последовательные контейнеры. Элементы в них расположены по порядку. При добавлении нескольких элементов в определённом порядке, они остаются в этом порядке.

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

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

Словарь данных

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

Если словари не были бы отсортированы, то поиск слов в них был невероятно сложным.

Существует два основных способа сортировки элементов в словаре: сравнение или хэш. Традиционное упорядочивание сравнением обычно более интуитивно. Оно похоже на порядок бумажном словаре, где всё отсортировано по алфавиту или по числам.

При сортировке элементов таким образом может потребоваться функция сравнения. Обычно эта функция по умолчанию является оператором «меньше чем», например a < b.

Второй способ сортировки элементов — использование хэша. Хэш — это просто способ преобразования блока данных в одно число. Например, строка «blue» может иметь хэш 0xa66b370d, строка «red» — хэш 0x3a72d292. Когда словарь данных использует хэш, он обычно считается неотсортированным. В действительности он всё равно отсортирован по хэшу, а не по удобному человеку критерию. Словарь данных работает тем же образом. Есть небольшая разница в скорости между использованием словарей с традиционной сортировкой и сортировкой по хэшу. Различия так малы, что их можно не учитывать.

В C++ есть семейство контейнеров map/mutimap или unordered_map/unordered_multimap. В Java семейство называется HashMap, TreeMap или LinkedHashMap. В C# это Dictionary или SortedDictionary. Каждое из них имеет собственные особенности реализации, например сортировка по хэшу или сравнением, допущение дубликатов, но в целом концепция одинакова. Заметьте, что в каждой из стандартных библиотек имеется их упорядоченная версия (в которой задаётся сравнение) и неупорядоченная версия (где используется хэш-функция). После добавления элементов в словарь данных вы сможете изменять значения, но не ключ.

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

Упорядоченное и неупорядоченное множество

Упорядоченное множество — это почти то же самое, что и словарь. Вместо ключа и значения в нём есть только ключ. Вместо традиционного словаря со словами и определениями там только слова. Множества полезны, когда вам нужно хранить только слова без дополнительных данных. В C++ семейство структур называется set/multiset или unordered_set/unordered_multiset. В Java это HashSet, TreeSet или LinkedHashSet. В C# они называются HashSet и SortedSet.

Как и в случае со словарями, существуют упорядоченные версии (где задаётся сравнение) и неупорядоченные версии (где используется хэш-функция). После добавления ключа его тоже нельзя изменять. Вместо этого нужно удалить старый объект и вставить новый. Часто они реализуются точно так же, как словарь данных, просто хранят только значение. Поскольку они реализуются так же, то они имеют те же характеристики. В множествах очень быстро ищутся и находятся значения, но они медленно работают при добавлении и удалении элементов.

Заключение

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

Часть 5. Правильный выбор структур данных.

В предыдущих частях мы перечислили самые часто используемые структуры данных.

Вкратце повторим их.

Существуют линейные структуры: массив, динамический массив и связанный массив. Они линейны потому, что остаются в том порядке, в котором из расположили. Массивы очень быстры при произвольном доступе и имеют относительно неплохую производительность при добавлении и удалении из конца. Связанный список очень хорош при частом добавлении и удалении из середины.

Есть линейные структуры данных с конечными точками: семейство стеков и очередей. Оба они работают примерно так же, как их аналоги в реальном мире. В стеке, например, в стопке тарелок или в стеке данных, можно «затолкнуть» (push) что-нибудь наверх, можно получить доступ к верхнему элементу и можно «столкнуть» (pop) этот элемент. Очередь, так же как очередь людей, работает добавлением к концу линии и удалением с начала линии.

Затем существуют нелинейные структуры данных: словарь данных, упорядоченное и неупорядоченное множество. Все они внутренне нелинейны, порядок, в котором вы добавляете их, в сущности, не связан с порядком, в котором вы получаете их обратно. Словарь данных работает примерно так же, как настоящий бумажный словарь. У него есть ключ (слово, которое мы ищем) и значение (определение слова). Упорядоченное множество — это точно то же, что и словарь данных, содержащий ключи, но не значения, и отсортированный. Неупорядоченное множество — это просто «мешок» с объектами. Название немного сбивает с толку, потому что на самом деле они упорядочены, просто способ упорядочивания неудобен для человека. Все эти структуры идеальны для быстрого поиска.

Эффект правильного выбора

Бо́льшую часть времени программистам приходится итеративно обрабатывать наборы данных.

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

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

Одна из самых частых задач в играх — поиск пути: необходимо найти маршрут из точки А в точку Б. Один из наиболее распространённых алгоритмов поиска пути — это A*. В алгоритме A* существует структура данных, содержащая частичные пути. Структура сортируется таким образом, чтобы наиболее вероятный частичный путь находился в передней части контейнера. Этот путь оценивается, и если он не является законченным, алгоритм превращает этот частичный путь в несколько частичных путей большего размера, а потом добавляет их в контейнер.

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

Выбор из паттернов

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

Динамический массив — выбор по умолчанию

В случае сомнений используйте динамический массив. В C++ это vector. В Java он называется ArrayList. В C# это List. В общем случае динамический массив — это то, что нужно. У него хорошая скорость для большинства операций, и неплохая скорость для всех остальных. Если вы выясните, что вам нужна другая структура данных, то с него перейти будет легче всего.

Стек — только один конец

Если вы используете добавление и удаление только с одного конца, то выбирайте стек. Это stack в C++, Stack в Java и C#. Существует много алгоритмов, использующих стековую структуру данных. Первый, который приходит мне в голову — это двухстековый калькулятор. Численные задачи, такие как «Ханойские башни», можно решить с помощью стека. Но, вероятно, вы не будете использовать эти алгоритмы в своей игре. Однако игровые инструменты часто выполняют парсинг данных, а парсеры активно используют стековые структуры данных, чтобы обеспечить правильное сочетание пар элементов. Если вы работаете с широким диапазоном типов ИИ, то стековая структура данных будет невероятно полезна для семейства автоматов, называемых автоматом с магазинной памятью (pushdown automaton).

Семейство очередей — первый вошёл, первый вышел.

Если вы добавляете и удаляете только с обоих концов, то используйте или очередь, или двухстороннюю очередь. В C++ это queue или deque. В Java можно использовать интерфейсы Queue или Deque, оба они реализованы с помощью LinkedList. В C# есть класс Queue, но нет встроенной Deque. Если вам нужно, чтобы важные события происходили первыми, но в остальном всё происходило по порядку, то выберите очередь с приоритетом. В C++ это priority_queue, в Java это PriorityQueue. В C# нужно реализовывать её самостоятельно.

Нелинейные структуры — быстрый поиск.

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

Связанный список — частые изменения с сохранением порядка

Если вы часто изменяете середину контейнера, и вам нужно обходить список только последовательно, то используйте связанный список. В C++ он называется list. В Java и C# это LinkedList. Связанный список — это отличный контейнер для случаев, когда данные только поступают и должны содержаться в порядке, или когда вам нужно периодически сортировать и перемещать элементы.

Заключение

Выбор подходящей структуры данных может сильно повлиять на скорость работы алгоритмов. Понимание основных структур данных, их преимуществ и недостатков, поможет вам в использовании наиболее эффективной структуры для любой задачи. Рекомендую вам в конечном итоге изучить их подробно. Полное изучение этих структур данных в колледже по специальности «Информатика» обычно занимает несколько недель. Надеюсь, вы уяснили основные структуры данных и сможете выбрать подходящую без долгой учёбы в колледже.

10 типов структур данных, которые нужно знать

Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

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

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

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

Связные списки

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

Так устроен связный список

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

Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.

Временная сложность связного списка

Упражнения от freeCodeCamp

Стеки

Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы только в её начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека, сперва придется убрать лежащие сверху.

Стек организован по принципу LIFO (Last In First Out, «последним пришёл — первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.

Так устроен стек

В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

Временная сложность стека

Упражнения от freeCodeCamp

Очереди

Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.

Так устроена очередь

Очередь устроена по принципу FIFO (First In First Out, «первый пришёл — первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue) и удалять первый элемент (dequeue).

Временная сложность очереди

Упражнения от freeCodeCamp

Множества

Так выглядит множество

Множество хранит значения данных без определенного порядка, не повторяя их. Оно позволяет не только добавлять и удалять элементы: есть ещё несколько важных функций, которые можно применять к двум множествам сразу.

• Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
• Пересечение анализирует два множества и создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
• Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
• Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.

Упражнения от freeCodeCamp

Map — это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:

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

Так устроена структура map

Упражнения от freeCodeCamp

Хэш-таблицы

Так работают хэш-таблица и хэш-функция

Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.

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

Таким образом, когда вы вводите пару ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.

Временная сложность хэш-таблицы

Упражнения от freeCodeCamp

Двоичное дерево поиска

Двоичное дерево поиска

Дерево — это структура данных, состоящая из узлов. Ей присущи следующие свойства:

1. Каждое дерево имеет корневой узел (вверху).
2. Корневой узел имеет ноль или более дочерних узлов.
3. Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

У двоичного дерева поиска есть два дополнительных свойства:

1. Каждый узел имеет до двух дочерних узлов (потомков).
2. Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.

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

Временная сложность двоичного дерева поиска

Упражнения от freeCodeCamp

Префиксное дерево

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

Так устроено префиксное дерево

Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Упражнения от freeCodeCamp

Двоичная куча

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

Так устроены минимальная и максимальная кучи

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

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Временная сложность двоичной кучи

Упражнения от freeCodeCamp

Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

По такому принципу устроены социальные сети: узлы — это люди, а рёбра — их отношения.

Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.

Граф в виде матрицы смежности

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

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

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

Временная сложность списка смежности (графа)

Упражнения от freeCodeCamp

Узнать больше

Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.

Мнение автора и редакции может не совпадать. Хотите написать колонку для «Нетологии»? Читайте наши условия публикации.

Разбираемся в алгоритмах и структурах данных. Доступно и понятно

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

Всем привет. Меня зовут Адам Леос, и я Senior Software Engineer в PlutoTV. Кроме основной работы, я активно участвую в развитии IT-сферы и повышении уровня разработчиков в целом. Например, я принимаю участие в хакатонах (как участник и как судья), пишу технические статьи, провожу вебинары и выступаю с докладами как приглашенный технический специалист в компаниях и как спикер на конференциях.

Темы для своих презентаций я подбираю так, чтобы это был не пиар себя/компании/технологии, а чтобы материал привнес что-то нужное, был полезен разработчику (желательно непосредственно сразу). Одна из таких тем — необходимость знания алгоритмов и структур данных. По определенным причинам среди разработчиков из стран СНГ бытует мнение, что эти знания не нужны и не важны. Спойлер! Это не так.

Для кого предназначена эта статья? Она будет полезна каждому, кто желает добиться одной (или нескольких, можно всех) из следующих целей:

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

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

Выступление на JSFest 2019 в Киеве

Статья будет базироваться на двух тезисах (и опровергать их):

1. Первый — «Знать алгоритмы и структуры данных не нужно. Никакой пользы разработчик от этих знаний не получит». Мы поймем, почему это не так, и разберем примеры из реальной жизни, как я применял эти знания в нескольких компаниях и получал огромный прирост в производительности.
2. Второй тезис для разработчиков, которые ушли немного дальше и считают так: «Вроде польза и может быть, но, чтобы ее получить, необходимо потратить очень много времени на изучение материала, который к тому же очень сложный». Для этого мы усвоим базовые знания и все необходимые вещи в самом начале этой статьи (поговорим о сложности алгоритма, нотации Big O, сортировках, самых популярных структурах данных и их использовании для оптимизации проекта).

Сложность алгоритма

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

Сразу обращу ваше внимание на «ресурсы». Какими ресурсами мы оперируем в разработке? Очевидно, это время (то, насколько быстро будет выполняться наш алгоритм: дольше выполняем — больше времени тратим © Кэп). Но, к возможному удивлению многих разработчиков, еще один ресурс, которым мы часто оперируем (да, и во front-end-разработке тоже), — это память. Безусловно, работая за свеженьким MacBook Pro под последним Chrome, вы можете никогда и не столкнуться с проблемами перерасхода памяти (хотя и с таким неоднократно сталкивался, разработчики могут создать утечек от души), но память — такой же ценный ресурс, как и время. Особенно остро я ощутил это в последних нескольких компаниях, занимаясь разработкой под разные платформы типа Smart TV, игровых приставок и прочего, обладающего очень слабым железом (телевизор за $20 000 будет слабее вашего смартфона, что уж говорить о более дешевых моделях).

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

Здесь мы получили массив, объявили переменную-сумму, изначально равную 0, и запустили итерацию по массиву, беря каждый элемент массива и добавляя его к сумме. Все просто. Теперь давайте проанализируем: что будет, если мы вызовем эту функцию с массивом из пяти чисел [1, 2, 3, 4, 5]? Очевидно, мы сделаем пять итераций — за каждый элемент в массиве, чтобы взять его и добавить к сумме. А что, если массив будет состоять из десяти чисел? Логично, что потребуется десять итераций.

Паттерн очевиден: чем длиннее массив мы передаем, тем больше итераций мы делаем (соответственно, больше времени тратим на выполнение). Только что мы выразили сложность алгоритма, и, вспомнив определение выше (как будет расти расход ресурсов с увеличением размера входных данных), мы увидим, как же рос расход ресурсов в нашем случае (расход времени — делали больше итераций) с увеличением размера входных данных (массива-инпута). Так, у нашего алгоритма сейчас линейная зависимость от входных данных: за каждый элемент массива мы делаем дополнительную итерацию.

Нотация Big O

Лучше всего зависимости можно увидеть на графиках, и для описания таких зависимостей существует нотация Big O (это те самые O(n), O(log n) и прочие, которые мы рассмотрим чуть дальше). Если выразить, что это такое, одним предложением, то это будет звучать так: функция, которая описывает рост сложности алгоритма. Что за сложность алгоритма и как она может расти, мы примерно себе представили. Big O — это функция, которая этот рост описывает. Единственное уточнение: функция фигурирует здесь в математическом смысле, то есть как функция, которая используется для построения графика.

Давайте возьмем наш синтетический код из примера выше и построим график зависимости размера входных данных от количества итераций. По оси X (горизонтальной) мы возьмем рост входных данных от 0 до какого-то конечного числа n. Основными точками пускай будут 1, 100, 1000 и 10 000 единиц (элементов в массиве). По оси Y (вертикальной) будет рост количества операций также от 0 вверх с основными точками в 1, 100, 1000, 10 000 операций. Остается только провести линию по зависимости, что была у нас в алгоритме.

Как вы помните, на каждый элемент в массиве нам необходимо сделать дополнительную операцию сложения. Значит, если нам пришло 100 элементов, делаем 100 операций. Приходит 10 000 элементов — делаем 10 000 операций. Приходит n элементов — делаем n операций. Вот и та самая n в сложности O(n), которая также называется линейной. Все очень просто.

График линейной функции, или О(n)

Здесь все классно, но надо посмотреть с разных сторон и на других примерах, чтобы закрепить. Рассмотрим новый пример простойПосчитать (simpleCalculate). Мы ничего не принимаем и выполняем какие-то операции: вычисляем переменные, выводим что-то в консоль (просто чтобы было больше операций) и возвращаем разницу.

Сложность такого алгоритма O(1) — постоянная, или константная. Здесь тоже все примитивно: наш алгоритм вообще ничего не принимает, поэтому никак не зависит от входных данных. Соответственно, даже если бы по какой-то причине в него передавали различные значения, он бы постоянно выполнял одни и те же операции, никак не увеличивая и не уменьшая расход ресурсов, поэтому сложность постоянная. На графике это показано еще доступнее:

График константной функции, или O(1)

Как видно на графике, у нас просто прямая линия: количество операций не растет и постоянно при любых значениях входных данных. Единственный важный для понимания момент здесь — в обозначении сложности O(1). Единица не указывает на количество операций и не будет меняться на другие числа, если алгоритм будет выполнять больше операций (как минимум наш алгоритм тоже выполняет больше операций). Единица здесь, так же, как и n в O(n), — это специальное обозначение, в этом случае константной сложности, и все.

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

Сложность этого алгоритма также будет O(1). Несмотря на то что мы уже принимаем аргумент и используем его, все, что мы делаем, — одну дополнительную операцию по сложению. Какое бы большое, маленькое, дробное или отрицательное число ни было, мы всегда просто берем его и складываем одной операцией (естественно, при условии, что оно помещается в память, но это уже совсем другая история), то есть количество операций постоянно и не зависит от инпута.

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

Здесь-то у нас уже появляется снова линейная зависимость от размера входных данных, знакомая нам по первому примеру. Больше массив — больше операций мы делаем для вычисления дополнительного слагаемого. Помните сложность такого алгоритма? O(n).

Отлично, сейчас многим может показаться, что они раскусили систему: если входные данные — это массив, то сложность всегда линейная, О(n), и думать здесь нечего. Но мы можем посмотреть на такую версию предыдущего кода.

В этот раз, все еще принимая массив аргументов, мы просто берем его длину как дополнительное число для сложения. А получение длины массива, хранящейся в отдельном свойстве, — мгновенная (та же константная) операция. Поэтому какой бы большой массив мы сюда ни передали, мы всегда будем мгновенно получать его длину и одной операцией добавлять к разнице. Итого это константная сложность, O(1).

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

Сложность такого алгоритма уже значительно выше, за каждый элемент массива нам нужно сделать полную итерацию по массиву. То есть, имея лишь массив из пяти элементов [1, 2, 3, 4, 5], мы проделаем 25 операций. Применив простейшую математику, мы можем прийти к тому, что нам требуется квадрат операций на наш размер входных данных. Эта сложность называется квадратичной и обозначается О(n^2). График демонстрирует резко растущий расход ресурсов такого алгоритма.

График квадратичной функции, или О(n^2)

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

Как вы уже догадались, сложность такого алгоритма — O(n^2). По сути, здесь присутствует тот же вложенный цикл. Реализация метода indexOf под капотом — это обычный цикл, обход массива: так как индексы каждого элемента в массиве не хранятся, то его надо найти. Само собой, опытный разработчик об этом знает. Правда, если при этом опытный разработчик не знает алгоритмов, то, скорее всего, он этот код так и оставит. К слову, оптимизация здесь была бы суперпростой. В методе forEach второй аргумент — это индекс итерируемого элемента, и легким движением руки квадратичная сложность превращается в линейную, потенциально сохраняя нам большое количество ресурсов на выполнение.

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

Сложность этого алгоритма будет не O(n + n^2), а просто квадратичная, O(n^2) — как раз потому, что квадрат будет расти несоизмеримо быстрее, делая влияние линейной сложности нерелевантной.

Пример роста в цифрах

Чтобы увидеть разницу, полезно взглянуть на сравнение количества операций в зависимости от сложности с одинаковыми размерами входных данных. Давайте смоделируем ситуацию, когда у нас на вход приходит массив с 10 000 (десятью тысячами) элементов, и определим, сколько операций проделают разные сложности:

• O(1), константная — 1 (одна) операция;
• O(log n), логарифмическая (например, бинарный поиск) —

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

Image Source

Несколько полезных комментариев к картинке:

• Обратите внимание на зеленую зону, там присутствует как константная сложность, так и логарифмическая. Как вы уже видели выше в примере с числами, логарифмическая сложность очень эффективна. Она почти так же хороша, как и константная.
• Сложность O(n * log n) — это лучшая сложность универсальных сортировок. Мы к этому еще вернемся.
• Несмотря на то что квадратичная сложность находится в красной зоне («ужасной»), правильно будет упомянуть, что задачи бывают разные. И иногда вы ну никак не можете достать что-то из своих данных эффективнее, чем за двойной обход. Но это будет как раз тем местом, куда вы должны смотреть, когда захотите оптимизировать участки логики для повышения производительности. О методах и подходах мы поговорим чуть дальше.
• Важный момент — начало всех графиков. Очевидно, что все они начинаются из одной точки и их рост при небольших значениях еще не так сильно заметен и критичен. Именно поэтому необходимо тестировать свои алгоритмы не на одном пользователе/товаре/записи, а на максимально приближенном к реальности (а лучше на еще большем, с запасом). Иначе и O(1), и O(n^2), и даже О(n!) дадут вам один результат (единица в квадрате — единица, факториал единицы — единица).

Структуры данных

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

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

Какие основные операции мы проворачиваем с данными? Все задачи в основном сводятся к следующим операциям:

• доступ (получить данные);
• поиск (найти данные);
• вставка (добавить данные);
• удаление (удалить данные).

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

Image Source

От разработчика требуется понимание, что есть разные структуры с разной эффективностью для разных задач. И знание структур данных подразумевает просто грамотное использование самой подходящей (максимально эффективной) структуры для решения какой-либо задачи. Надо часто искать? Берете это. Часто что-то вставляете? Берете другое. Приходится переставлять и удалять? Берете третье.

Дальше давайте поговорим о самых ярких представителях жанра в ежедневной разработке и об их грамотном использовании.

Массивы

Самой первой и, возможно, самой популярной структурой будут массивы. Давайте взглянем на основные манипуляции, которые мы производим с массивами, и проанализируем сложность. Вот есть у нас массив:

Что мы можем с ним делать? Очевидно, получить какой-то из элементов по индексу.

Как считаете, какова сложность этой операции? Кто предположил (или знал), что это O(1), оказался прав. Мы можем мгновенно по уникальному идентификатору (индексу) получить любой элемент массива (даже которого там нет, просто получим undefined). Так же можно и записывать по индексу.

Так делать (обычно) все же не стоит, ибо это чревато последствиями: можно получить «дырки» в массиве и прочие радости мутаций. Но это уже другая тема.

Ладно, давайте о методах: например, добавление элемента в конец массива.

Сложность такой операции будет O(1).

Примечание. Добавление элемента в конец списка в JavaScript — константная операция, только не обычная, а «амортизированная». Что это значит? В JS мы не управляем памятью напрямую, но в языках программирования, где мы ей управляем, создание массива под наши нужды будет немного отличаться. Нам будет необходимо выделить память под массив определенного размера. То есть выделив память на массив длиной в 20 элементов и захотев добавить 21-й, мы будем вынуждены выделять еще память, что является О(n)-операцией. Несмотря на то что мы не делаем такого в JavaScript, это происходит «под капотом». И хотя преимущественно мы будем вставлять элементы в О(1), иногда могут быть «скачки», когда под наш новый элемент выделяется больше памяти. Так что эта операция как бы константная, но амортизированная.

Что у нас с удалением с конца массива?

Здесь мы имеем также O(1). Хорошо, а что с задачами добавления и удаления с начала массива?

Как многие знают (или догадались по подводке), здесь мы имеем другую картину. Вставка и удаление элемента с начала списка имеют сложность О(n). Все потому, что, манипулируя элементами в начале списка, мы должны обновить индексы всех последующих элементов. Если произошло удаление, то элемент, который был вторым, должен стать первым, вторым станет третий и т. д. То же самое происходит при вставке в начало: требуется обновить индексы всех последующих элементов.

Это, как вы сами видите, значительно менее эффективно. Именно поэтому разнообразные реализации стеков (stack) базируются на push & pop, а не на unshift & shift. Немного о стеках. Представьте стопку документов на подпись: тот, что лежит сверху, и берем первым для подписи. Если мы что-то добавляем, то кладем поверх всех, и он становится первым для следующей подписи. Это еще называется LIFO — last in, first out (последним вошел — первым вышел). Самым популярным применением в программировании будут разнообразные стеки операций: например, стек изменений в редакторе кода, чтобы иметь возможность быстро отменять изменения и возвращаться к предыдущим состояниям, или стек передвижения по страницам в браузере, чтобы быстро переходить по страницам.

Напоследок обязательно стоит упомянуть другие методы работы с массивами, которые имеют О(n)-сложность (как в примере с indexOf). Это будут практически все методы по работе с массивами — все, где мы что-то фильтруем, ищем, перебираем, переворачиваем и даже превращаем в строку (toString) — все это имеет O(n)-сложность.

Объекты

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

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

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

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

Как вы можете догадаться, сложность этих методов — О(n): надо пройти по всем значениям, создавая из них массив.

Именно благодаря тому, что каждое свойство объекта — уникальный идентификатор и по этому уникальному ID мы можем мгновенно получать, записывать, удалять и обновлять данные, объекты часто используются как вспомогательная структура для многих оптимизаций через маппинг. Для многих это может быть знакомо по аналогам из других языков: словарю (dictionary) или «карте» (map). К слову, в ES2015 в JS тоже добавили объект Map — как раз для такого использования. Кто не знаком, он предоставляет методы для всех тех манипуляций, которые мы проводили раньше с объектом, имитируя Map. Например:

• Проверить, есть ли запись (has), вместо сравнения с undefined.
• Получить по ключу (get) и записать (set).
• Применить forEach сразу к map, итерируя на месте по связкам (ключ, значение).
• Прочие удобности.

Теперь давайте взглянем на применение. Начнем с решения очень популярной на собеседованиях задачи (например, ее устное решение спрашивали у меня в Microsoft). Задача — посчитать количество уникальных символов в строке. Решение тривиально и работает с любыми символами:

Результатом вызова с какой-либо строкой будет карта по уникальным символам и их количеству:

То есть мы создали карту и заполнили символами из строки, где каждый символ — уникальный идентификатор. Так мы могли мгновенно проверить его наличие в карте, получить значение и перезаписать его. И это работало для любого символа любого языка, специальных символов и даже пробелов. В общем, идею маппинга вы уловили: это создание вспомогательной структуры для определенных операций за О(1). Теперь давайте перейдем к их применению в реальной жизни.

Полезный маппинг в реальном мире

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

Краткое описание проекта: делал я как-то видеостриминговое приложение на ReactJS + Node.js для альтернативных платформ типа Smart TV и игровых приставок.

«Типа Netflix», только еще с телевизионными Live-каналами

Была там одна задача, которую решили еще до моего прихода на проект. Ситуация была следующая. У нас в приложении есть тысячи шоу: какие-то сериалы, фильмы — весь видеоконтент приложения со следующей структурой (все упрощено и переименовано в угоду простоте восприятия и для удовлетворения NDA, все совпадения случайны):

То есть массив из множества объектов, представляющий отдельное шоу и хранящий информацию по этому шоу, — стандартные ID, name и прочее.

Ну и в каких-то моментах мы получаем другой массив «забаненных» шоу. По определенным причинам мы не хотим показывать это шоу пользователю: конкретно что-то с пользователем, или канал сегодня решил не показывать это, или вообще там проблемы с транслированием именно на этом канале именно для этого пользователя и прочие мутные бизнес-причины. У нас есть массив других объектов, хранящих немного информации, достаточной для бана каких-то шоу «на месте».

И вот код, как это было решено:

Что здесь происходит? Начинается цикл по всем шоу, берется ID каждого из этих шоу и запускается обход забаненных шоу с целью найти совпадения. Если совпадение есть, шоу должно быть забанено (условно помечаем флагом isBanned).

Чей-то опытный глаз уже мог заметить проблему (и возможно, нервно задергаться). Вообще, здесь совершается слишком много ненужных операций: мы для каждого шоу запускаем итерацию по забаненным, это очень большая и лишняя нагрузка. А ведь оптимизируется это очень легко, нам нужна лишь карта забаненных ID, с помощью которой мы бы могли мгновенно проверять, забанено шоу или нет. Реализовать это можно как с помощью обычных объектов, так и с помощью Map или даже Set (Set — это просто набор, то есть оперируем как с Map, только никаких значений записям не присваиваем, просто добавляем уникальные ключи, чтобы они были в наборе, и выполняем мгновенные проверки на их наличие):

Что изменилось: мы вынесли вложенный цикл итерирования по забаненным шоу наружу и проходим по нему всего один раз для заполнения нашего Set, который будет набором всех забаненных ID с возможностью мгновенно проверять, есть ли там определенная запись. В итоге мы не запускаем множество ненужных циклов внутри обхода всех шоу, а делаем лишь мгновенную проверку на наличие итерируемого шоу в списке (Set) забаненных. И если совпадение есть, то шоу должно быть помечено как забаненное.

Это можно реализовать как еще короче, так и более развернуто и доступно. Можно использовать объект вместо Set и просто делать запись в объект, где ключом будет тот же уникальный ID забаненного шоу, а значением — что угодно, то же булево true. И затем для проверки, забанено ли итерируемое шоу, достаточно «постучаться» в объект по ID, и мы получим либо true, что будет значить, что шоу надо банить, либо undefined, а значит, шоу в забаненных нет, пропускаем.

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

Память в реальном мире

А с памятью все тоже просто (хоть и менее прозрачно). В качестве примера я буду использовать оптимизацию, которую я сделал уже на текущем проекте в PlutoTV (тоже видеостриминговое приложение на React под телевизоры и приставки).

Был вот такой красивый и функциональный код:

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

Кто уже увидел проблему для памяти? Что делают методы filter и map? Возвращают новый массив, под который необходимо выделить память, возможно, много (возможно, непозволительно много для некоторых платформ). А существует этот массив лишь для того, чтобы по нему запустить новый цикл и провернуть другую операцию с теми же элементами, что и в предыдущем цикле. Какое расточительство памяти на ровном месте!

Исправить это можно очень просто, заменив все на один обход. Например, с помощью reduce:

Идея, как видите, очень проста. Мы имеем один reduce (можно даже заменить фильтрацию, просто не наполняя аккумулятор по условию). Естественно, можно записать как короче, так и размашистее, кто как любит. Суть в том, что мы не выделяем кучу памяти под новые массивы, которые даже толком не используем. Эта маленькая оптимизация позволила сохранить от 10% до 30% расхода памяти приложения в зависимости от старины девайса. Что очень много: 30% для одного места, когда все приложение еще должно где-то работать.

Сортировки

Еще очень полезно будет разобраться с сортировками. Сразу скажу, что необходимость реализовывать какую-то свою уникальную сортировку у вас будет появляться крайне редко (а то и вовсе не случится за всю карьеру), так как в каждом языке программирования присутствуют довольно хорошо оптимизированные методы сортировки (отличным примером будут оптимизации array.sort() в JavaScript, которые мы обязательно разберем дальше). Но сортировки вне зависимости от необходимости их реализовывать — это очень классный пример алгоритмов и балансировки между расходами времени и памяти. Так что давайте взглянем на две самые популярные сортировки с очень разными расходами ресурсов.

Первым делом мы посмотрим на знакомую многим сортировку пузырьком (Bubble Sort). Идея этой сортировки в том, чтобы, проходя по массиву, находить самый большой элемент и «протаскивать» его до конца массива. Очевидно, чтобы отсортировать таким образом, когда за один обход мы дотаскиваем только один самый большой элемент, нам потребуется n обходов массива (где n — длина массива). А когда нам необходимо сделать n обходов, каждый из которых заключается в полном обходе массива, это O(n^2)-сложность. Ну вы и сами уже знаете.

Давайте посмотрим на визуализацию, а затем погрузимся в реализацию.

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

В коде все будет тоже очень просто.

Бесполезна ли эта сортировка, имеющая аж квадратичную сложность, когда есть более быстрые универсальные сортировки? Отнюдь. Как мы могли наблюдать, у сортировки пузырьком (как и у подобных ей, типа сортировки вставками) есть одно довольно важное преимущество — расход памяти. Здесь нам требуется лишь одна вспомогательная переменная для смены мест двух элементов, то есть константная сложность по памяти. Это огромная разница по сравнению со следующей быстрой универсальной сортировкой — сортировкой слиянием. Давайте взглянем на нее.

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

Благодаря постоянной разбивке пополам и попарному слиянию сложность этой сортировки — O(n * log n), то есть длина массива (надо как минимум раз полностью пройти по массиву), умноженная на логарифм от длины (сложность постоянного деления пополам). Сейчас взглянем на код и на еще одну визуализацию, и все должно стать понятно.

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

Посмотрим на еще одну визуализацию, на которой хорошо видно, как массивы разбиваются и затем попарно сливаются обратно. Сразу после визуализации перейдем к методу merge.

В чем будет заключаться наша логика слияния? У нас приходят два массива: левый и правый. Оба либо уже отсортированы (см. логику выше), либо просто состоят из одного элемента. Теперь нам нужно начать обход по обоим (достаточно одного обхода с двумя указателями: первый указывает на итерируемый элемент левого массива, второй — на итерируемый элемент правого массива) и брать меньший из двух элементов, закидывая его в новый массив, который мы вернем как отсортированный.

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

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

Так что теперь мы можем качественно понять, что за оптимизации скрыты под капотом у array.sort(). Несмотря на то что имплементации могут отличаться от браузера к браузеру (и даже от версии к версии), глобальная идея заключается в том, чтобы использовать сортировку слиянием и быструю сортировку (также O(n * log n)) в зависимости от типа данных в массиве. Но массив не разбивается на подмассивы до одного элемента, как в нашей реализации. Вместо этого разбивание останавливается на 10 элементах, и уже к этим массивам из 10 элементов применяется сортировка вставками (аналог пузырьковой, O(n^2)). И лишь после этого начинается алгоритм слияния / быстрой сортировки. Таким образом, экономится очень много памяти (не создается целая куча лишних массивов) и практически нет проигрыша по быстродействию (сортировка вставками довольно эффективна на небольших массивах). Вот и чудесный пример балансировки между быстродействием и расходом памяти.

Важное послесловие о сортировках: я не просто так несколько раз писал, что сортировка слиянием и быстрая сортировка — это лучшие универсальные сортировки. То есть они будут стабильно хорошо работать в любых ситуациях с любыми данными (естественно, в пределах разумного). Хотя да, существуют разные сортировки со сложностью лучше, чем O(n * log n): например, radix sort. Но их применение специфично и не является универсальным. Хотя такие сортировки, само собой, широко применяются, просто они эффективны в конкретных ситуациях.

Выводы

• Вам не нужно знать все алгоритмы и структуры данных. Самые необходимые знания, дающие больше всего пользы, в то же время являются и самыми простыми в освоении.
• Нет необходимости помнить все реализации, вы даже можете забыть какие-то самые важные. Достаточно один раз разобраться в них, чтобы иметь представление о возможностях.
• Анализируйте ваши алгоритмы. Задумывайтесь над их эффективностью. Чем более эффективный код вы создаете, тем производительнее и надежнее будет ваш продукт (и тем круче вы станете как разработчик).

Полезные материалы

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