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

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

  • автор:

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

Массив

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

Заключение

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

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

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

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

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.

Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.

Сегодня мы узнаем всё о структурах данных.

«Оооооой как интересно. », да?

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

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

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

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

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

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

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

/*** ===================================================================== ***\ * * * ,--,--. ,--,--. * * ,----------. | | | | | | _____ * * |`----------'| | | | | | | | | ,------. * * | | | | | | | | ,--. | o o | |`------'| * * | | ,| +-|-+ | | +-|-+ |` | | |_____| | | * * | | ,:==| | |###|======|###| | |====#==#====#=,, | | * * | | || `| +---+ | | +---+ |' ,,=#==#====O=`` ,| | * * | | || | | | | | | ``=#==#====#=====|| | * * `----------' || | | | | | | |__| `| | * * | | ``=| |===`` `--,',--` `--,',--` /||\ `------' * ** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| ** \*** ===================================================================== ***/

Алгоритмы

Алгоритм — такое хитроумное название для последовательности совершаемых действий.

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

Любая данная задача реализуется бесконечным количеством способов. Как следствие, для решения распространённых задач изобрели множество различных алгоритмов.

Например, для сортировки неупорядоченного множества элементов существует до смешного большое количество алгоритмов:

Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка.

Некоторые из них значительно быстрее остальных. Другие занимают меньше памяти. Третьи легко реализовать. Четвёртые построены на допущениях относительно наборов данных.

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

Для сравнения производительности алгоритмов используется грубое измерение средней производительности и производительности в худшем случае, для обозначения которых используется термин «О» большое.

/*** ===================================================================== ***\ * a b d * * a b O(N^2) d * * O(N!) a b O(N log N) d c * * a b d c * * a b d c O(N) * * a b d c * * a b d c * * a b d c * * ab c O(1) * * e e e e ec d e e e e e e e e * * ba c d * * ba c d f f f f f f f * ** cadf f d f f f f f O(log N) ** \*** ===================================================================== ***/

О большое

«О» большое — обозначение способа приблизительной оценки производительности алгоритмов для относительного сравнения.

О большое — заимствованное информатикой математические обозначение, определяющее, как алгоритмы соотносятся с передаваемым им некоторым количеством N данных.

О большое характеризует две основные величины:

Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.

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

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

Вот некоторые распространённые значения О большого:

Имя Нотация Что вы скажете, припрись они к вам на вечеринку ---------------------------------------------------------------------------- Константная O(1) ОХРЕНЕННО!! Логарифмическая O(log N) КРУТО! Линейная O(N) НОРМАС. Линейно- логарифмическая O(N log N) БЛИИИН. Полиномиальная O(N ^ 2) ОТСТОЙ Экспоненциальная O(2 ^ N) ОТВРАТИТЕЛЬНО Факториальная O(N!) ТВОЮЖМАТЬ

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

 N = 5 10 20 30 ----------------------------------------------------------------------- O(1) 1 1 1 1 O(log N) 2.3219. 3.3219. 4.3219. 4.9068. O(N) 5 10 20 30 O(N log N) 11.609. 33.219. 84.638. 147.204. O(N ^ 2) 25 100 400 900 O(2 ^ N) 32 1024 1,048,576 1,073,741,824 O(N!) 120 3,628,800 2,432,902,0. 265,252,859,812,191,058,636,308,480,000,000 

Как видите, даже при относительно небольших числах можно сделать *дофига* дополнительной работы.

Структуры данных позволяют производить 4 основных типа действий: доступ, поиск, вставку и удаление.

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

 Доступ Поиск Вставка Удаление ------------------------------------------------------------------------ Массив O(1) O(N) O(N) O(N) Связный список O(N) O(N) O(1) O(1) Двоичное дерево поиска O(log N) O(log N) O(log N) O(log N) 
 Доступ Поиск Вставка Удаление ------------------------------------------------------------------------ Массив ОХРЕНЕННО НОРМАС НОРМАС НОРМАС Связный список НОРМАС НОРМАС ОХРЕНЕННО ОХРЕНЕННО Двоичное дерево поиска КРУТО КРУТО КРУТО КРУТО

