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

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

  • автор:

9 структур данных, которые вам понадобятся

9 структур данных, которые вам понадобятся

Еще в девяностые профессор Корейского университета передовых технологий Сонгчун Мун предложил Биллу Гейтсу назвать свой стартап Microdata, а не Microsoft. Мун указал на то, что данные и их структура — будущее программирования.

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

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

#1. Массив (Array)

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

Представьте себе записную книжку со страницами, пронумерованными от 1 до 10. Каждая из них может содержать информацию или быть пустой. Блокнот — массив страниц, страницы — элементы массива «блокнот». Программно вы извлекаете информацию со страницы, обращаясь к ее индексу, то есть «блокнот+4» будет ссылаться на содержимое четвертой страницы.

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

#2. Матрица (Matrix)

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

Матрицы используют для описания вероятностей. Например, для ранжирования страниц в поиске Google при помощи алгоритма PageRank. В компьютерной графике — для работы с 3D-моделями и проецирования их на двумерный экран.

#3. Связный список (Linked list)

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

Начальный элемент этой структуры называется головой, а все последующие узлы цепочки — хвостом. Хвост состоит из элементов двух типов: с информацией (info) и с указанием на следующий узел (next). Конец цепочки обозначается как null.

#4. Стек (Stack)

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

Новые элементы стека заменяют старые. Принцип работы такой структуры — LIFO (last in — first out, «последним пришел — первым ушел»). Поэтому стек еще называют магазином — по аналогии с огнестрельным оружием: выстрелит патрон, который был заряжен последним.

Эта структура данных реализована в функции «отменить» (undo). Программа сохраняет статус работы так, что последнее действие становится первым в очереди на отмену. В стеке возможны всего три операции: добавление элемента (push), удаление (pop), чтение (peek).

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

Существует похожая СД — дек (deque — double ended queue, «двусторонняя очередь»). Это стек с двусторонним доступом.

#5. Очередь (Queue)

Этот тип СД напоминает стеки, но принцип работы реализован как FIFO (first in — first out, «первым пришел — первым ушел»). Как в супермаркете: первым покупки унесет домой тот, кто раньше всех займет очередь.

Очереди используются, когда ресурс нужно распределить между несколькими потребителями (работа ЦП, пропускная способность роутера). Или когда данные передаются асинхронно, то есть скорости приема и отдачи — разные.

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

#6. Дерево (Tree)

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

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

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

Но деревья сложно хранить и у них невысокая скорость работы.

Data Science with Python

Director of Data Science в Shelf

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

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

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

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

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

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

Структура данных относится, по существу, к «пространственным» понятиям: ее можно свести к схеме организации информации в памяти компьютера.

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

Классификация структур данных

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.

Понятие «ФИЗИЧЕСКАЯ структура данных» отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.

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

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами . Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных — простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных — ее изменчивость — изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

Рис. Классификация структур данных

Важный признак структуры данных — характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур — многосвязные списки, деревья, графы.

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

Информация по каждому типу однозначно определяет :

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

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.

Операции над структурами данных

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

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

Главное заключается в том, что независимо от используемого языка программирования, имеющиеся в программе структуры данных не появляются «из ничего», а явно или неявно объявляются операторами создания структур. В результате этого всем экземплярам структур в программе выделяется память для их размещения.

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

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

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

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

Структурность данных и технология программирования

знание структуры данных позволяет организовать их хранение и обработку максимально эффективным образом — с точки зрения минимизации затрат как памяти, так и процессорного времени. Другим не менее, а может быть, и более важным преимуществом, которое обеспечивается структурным подходом к данным, является возможность структурирования сложного программного изделия. Программисту, который хочет, чтобы его программа имела реальное применение в некоторой прикладной области не следует забывать о том, что программирование — это обработка данных. Таким образом, задачей любого программного изделия является преобразование входных данных в выходные. Инструментальные средства программирования предоставляют набор базовых (простых, примитивных) типов данных и операции над ними. Интегрируя базовые типы, программист создает более сложные типы данных и определяет новые операции над сложными типами. Ключевым понятием в СУБД является понятие модели данных, в основном тождественное понятию логической структуры данных. Отметим, что физическая структура данных в СУБД не рассматривается вообще. Но сами СУБД являются программными пакетами, выполняющими отображение физической структуры в логическую (в модель данных). Для реализации этих пакетов используются те или иные системы программирования, разработчики СУБД, следовательно, имеют дело со структурами данных в терминах систем программирования. Для пользователя же внутренняя структура СУБД и физическая структура данных совершенно прозрачна; он имеет дело только с моделью данных и с другими понятиями логического уровня.

Массив

image

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

// Таблица рекордов int score1 = 0; int score2 = 0; int score3 = 0; int score4 = 0; int score5 = 0;

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

// Таблица рекордов const int NUM_HIGH_SCORES = 5; int highScore[NUM_HIGH_SCORES] = ;

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

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

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

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

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

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

// Внутреннее устройство класса динамического массива sometype *internalArray; unsigned int currentLength; unsigned int maxCapacity;

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

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

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

При добавлении объекта к динамическому массиву каждый объект может переместиться в памяти. В таких языках, как C и C++, добавление к динамическому массиву означает, что ВСЕ указатели на объекты массива становятся недействительными.

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

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

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

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

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

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

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

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

// Узел связанного списка sometype data; Node* next;

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

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

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

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

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

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

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

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

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

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

Если вам нужно получить пятисотый элемент массива, то достаточно просто посмотреть на 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.

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

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

// Узел дерева Node* left; Node* right; sometype data;

Достаточно просто. Теперь представим, что в нём нужно хранить 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. Связанный список — это отличный контейнер для случаев, когда данные только поступают и должны содержаться в порядке, или когда вам нужно периодически сортировать и перемещать элементы.

Заключение

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

На этом статья завершается. Благодарю за чтение.

  • Программирование
  • Разработка игр

7 структур данных, которые пригодятся каждому программисту

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

Что такое структуры данных

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

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

Главная особенность структур — любая единица данных должна быть размещена на определенном месте, по которому её легко будет отыскать. Как формируется это место и каким образом его ищут, зависит от вида структуры.

Классификация основных структур данных

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

Массивы делятся на два вида: одномерные — все элементы обладают только одним индексом, и многомерные — у каждого элемента несколько индексов. Информацию в массиве можно просматривать, фильтровать и менять.

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

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

В этой структуре можно включать и убирать элементы только из начала списка. Она функционирует по принципу LIFO: последний добавленный элемент в стеке должен будет уйти первым.

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

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

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

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

Если вы хотите бесплатно пройти обучение, совместно с командой разработать отечественные программы с искусственным интеллектом для известных организаций, то вам стоит поучаствовать в нашем проекте «Цифровой прорыв. Сезон: искусственный интеллект».

Читайте нас в Telegram — stranavozmojnostey Поделиться в социальных сетях

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

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