Вы не можете говорить об алгоритмах, не упоминая о важности структур данных.
Выбор различных структур данных может повлиять на производительность алгоритма. В зависимости от вашего выбора правильный выбор может привести к большей эффективности. Кроме того, структуры данных являются одной из основополагающих тем компьютерных наук, поэтому важно закрепить прочные знания по этому предмету и тому, как их можно применять в повседневной жизни в качестве инженера-программиста.
В этой статье мы сосредоточимся на том, как структуры данных влияют на алгоритмы с точки зрения производительности выполнения, и на некоторых рекомендациях по их выбору.
Назначение структур данных
Они служат абстракциями, которые позволяют нам организовывать данные для хранения, извлечения и использования всякий раз, когда они необходимы. Структура данных помогает нам логически обрабатывать такие данные. Структуры данных определяют, как данные хранятся и доступны в памяти, а также как они могут быть обработаны.
Запуск алгоритма включает в себя хранение и манипулирование данными, для этого потребуется выполнить определенное количество операций с его использованием.
Некоторые из наиболее распространенных операций включают в себя:
- Поиск
- Доступ
- Вставлять
- Удалить
В каждой структуре данных такие операции будут выполняться с определенной стоимостью, которая обычно выражается в терминах нотации big-O.
Вы можете обратиться к этой статье из Free Code Camp для получения более подробной информации о самой нотации. Таким образом, это соглашение для измерения производительности алгоритмов или операций в зависимости от их входных данных.
Существуют основные типы структур данных, которые обычно доступны во многих языках программирования, таких как целые числа, числа с плавающей запятой, строки и логические значения.
Они являются строительными блоками более сложных структур, таких как очередь, стек, массив, связанный список и хеш-таблица.
Для получения подробной информации о затратах на сложность, связанных с общими структурами данных, вы можете обратиться к Шпаргалке Big-O, которая доступна здесь.
Как выбрать правильную структуру данных
Важно констатировать, что ни одна структура данных не может служить оптимальным решением для всех проблем. Имея это в виду, чтобы выбрать лучшую структуру данных для решения конкретной проблемы, мы должны учитывать, какие операции мы собираемся выполнять и как часто они будут выполняться. Затем нам нужно выбрать структуру данных, которая обеспечивает наилучший компромисс между производительностью и задачами, которые мы должны выполнить.
Попробуем понять это понятие на конкретном примере.
Алгоритм кратчайшего пути
Представьте, что вы ищете на Картах Google лучший способ добраться до местного ресторана из дома.
Прежде всего, нам нужен способ представления карты города, чтобы мы могли обрабатывать ее в нашем алгоритме. Один из возможных способов — представить его в виде графа.
Представление графика
Граф представляет собой структуру, состоящую из узлов (также называемых вершинами), связанных друг с другом ребрами (связями).
Мы можем определить путь как последовательность последовательных дуг, соединяющих один узел с другим. Кроме того, пересечение каждого ребра обычно требует определенных затрат, в примере алгоритма поиска кратчайшего пути мы можем думать об этом как о представлении расстояния.
Это был пример графика без направлений. У нас также могут быть ориентированные графы, где отношения между узлами будут представлены стрелками, а не простыми линиями.
Например, расстояние между узлами C и E будет:
C -> D(Cost 1) + D -> E(Cost 4) Cost 5 in total.
Алгоритмы Дейкстры
Теперь, когда у нас есть абстракция карты. Мы можем выбрать алгоритм для решения задачи о минимальном расстоянии. В этом примере мы увидим влияние выбора структуры данных на алгоритмы Дейкстры.
В двух словах, он выполняет послойный обход графа, начиная с исходного узла. По мере продолжения он сохраняет запись, содержащую самые короткие пути, встречавшиеся до сих пор, для каждого узла, найденного на этом пути. Запись кратчайшего пути обновляется всякий раз, когда мы находим лучшую альтернативу существующему пути.
Алгоритм:
- Объявите список узлов для посещения (обычно известный как граница), начиная с исходного узла в нем.
- Мы должны назначить расстояние каждому узлу в графе от начала координат, так как мы только запускаем алгоритм, мы можем считать такие расстояния бесконечными.
- Начните перебирать список узлов, которые нужно посетить:
а. Извлеките первый узел из границы
б. Получить соседей по узлу.
в. Добавьте соседей, которые не были посещены, в конец списка frontier.
д. Вычислите расстояние между узлом отправления и узлом, посещаемым на текущей итерации.
е. Если вычисленное расстояние меньше уже найденного, обновите его.
Для границы нам нужна структура данных, позволяющая легко добавлять данные в конец и удалять ее первый элемент. Мы собираемся сравнить производительность трех структур данных:
- Множество
- Двоичная куча
- Очередь
Реализация массива
В первом испытании мы собираемся использовать массив, представленный в виде списка Python, он имеет следующие рабочие характеристики:
Append: O(1) Extract 1st element: O(n)
Вот реализация на Python:
Мы представляем ввод графика в виде словаря Python (хеш-таблица), где каждый ключ соответствует узлу, а каждое значение — другому словарю с соседями узла:
{
'A': {'B': 2, 'C': 5},
'B': {'F': 1},
'C': {'D': 1},
'D': {'E': 4},
'E': {'F': 3},
'F': {'A': 3, 'D': 2},
}
Анализируя временную сложность вышеприведенной реализации, мы можем выделить, в первую очередь, следующие шаги:
- Инициализация алгоритма выполняется в постоянное время
- Цикл while, который перебирает все узлы графа: O (узлы)
- Получить 1-й элемент списка: O (извлечение).
- Цикл for, который перебирает все ребра графа: всего O(Edges).
- Добавить сложность: O (Добавить).
В целом, наша реализация дает следующую сложность:
O(Nodes.Extraction + Edges.Append)
Используя список Python, мы имеем:
O(Extraction) = O(Nodes) at worst O(Append) = O(1)
Окончательная сложность будет:
O(Nodes² + Edges)
Реализация двоичной кучи
Обратите внимание, что выбор структуры данных массива оказывает определенное влияние на производительность, учитывая, что операция по извлечению 1-го элемента осуществляется за счет:
O(Nodes)
Двоичная куча, по-видимому, обеспечит лучший компромисс сложности:
Append: O(log n) Extract 1st element: O(log n)
Мы можем изменить базовую реализацию границы, изменив функции Append и Extract:
Новая сложность соответствует:
O(log Nodes.(Nodes + Edges))
Это действительно лучше?
Это зависит от количества ребер, которые у нас есть на графе, для фиксированного числа 10 узлов:
Производительность при использовании бинарной кучи лучше только для количества ребер меньше 30.
Реализация очереди
Мы все еще можем попытаться улучшить эту производительность, используя альтернативную структуру данных, Очередь может быть лучшим выбором в этом случае, поскольку она имеет:
Append: O(1) Extract: O(1)
Обе операции могут быть выполнены в постоянное время! Это, безусловно, улучшит нашу производительность:
Такой выбор приведет к следующей сложности:
O(Nodes + Edges)
На изображении выше показано, что очередь обеспечивает наилучшую производительность для алгоритма кратчайшего расстояния. Независимо от количества ребер графа.
Заключение
В этой статье мы увидели влияние структуры данных на выполнение алгоритма, вот основные выводы:
- Ни одна структура данных не может быть использована для решения всех проблем.
- Чтобы сделать наилучший выбор, мы должны учитывать, как структура данных будет использоваться и как часто.
- Постарайтесь выбрать тот, который имеет наименьшие затраты на операции, выполняемые чаще всего.
- Сравните разные подходы! Может быть, это не так очевидно, чтобы найти, какой из них подойдет лучше всего.
Спасибо, что дошли до конца! Если эти идеи были полезны, рассмотрите возможность подписаться на меня в Medium, чтобы получать больше историй, подобных этой!
Бит: создавайте лучшие библиотеки компонентов пользовательского интерфейса
Скажи привет Bit. Это инструмент №1 для разработки приложений на основе компонентов.
С помощью Bit вы можете создать любую часть своего приложения в виде «компонента», который можно компоновать и использовать повторно. Вы и ваша команда можете совместно использовать набор компонентов для более быстрой и последовательной совместной разработки большего количества приложений.
- Создавайте и компонуйте «строительные блоки приложения»: элементы пользовательского интерфейса, полные функции, страницы, приложения, бессерверные или микросервисы. С любым стеком JS.
- С легкостью делитесь и повторно используйте компоненты в команде.
- Быстро обновляйте компоненты в разных проектах.
- Делайте сложные вещи простыми: Монорепо, дизайн-системы и микрофронтенды.
Попробуйте Bit бесплатно и с открытым исходным кодом→