Кроме того, некоторые действия имеют разную «среднюю» производительность и производительность в «самом худшем случае».

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

/*** ===================================================================== ***\ * _.-.. * * ,'9 )\)`-. --. * * `-.| `. * * \, , \) * * `. )._\ (\ * * |// `-,// * * ]|| //" * ** hjw "" "" ** \*** ===================================================================== ***/

Память

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

Фрагмент памяти можно представить так:

Значения: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011. Адреса: 0 1 2 3 4 5 6 7 8 9 .

Если вы задумывались, почему в языках программирования отсчёт начинается с 0 — потому, что так работает память. Чтобы прочитать первый фрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адреса этих фрагментов соответственно равны 0 и 1.

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

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

Абстракции имеют два дополнительных назначения:

— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.

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

/*** ===================================================================== ***\ * * _______________________ * * ()=(_______________________)=() * * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * * | | * * * | ~ ~~~~~~~~~~~~~ | * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * | | * * * |_____________________| * * * * ()=(_______________________)=() * ** ** \*** ===================================================================== ***/

Списки

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

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

Начнём с пустого блока памяти, представленного обычным JavaScript-массивом. Также нам понадобится хранить значение длины списка.

Заметьте, что мы хотим хранить длину отдельно, поскольку в реальности у «памяти» нет значения length, которое можно было бы взять и прочитать.

class List < constructor() < this.memory = []; this.length = 0; >//. >

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

Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»

get(address)

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

  • Push — Добавить значение в конец.
  • Pop — Удалить значение из конца.
  • Unshift — Добавить значение в начало.
  • Shift — Удалить значение из начала.

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

Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»

push(value)

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

Далее, реализуем метод «pop», убирающий элемент из конца нашего списка. Аналогично push, всё, что нужно сделать — убрать значение из последнего адреса. Ну, и уменьшить длину.

Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»

«Push» и «pop» работают с концом списка, и в общем-то являются простыми операциями, поскольку не затрагивают весь остальной список.

Давайте посмотрим, что происходит, когда мы работаем с началом списка, с операциями «unshift» и «shift».

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

[a, b, c, d, e] 0 1 2 3 4 ⬊ ⬊ ⬊ ⬊ ⬊ 1 2 3 4 5 [x, a, b, c, d, e]

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

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

Добавление элемента в начало списка — линейно O(N) — «НОРМАС.»

unshift(value) < // Cохраняем значение, которое хотим добавить в начало. var previous = value; // Проходимся по каждому элементу. for (var address = 0; address < this.length; address++) < // заменяя текущее значение «current» на предыдущее значение «previous», // и сохраняя значение «current» для следующей итерации. var current = this.memory[address]; this.memory[address] = previous; previous = current; >// Добавляем последний элемент на новую позицию в конце списка. this.memory[this.length] = previous; this.length++; > 

Осталось написать функцию сдвига списка в противоположном направлении — shift.

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

[x, a, b, c, d, e] 1 2 3 4 5 ⬋ ⬋ ⬋ ⬋ ⬋ 0 1 2 3 4 [a, b, c, d, e]

Удаление элемента из начала списка — линейно O(N) — «НОРМАС.»

shift() < // Нет элементов — ничего не делаем. if (this.length === 0) return; var value = this.memory[0]; // Проходимся по каждому элементу, кроме последнего for (var address = 0; address < this.length - 1; address++) < // и заменяем его на следующий элемент списка. this.memory[address] = this.memory[address + 1]; >// Удаляем последний элемент, поскольку значение теперь в предыдущем адресе. delete this.memory[this.length - 1]; this.length--; return value; > 

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

Давайте посмотрим на иную структуру данных и её методы по добавлению, доступу и удалению значений без необходимости знать адреса элементов.

