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

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

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

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

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

Массивы (Arrays)

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

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

DS
Специализация Data Science
Идет набор в группу 12 500₽ в месяц

Стек (Stack)

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

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

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

Очередь (Queue)

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

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

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

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

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

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

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

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

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

Курс по Machine Learning
Идет набор в группу 3 800₽ в месяц

 Дерево (Tree)

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

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

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

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

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

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

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

Курс по нейронным сетям
Идет набор в группу 4 200₽ в месяц

Графы (Graphs)

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

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

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

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

 Хеш-таблицы

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

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

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

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

Текст: Помогаев Дмитрий

Поделиться:
Опубликовано в рубрике Наука о данных (Data Science)Tagged ,

SkillFactory.Рассылка