Npk18.ru

Обучение новым специальностям
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Основные структуры данных программирование

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

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

В 1976 году швейцарец Никлаус Вирт опубликовал книгу «Алгоритмы и структуры данных». Несмотря на то, что после публикации этой книги уже прошло более 40 лет, работа Вирта «Алгоритмы и структуры данных» до сих чрезвычайно актуальна. Это обусловлено тем, что любой разработчик ПО должен прекрасно теоретические основы структур данных. Косвенно это подтверждается тем, что практически на любом ИТ-собеседовании возникает вопрос на данную тематику.

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

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

Назначение структур данных

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

Самые востребованные структуры данных

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

  • стек;
  • массив;
  • очередь;
  • связный список;
  • дерево;
  • граф;
  • префиксное дерево;
  • хеш-таблица.

Массивы

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

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

Выше указан одномерный массив, но также существует его многомерный аналог. Простыми словами его можно назвать массивы массивов.

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

  • вставки;
  • извлечения нужного элемента по индексу;
  • удаления;
  • определения количества элементов в массиве.

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

  • Как найти минимальный элемент?
  • Как объединить 2 отсортированных массива?
  • Как поменять местами положительные и отрицательные значения?

Стеки

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

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

Для понимания работы стека стоит привести самый тривиальный пример. Предположим, на столе одна на одной лежит куча тетрадок. Чтобы взять тетрадку из середины, необходимо удалить тетрадки, которые лежат сверху. Таким образом работаем принцип «последним пришел – первым ушел. В среде разработчиков этот принцип называется LIFO (Last In First Out).

Ниже приведен пример стека.

Элемент со значением «3» находится в самом верху. Следовательно, он будет удален первым.

Если говорить об операциях со стеками, то прежде всего нужно отметить:

  • вставку элемента в топ;
  • извлечение и последующее удаление верхнего элемента;
  • проверку на пустоту стека;
  • извлечение первого элемента.

На ИТ-собеседованиях программисту стоит быть готовым к таким вопросам:

  • Как отсортировать стек?
  • Как проверить соответствие скобок в выражении?

Очереди

Очередь – линейная структура данных, хранящая элементы в определенной последовательности. В очереди используется принцип «первым пришел – первым ушел» (FIFO).

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

Ниже приведен пример очереди, состоящей из 4 элементов.

В этом примере элемент со значением «1» находится в начале очереди. Следовательно, именно этот элемент первым выйдет из очереди.

К основным действиям с queue стоит отнести:

  • вставку в конец;
  • удаление первого элемента;
  • проверку на пустоту очереди;
  • извлечение первого элемента.

На собеседовании разработчика могут попросить:

  • создать стек посредством очереди;
  • сгенерировать двоичные числа посредством очереди.

Связный список

Создание структуры базы данных также предусматривает использование связных списков. Эта структура очень схожа с массивом. Но все-таки она отличается:

  • организацией;
  • принципом распределения памяти;
  • принцип выполнения операций Insert и Delete.

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

Главной задачей связных списков является систем хранения файлов. Ниже приведен пример этой структуры:

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

  • вставка в начало или конец;
  • удаление первого или выбранного элемента;
  • поиск определенного элемента;
  • проверка на пустоту списка.

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

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

Графы

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

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

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

  • реализация поиска;
  • определение количества ребер;
  • проверка на то является ли граф деревом.

Дерево

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

Именно эта структура используется для создания интеллектуальных машин.

Ниже приведен пример простого дерева:

Стоит добавить, что в программирование существует несколько видов деревьев:

  • N-арное;
  • сбалансированное;
  • бинарное;
  • AVL;
  • красно-черное;
  • 2-3;
  • бинарное дерево поиска.

К наиболее часто задаваемым вопросам по деревьям стоит отнести:

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

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

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

Ниже приведен пример префиксного дерева.

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

На ИТ-собеседованиях разработчику могут задать такие задания, связанные с префиксными деревьями:

  • создание словаря Т9;
  • определение общего количества элементов;
  • сортировка массива.

Хэш-таблица

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

Производительность хэш-таблиц зависит от следующих нюансов:

  • хеширования;
  • размера;
  • способа обработки коллекций.

Ниже приведен пример, в котором хэш отображается в массиве:

Читать еще:  Программирование андроид с нуля

На ИТ-собеседовании разработчику могут быть заданы такие задания:

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

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

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

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

«Алгоритмы + структуры данных = программы». Это — название книги Никлауса Вирта, знаменитого швейцарского специалиста по программированию, автора языков Паскаль , Модула-2, Оберон. С именем Вирта связано развитие структурного подхода к программированию. Н.Вирт известен также как блестящий педагог и автор классических учебников.

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