/*** ===================================================================== ***\ * ((\ * * ( _ ,-_ \ \ * * ) / \/ \ \ \ \ * * ( /)| \/\ \ \| | .'---------------------'. * * `~()_______)___)\ \ \ \ \ | .' '. * * |)\ ) `' | | | .'-----------------------------'. * * / /, | '. ' * * ejm | | / \ _____________________ / * * \ / | |_) (_| | * * \ / | | | | * * ) / | | | | * ** / / (___) (___) ** \*** ===================================================================== ***/

Хеш-таблицы

Хеш-таблица — неупорядоченная структура данных. Вместо индексов мы работаем с «ключами» и «значениями», вычисляя адрес памяти по ключу.

Смысл в том, что ключи «хешируются» и позволяют эффективно работать с памятью — добавлять, получать, изменять и удалять значения.

var hashTable = new HashTable(); hashTable.set('myKey', 'myValue'); hashTable.get('myKey'); // >> 'myValue' 

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

class HashTable < constructor() < this.memory = []; >// . > 

Чтобы сохранять пары ключ-значение из хеш-таблицы в память, нужно превращать ключи в адреса. Этим занимается операция «хеширования».

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

hashKey("abc") => 96354 hashKey("xyz") => 119193 

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

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

Любая реализация хеш-таблиц сталкивается с этой проблемой.

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

Давайте определим функцию «hashKey».

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

hashKey(key) < var hash = 0; for (var index = 0; index < key.length; index++) < // Ма-а-а-агия. var code = key.charCodeAt(index); hash = ((hash return hash; > 

Теперь определим функцию «get», получающую значение по ключу.

Сложность чтения значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»

get(key) < // Сперва получим адрес по ключу. var address = this.hashKey(key); // Затем просто вернём значение, находящееся по этому адресу. return this.memory[address]; >

Перед тем, как получать данные, неплохо бы их сперва добавить. В этом нам поможет функция «set».

Сложность установки значения в хеш-таблицу — константа O(1) — «ОХРЕНЕННО!!»

set(key, value) < // И вновь начинаем с превращения ключа в адрес. var address = this.hashKey(key); // Затем просто записываем значение по этому адресу. this.memory[address] = value; >

Наконец, нужен способ удалять значения из хеш-таблицы. Сложность удаления значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»

remove(key) < // Как обычно, хешируем ключ, получая адрес. var address = this.hashKey(key); // Удаляем значение, если оно существует. if (this.memory[address]) < delete this.memory[address]; >>

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

  • Организовывают данные, исходя из особенностей их применения
  • Абстрагируют детали реализации
/*** ===================================================================== ***\ * _ . - - -- .. _ * * |||| .-' /```\ `'-_ /| * * |||| ( /`` \___/ ```\ ) | | * * \__/ |`"-//..__ __..\\-"`| | | * * || |`"||. __`````__. ||"`| | | * * || |`"||. __`````__. ||"`| \ | * * || _,.--|`"||. __`````__. ||"`|--.,_ || * * || .'` |`"||. __`````__. ||"`| `'. || * * || '. `/ |. __`````__. | \ .' || * * || `'-..__ `` ````` `` __..-'` || * * `""---. _______. ---""` * ** ** \*** ===================================================================== ***/

Стеки

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

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

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

Нам вновь понадобится JavaScript-массив, но на этот раз он символизирует не память, а список, вроде реализованного выше.

class Stack < constructor() < this.list = []; this.length = 0; >// . >

Нам понадобится реализовать два метода, функционально идентичных методам списка — «push» и «pop».

Push добавляет элементы на верхушку стека.

push(value)

Pop удаляет элементы из верхушки.

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

peek() < // Возвращаем последний элемент, не удаляя его. return this.list[this.length - 1]; >
/*** ===================================================================== ***\ * /:""| ,@@@@@@. * * |: oo|_ ,@@@@@`oo * * C _) @@@@C _) * * ) / "@@@@ '= * * /`\\ ```)/ * * || | | /`\\ * * || | | || | \ * * ||_| | || | / * * \( ) | ||_| | * * |~~~`-`~~~| |))) | * * (_) | | (_) |~~~/ (_) * * | |`"". __ __. ""`| |`"". _|| / __. ""`| | * * | |`"". __`````__. ""`| |`"". __`````__. ""`| | * * | | | ||``` | | ||`|`` | | * * | | |_||__ | | ||_|__ | | * * ,| |, jgs (____)) ,| |, ((;:;:) ,| |, * ** `---` `---` `---` ** \*** ===================================================================== ***/

