123

Зачем нужны структуры данных и алгоритмы

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

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

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

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

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

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

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

Как используются структуры данных?

Структуры данных выполняют для нас четыре основные функции:

ввод информации

Обработка информации

Сохранение информации

Извлечение информации

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

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

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

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

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

Какую структуру данных выбрать?

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

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

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

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

Алгоритмы

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

Алгоритмы сортировки

алгоритмы поиска

Алгоритм "разделяй и властвуй