Общее понятие структуры данных

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

Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс , сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java .

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

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

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

Основные структуры данных программирование

1. Какие бывают данные и их структуры?

2. Как задаются структуры данных?

… Лучше, чтобы в 100 функциях

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

чем в 10 функциях — 10 структур

А. Дж. Перлис

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

Будем исходить из того представления, что структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных или логически связанных данных в вычислительной технике (https://ru.wikipedia.org/wiki/Структура_данных). Она формируется с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.

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

В языке Си различают следующие категории типов данных : базовые (или простые, основные, стандартные) типы данных и производные (или сложные, составные) типы данных. Основные типы данных представлены на рис. 3.1.

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

Рисунок 3.1 — Основные типы данных, применяемые в программировании

Указание типа данных четко определяет:

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

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

  • char — размер 1 байт. Всегда! Это нужно запомнить.
  • short — размер 2 байта
  • int — размер 4 байта
  • long — размер 4 байта
  • long long — размер 8 байт.

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


Список.


Двунаправленный список.

Рисунок 3.4 – Структуры данных «Однонаправленный и двунаправленный список»

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

Рисунок 3.5 – Структура данных «Связанный список»

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

struct spis *next; >; // Указатель на структуру

Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.

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

3.2.3 Стек

Стек – это динамическая линейная структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in first out, «последним пришёл — первым вышел»).

Читать еще:  Программирование http для начинающих

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Пример задания стека :

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek). При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным. При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).

Рисунок 3.6 – Структура данных «стек»

Рисунок 3.7 — Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

3.2.4 Очередь

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

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

Рисунок 3.8 – Структура данных «Очередь»

Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от «store»— «сохранять», «retrieve» — «получать»). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение.

3.2.5 Дек

Дек – структура данных одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов структур данных.

Рисунок 3.9 – Структура данных «дек»

3.2.6 Хэш-таблица

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

Рисунок 3.10 – Структура данных «хэш – таблица»

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

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

Рисунок 3.11 — Телефонная книга на примере хэш-таблицы

3.2.7 Иерархические структуры данных

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

Деревья

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

Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева. Отдельно выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня): прямой или префиксный <узел, левое поддерево, правое поддерево>; обратный или постфиксный <левое поддерево, правое поддерево, узел>; симметричный или инфиксный
<левое поддерево, узел, правое поддерево>.

Пример представления дерева:

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


Рисунок 3.12 – Структура данных «дерево»

Иерархический список

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


Рисунок 3.13 – Структура данных «Иерархический список»

Примеры применения структур данных

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

Пример 3.2. Пример создания и просмотра односвязного списка (http://c.guti.ru/dstruktury.asp ).

Пример 3.3. Пример реализации структуры данных «стек».

Основные типы структур данных: порядок на рабочем столе

Если вы захотите устроиться на должность программного инженера, разработчика или даже junior data scientist, на интервью вам наверняка предложат задачи по структурам данных. Так или иначе с этим понятием связаны абсолютно все аспекты программирования, более того — data structures помогают выполнять великое множество задач в повседневной жизни.

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

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

Далее мы расскажем об основных структурах и возможностях их применения в разработке. Эти знания будут полезны любому, кого интересуют вакансии в области Data Science.

Массивы (Arrays)

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

Читать еще:  Где научиться программированию

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

Стек (Stack)

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

Понимает учитель или нет, но такая проверка сочинений напоминает работу со стеком данных. Правило обращения к информации, по которому первой освобождается последняя ячейка, называется LIFO (Last-In-First-Out, «последний зашёл — первый вышел»).

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

Очередь (Queue)

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

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

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

Связный список (Linked List)

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

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

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

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

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

Дерево (Tree)

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

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

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

Префиксное дерево (Trie)

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

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

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

Графы (Graphs)

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

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

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

Читайте в блоге: В чем разница между Data Scientist и Data Engineer?

Читайте также

Хеш-таблицы

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

Производительность этой структуры данных зависит от хеш-функции, размера таблицы и эффективности борьбы с так называемыми коллизиями. Так называется ситуация, в которой два объекта получают одинаковый ключ. Фактически хеш-функция представляет собой вычислительную операцию. Коллизию можно сравнить с совпадением значений x в 2*6=x и 3*4=х. С этим явлением также связан известный парадокс, согласно которому в любой группе из более чем 23 участников, скорее всего, будут двое с совпадающим днём рождения (разумеется, в разные годы).

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

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

Ссылка на основную публикацию
Adblock
detector