Очереди

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

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

И вновь мы призываем на помощь JavaScript-массив! В случае с очередью мы опять рассматриваем его как список, а не как память.

class Queue < constructor() < this.list = []; this.length = 0; >// . > 

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

Первым будет «enqueue» — добавление элемента в конец списка.

enqueue(value)

Далее — «dequeue». Элемент удаляется не из конца списка, а из начала.

dequeue() < // Нет элементов — ничего не делаем. if (this.length === 0) return; // Убираем первый элемент методом shift и возвращаем значение. this.length--; return this.list.shift(); >

Аналогично стекам объявим функцию «peek», позволяющую получить значение в начале очереди без его удаления.

peek()

Важно заметить, что, поскольку для реализации очереди использовался список, она наследует линейную производительность метода shift (т.е. O(N) — «НОРМАС.»).

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

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

+- Структура данных -------------------------------------+ | +- Элемент A ------------+ +- Элемент B ------------+ | | | Значение: 1 | | Значение: 2 | | | | Ссылка на: (Элемент B) | | Ссылка на: (Элемент A) | | | +------------------------+ +------------------------+ | +--------------------------------------------------------+ 

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

Сейчас вы поймёте, что я имею ввиду.

/*** ===================================================================== ***\ * * * | RICK ASTLEY'S NEVER GONNA. * * | +-+ * * | +-+ |-| [^] - GIVE YOU UP * * | |^| |-| +-+ [-] - LET YOU DOWN * * | |^| |-| +-+ |*| [/] - RUN AROUND AND DESERT YOU * * | |^| |-| +-+ |\| |*| [\] - MAKE YOU CRY * * | |^| |-| |/| |\| +-+ |*| [.] - SAY GOODBYE * * | |^| |-| |/| |\| |.| |*| [*] - TELL A LIE AND HURT YOU * * | |^| |-| |/| |\| |.| |*| * * +-------------------------------- * ** ** \*** ===================================================================== ***/

Графы

На самом деле граф — совсем не то, о чём вы подумали, увидев ascii-график.

Граф — структура наподобие этой:

У нас есть множество «вершин» (A, B, C, D, . ), связанных линиями.

Эти вершины можно представить вот так:

Node

А весь граф будет выглядеть вот так:

Graph < nodes: [ Node , Node , . ] > 

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

class Graph < constructor() < this.nodes = []; >// . > 

Начнём добавлять значения в граф, создавая вершины без каких-либо линий.

addNode(value) < this.nodes.push(< value: value, lines: [] >); > 

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

Но в нашем случае мы просто переберём все вершины, чтобы найти соответствующую значению. Способ медленный, но работающий.

find(value) < return this.nodes.find(function(node) < return node.value === value; >); > 

Теперь мы можем связать две вершины, проведя «линию» от одной до другой (прим. переводчика: дугу графа).

addLine(startValue, endValue) < // Найдём вершины для каждого из значений. var startNode = this.find(startValue); var endNode = this.find(endValue); // Ругнёмся, если не нашли одной или другой. if (!startNode || !endNode) < throw new Error('Обе вершины должны существовать'); >// В стартовую вершину startNode добавим ссылку на конечную вершину endNode. startNode.lines.push(endNode); > 

Полученный граф можно использовать вот так:

var graph = new Graph(); graph.addNode(1); graph.addNode(2); graph.addLine(1, 2); var two = graph.find(1).lines[0]; 

Кажется, что для такой мелкой задачи сделано слишком много работы, однако это мощный паттерн.

Он часто применяется для поддержания прозрачности в сложных программах. Это достигается оптимизацией взаимосвязей между данными, а не операций над самими данными. Если вы выберете одну вершину в графе, невероятно просто найти связанные с ней элементы.

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

/*** ===================================================================== ***\ * _______________________ * * ()=(_______________________)=() ,-----------------,_ * * | | ," ", * * | ~ ~~~~~~~~~~~~~ | ,' ,---------------, `, * * | ,----------------------------, ,----------- * * | ~ ~~~~~~~~ | | | * * | `----------------------------' `----------- * * | ~ ~~~~~~~~~~~~~ | `, `----------------' ,' * * | | `, ,' * * |_____________________| `------------------' * * ()=(_______________________)=() * ** ** \*** ===================================================================== ***/

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

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

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

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

1 -> 2 -> 3 -> 4 -> 5

Если представить эту структуру в виде JSON, получится нечто такое:

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

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

class LinkedList < constructor() < this.head = null; this.length = 0; >// . > 

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

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

get(position) < // Выведем ошибку, если искомая позиция превосходит число вершин в списке. if (position >= this.length) < throw new Error('Позиция выходит за пределы списка'); >// Начнём с головного элемента списка. var current = this.head; // Пройдём по всем элементам при помощи node.next, // пока не достигнем требуемой позиции. for (var index = 0; index < position; index++) < current = current.next; >// Вернём найденную вершину. return current; > 

Теперь необходим способ добавлять вершины в выбранную позицию.

Создадим метод add, принимающий значение и позицию.

add(value, position) < // Сначала создадим вершину, содержащую значение. var node = < value: value, next: null >; // Нужно обработать частный случай, когда вершина вставляется в начало. // Установим поле «next» в текущий головной элемент и заменим // головной элемент нашей вершиной. if (position === 0) < node.next = this.head; this.head = node; // Если мы добавляем вершину на любую другую позицию, мы должны вставить её // между текущей вершиной current и предыдущей previous. >else < // Сперва найдём предыдущую и текущую вершины. var prev = this.get(position - 1); var current = prev.next; // Затем вставим новую вершину между ними, установив поле «next» // на текущую вершину current, // и поле «next» предыдущей вершины previous — на вставляемую. node.next = current; prev.next = node; >// И увеличим длину. this.length++; > 

Последний метод, который нам понадобится — remove. Найдём вершину по позиции и выкинем её из цепочки.

remove(position) < // Если мы удаляем головной элемент, просто переставим указатель head // на следующую вершину. if (position === 0) < this.head = this.head.next; // Для остальных случаев требуется найти предыдущую вершину и поставить // в ней ссылку на вершину, следующую за текущей. >else < var prev = this.get(position - 1); prev.next = prev.next.next; >// И затем уменьшим длину. this.length--; > 

Две оставшиеся структуры данных относятся к семейству «деревьев».

Как и в жизни, существует множество различных древовидных структур данных.

Прим. переводчика: ну не-е-е-е, я пас…

Binary Trees:
AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree, left child/right sibling tree, order statistic tree, Pagoda,…

B Trees:
B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree,…

Heaps:
Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap,…

Trees:
Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie,…

Multi-way Trees:
Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree,…

Space Partitioning Trees:
Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree, Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree,…

Application-Specific Trees:
Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree,…

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

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

Если вы можете пройти круг по вершинам дерева… что ж, поздравляю, но это не дерево.

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

/*** ===================================================================== ***\ * ccee88oo \ | / * * C8O8O8Q8PoOb o8oo '-.;;;.-, ooooO8O8QOb o8bDbo * * dOB69QO8PdUOpugoO9bD -==;;;;;==-aadOB69QO8PdUOpugoO9bD * * CgggbU8OU qOp qOdoUOdcb .-';;;'-. CgggOU ddqOp qOdoUOdcb * * 6OuU /p u gcoUodpP / | \ jgs ooSec cdac pdadfoof * * \\\// /douUP ' \\\d\\\dp/pddoo * * \\\//// \\ \\//// * * |||/\ \\/// * * |||\/ |||| * * ||||| /||| * ** . //||||\. //|||\\. ** \*** ===================================================================== ***/

Деревья

Начнём с простой древовидной структуры. В ней нет особых правил, и выглядит она примерно так:

Tree < root: < value: 1, children: [< value: 2, children: [. ] >, < value: 3, children: [. ] >] > > 

Дерево должно начинаться с единственного родителя, «корня» дерева.

class Tree < constructor() < this.root = null; >// . > 

Нам нужен способ обходить наше дерево и вызывать определённую функцию в каждой его вершине.

traverse(callback) < // Определим функцию обхода walk, которую можно рекурсивно вызывать // в каждой вершине дерева. function walk(node) < // Сперва вызовем callback на самой вершине. callback(node); // Затем рекурсивно вызовем walk на всех её потомках. node.children.forEach(walk); >// А теперь запустим процесс обхода. walk(this.root); > 

Теперь нужен способ добавлять вершины в дерево.

add(value, parentValue) < var newNode = < value: value, children: [] >; // Если корня не существует, установим в него новую вершину. if (this.root === null) < this.root = newNode; return; >// В остальных случаях переберём внутреннее дерево, найдём вершину // с соответствующим значением parentValue и добавим новую вершину // к его потомкам. this.traverse(function(node) < if (node.value === parentValue) < node.children.push(newNode); >>); > 

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

Однако при наличии дополнительных правил деревья могут выполнять кучу различных задач.

/*** ===================================================================== ***\ * 0 0 1 0 1 0 0 1 0 1 1 1 0 1 ,@@@@@@@@@@@@@@, 0 0 1 0 1 0 0 1 0 1 1 1 0 * * 0 1 0 1 0 1 0 1 1 0 1 1 0 @@` '@@ 0 1 0 1 0 1 1 0 1 0 1 0 * * 1 1 0 0 0 1 0 0 1 1 1 0 @@` 8O8PoOb o8o '@@ 0 0 1 0 0 1 0 0 1 1 1 * * 0 0 1 1 0 1 0 1 0 0 0 @@ dOB69QO8PdUgoO9bD @@ 1 0 1 1 0 1 0 1 0 0 * * ===================== @@ CgbU8OU qOp qOdOdcb @@ 0 1 1 0 1 0 1 0 1 0 * * @@ 6OU /p u gcoUpP @@ 1 0 1 1 0 1 0 0 1 1 * * ===================== @@ \\// /doP @@ 0 1 1 0 0 1 0 0 1 0 * * 1 1 0 0 1 1 0 1 1 0 0 @@ \\// @@ 1 0 1 0 0 1 1 0 1 1 * * 0 1 1 0 1 0 1 1 0 1 1 0 @@, ||| ,@@ 0 1 1 0 1 1 0 0 1 0 1 * * 1 0 1 0 1 1 0 0 1 0 0 1 0 @@, //|\ ,@@ 0 1 0 1 0 1 1 0 0 1 1 0 * ** 1 0 1 0 0 1 1 0 1 0 1 0 1 `@@@@@@@@@@@@@@' 0 1 1 1 0 0 1 0 1 0 1 1 ** \*** ===================================================================== ***/

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

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

Представьте, что у вас есть последовательность чисел:

1 2 3 4 5 6 7

Развернём её в дерево, начинающееся из центра.

4 / \ 2 6 / \ / \ 1 3 5 7 -^--^--^--^--^--^--^- 1 2 3 4 5 6 7
  • Левый — меньше, чем значение вершины-родителя.
  • Правый – больше, чем значение вершины-родителя.

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

(4) 4, двигаемся направо. / \ 2 (6) 


Заметьте, чтобы добраться до 5, потребовалось сделать лишь 3 проверки. А если бы дерево состояло из 1000 элементов, путь был бы таким:

500 -> 250 -> 125 -> 62 -> 31 -> 15 -> 7 -> 3 -> 4 -> 5

Всего 10 проверок на 1000 элементов!

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

Как и в прошлой секции, сперва нужно установить “корень” двоичного дерева поиска.

class BinarySearchTree < constructor() < this.root = null; >// . > 

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

contains(value) < // Начинаем с корня. var current = this.root; // Мы будем продолжать обход, пока есть вершины, которые можно посетить. // Если мы достигнем левой или правой вершин, равных null, цикл закончится. while (current) < // Если значение value больше current.value, двигаемся вправо. if (value >current.value) < current = current.right; // Если значение value меньше current.value, двигаемся влево. >else if (value < current.value) < current = current.left; // Иначе значения должны быть равны и мы возвращаем true. >else < return true; >> // Если мы не нашли ничего, возвращаем false. return false; > 

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

Однако теперь, когда мы доберёмся до левой или правой вершины, равной null,
мы добавим вершину в эту позицию.

add(value) < // Для начала создадим вершину. var node = < value: value, left: null, right: null >; // Частный случай, если не существует корневой вершины — добавим её. if (this.root === null) < this.root = node; return; >// Начнём обход с корня. var current = this.root; // Мы собираемся циклически продолжать работу до тех пор, пока не добавим // наш элемент или не обнаружим, что он уже находится в дереве. while (true) < // Если значение value больше current.value, двигаемся вправо. if (value >current.value) < // Если правая вершина не существует, установим её и закончим обход. if (!current.right) < current.right = node; break; >// Иначе перейдём на правую вершину и продолжим. current = current.right; // Если значение value меньше current.value, двигаемся влево. > else if (value < current.value) < // Если левая вершина не существует, установим её и закончим обход. if (!current.left) < current.left = node; break; >// Иначе перейдём на левую вершину и продолжим. current = current.left; // Если значение ни больше и не меньше, оно должно быть совпадать // с текущим, значит ничего делать не надо. > else < break; >> > 
/*** ===================================================================== ***\ * .''. * * .''. *''* :_\/_: . * * :_\/_: . . *_\/_* : /\ : .'. '. * * .''.: /\ : _\(/_ ':'* /\ * : '..'. -=:o:=- * * :_\/_:'. /)\*''* .|.* '.\'/.'_\(/_'.':'.' * * : /\ : . '*_\/_* | | -= o =- /)\ ' * * * '..' '. ' * /\ * |'| .'/.\'. '._____ * * * __*..* | | : |. |' .---"| * * _* .-' '-. | | .--'| || | _| | * * .-'| _.| | || '-__ | | | || | * * |' | |. | || | | | | || | * * _____________| '-' ' "" '-' '-.' '` |____________ * ** jgs~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ** \*** ===================================================================== ***/

Конец

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

Также можете прочитать другую мою статью, «The Super Tiny Compiler» github.com/thejameskyle/the-super-tiny-compiler

// Экспортируем модули для тестов. module.exports = < List: List, HashTable: HashTable, Stack: Stack, Queue: Queue, Graph: Graph, LinkedList: LinkedList, Tree: Tree, BinarySearchTree: BinarySearchTree >; 

Также эту статью можно прочитать на гитхабе.

Перевод: aalexeev, редактура: iamo0, Чайка Чурсина.

Что такое структуры данных? Определение и типы

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

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

Почему структуры данных имеют значение в разработке программного обеспечения

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

  1. Эффективность. Правильно выбранные структуры данных оптимизируют доступ и обработку данных, что приводит к созданию более быстрого и эффективного программного обеспечения. Правильная структура данных может значительно сократить временную сложность стандартных операций, таких как поиск, вставка и удаление.
  2. Масштабируемость. По мере роста приложений и обработки больших объемов данных эффективные структуры данных становятся еще более важными. Хорошо спроектированная структура данных может поддерживать расширение приложений без серьезного снижения производительности, гарантируя, что программное обеспечение остается отзывчивым и стабильным.
  3. Сопровождение кода. Приложение с организованными структурами данных легче поддерживать, изменять и расширять. Выбор подходящих структур данных упрощает код и способствует улучшению практики кодирования, тем самым улучшая качество программного обеспечения.
  4. Разработка алгоритмов. Поскольку большинство алгоритмов построены на основе одной или нескольких структур данных, их эффективность во многом зависит от базовых структур. Правильная структура данных позволяет лучше реализовать алгоритм и может существенно повлиять на производительность программного обеспечения.

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

Распространенные типы структур данных

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

  1. Массивы. Массив представляет собой линейную структуру данных фиксированного размера, в которой хранятся элементы одного типа данных. Он использует целочисленные индексы для прямого доступа к элементам, обеспечивая быстрый поиск и изменение. Массивы легко реализовать, но их фиксированный размер может привести к нерациональному использованию памяти или проблемам с изменением размера.
  2. Связанные списки. Связанный список — это еще одна линейная структура данных, состоящая из элементов, называемых узлами. Каждый узел хранит элемент данных и ссылку (указатель) на следующий узел. Связанные списки можно легко расширять и сжимать, обеспечивая динамическое распределение памяти, но за счет более медленного доступа к элементам, чем у массивов.
  3. Стеки. Стек — это структура данных «последним пришел — первым обслужен» (LIFO), в которой доступен только верхний элемент. Стеки позволяют выполнять простые операции добавления (push) и удаления (pop), что делает их полезными для управления данными в определенном порядке, например, для управления вызовами функций или функциями отмены и повтора в текстовом редакторе.
  4. Очереди. Очередь — это структура данных «первым пришел — первым обслужен» (FIFO), которая поддерживает добавление элементов в конец (постановка в очередь) и удаление элементов в начало (удаление из очереди). Очереди обычно используются в таких сценариях, как планирование задач или обработка запросов веб-сервера, где элементы обрабатываются в порядке их поступления.
  5. Хэш-таблицы. Хэш-таблица — это структура данных, которая использует хеш-функцию для сопоставления ключей со значениями, обеспечивая эффективные операции поиска, вставки и удаления. Хэш-таблицы особенно полезны в сценариях, требующих быстрого доступа к данным, таких как хранение и извлечение данных в базе данных или реализация кэшей.
  6. Деревья. Дерево — это иерархическая структура данных, состоящая из узлов, соединенных ребрами, с одним корневым узлом и листьями на самом низком уровне. Деревья позволяют эффективно искать, вставлять и удалять элементы, а также моделировать различные структуры реального мира, такие как файловые системы или организационные диаграммы.
  7. Графы. Граф — это нелинейная структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Графики могут моделировать сложные отношения и сети, такие как социальные сети, транспортные системы или веб-страницы и их гиперссылки, что упрощает разработку эффективных алгоритмов поиска пути и других задач оптимизации.

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

Попробуйте no-code платформу AppMaster

AppMaster поможет создать любое веб, мобильное или серверное приложение в 10 раз быстрее и 3 раза дешевле

Реальные применения структур данных

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

Поисковые системы: деревья и графы

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

Базы данных: хэш-таблицы, B-деревья.

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

Алгоритмы маршрутизации: графы, очереди приоритетов

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

Текстовые редакторы: стеки, массивы

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

Обработка изображений: массивы

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

Выбор правильной структуры данных для вашего приложения

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

Тип данных

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

Желаемые операции

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

Требования к производительности

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

Масштабируемость

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

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

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

AppMaster — это мощная no-code платформа, позволяющая визуально создавать серверные, веб- и мобильные приложения. Он упрощает процесс управления структурами данных за счет автоматизации основных задач, связанных с организацией, обработкой и хранением данных. Более того, платформа поддерживает бесшовную интеграцию с различными системами хранения данных, включая базы данных, совместимые с Postgresql , что позволяет работать даже с самыми сложными приложениями.

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

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

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

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

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

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

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

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

Как AppMaster может помочь со структурами данных?

AppMaster — это мощная платформа no-code , которая позволяет визуально создавать серверные, веб- и мобильные приложения. Он эффективно управляет структурами данных во время создания приложений, заботясь об организации, обработке и хранении данных без написания сложного кода.

Каковы распространенные типы структур данных?

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

Как выбрать правильную структуру данных для моего приложения?

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

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

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