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

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

Понимание ваших данных

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

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

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

instagram viewer

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

Рассмотрим операции, которые необходимо выполнить над данными

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

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

Оцените окружающую среду

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

При оценке своего текущего состояния учитывайте следующие факторы:

  1. Вычислительная мощность: выберите структуры данных для ваших приложений, которые хорошо работают на ПК с небольшой вычислительной мощностью при работе на платформе. Например, более простые структуры данных, такие как массивы, могут быть более подходящими, чем деревья или графы.
  2. параллелизм: вам следует выбрать потокобезопасную структуру данных, которая может обрабатывать одновременный доступ без повреждения данных; если ваше приложение работает в параллельной среде, где несколько потоков или процессов одновременно обращаются к структуре данных. В этом случае неблокирующие структуры данных, такие как ConcurrentLinkedQueue и ConcurrentHashMap может быть более подходящим, чем традиционные, такие как ArrayListand HashMap.
  3. Сетевая задержка: если вашему приложению требуется передача данных по сети, вы должны учитывать задержку в сети при выборе наилучшей структуры данных. В таких ситуациях использование структуры данных, которая ограничивает сетевые вызовы или уменьшает объем передаваемых данных, может помочь улучшить выполнение.

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

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

  1. Массивы: это простая и эффективная структура данных, которая может содержать серию элементов фиксированного размера одного и того же типа данных. Чтобы они работали правильно, им нужен быстрый прямой доступ к определенным объектам через индекс.
  2. Связанные списки: связанные списки состоят из узлов, которые содержат элемент и ссылку на следующий узел и/или предыдущий узел. Благодаря своей эффективности связанные списки лучше всего подходят для ситуаций, требующих частой вставки или удаления элементов. Однако доступ к отдельным элементам по индексу в связанных списках происходит медленнее по сравнению с массивами.
  3. Очереди и стеки: стеки придерживаются правила «последним пришел – первым вышел» (LIFO), согласно которому последний вставленный элемент удаляется первым. Очереди регулируются по принципу «первым пришел – первым обслужен» (FIFO). где первый добавленный элемент также является первым удаленным.
  4. Хэш-таблицы: хеш-таблицы — это форма структуры данных, которая содержит пары ключ-значение. Лучшее решение — использовать хеш-таблицы, когда количество компонентов непредсказуемо, и нужен быстрый доступ к значениям по ключу.
  5. Деревья: деревья — это иерархические структуры данных, которые могут хранить группу элементов в иерархии. Лучшее использование для бинарные деревья поиска находятся в иерархических структурах данных, где отношения между элементами данных могут представлять собой древовидную структуру.

Выбор правильной структуры данных

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

  1. Сложность времени: производительность вашего приложения может существенно зависеть от временной сложности вашей структуры данных. Если ваше приложение требует частых операций поиска или извлечения, используйте структуру данных с уменьшенной временной сложностью, например хеш-таблицу.
  2. Космическая сложность: Еще одним важным фактором является пространственная сложность структуры данных. Если ваше приложение интенсивно использует память, выберите структуру данных с меньшей пространственной сложностью, например массив. Если пространство не имеет значения, вы можете использовать структуру данных с большей пространственной сложностью, например дерево.
  3. Читать по сравнению с Операции записи: если ваше приложение использует много операций записи, выберите структуру данных с более быстрой производительностью вставки, например хеш-таблицу. Если ваше приложение требует много операций чтения, выберите структуру данных с более высокой скоростью поиска, например двоичное дерево поиска.
  4. Тип данных: данные, с которыми вы имеете дело, также могут повлиять на выбранную вами структуру данных. Например, вы можете использовать древовидную структуру данных, если ваши данные иерархичны. Если у вас есть простые данные, к которым нужно обращаться случайным образом, выбор структуры данных на основе массива может быть вашим лучшим вариантом.
  5. Доступные библиотеки: рассмотрите библиотеки, которые легко доступны для рассматриваемой вами структуры данных. Было бы проще выполнять и поддерживать, если бы ваш язык программирования имел встроенные библиотеки, доступные для определенной структуры данных.

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

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

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

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

сортУзел:
деф__в этом__(я, ценность):
 самостоятельная ценность = ценность
 self.left_child = Никто
 self.right_child = Никто


сортДвоичныйПоискДерево:


деф__в этом__(себя):
 self.root = Никто
дефвставлять(я, ценность):


если self.root являетсяНикто:
 self.root = узел (значение)


еще:
 self._insert (значение, self.root) 
деф_вставлять(я, значение, текущий_узел):


если значение < текущий_узел.значение:
если current_node.left_child являетсяНикто:
 current_node.left_child = Узел (значение)


еще:
 self._insert (значение, current_node.left_child)
Элиф значение > current_node.value:
если current_node.right_child являетсяНикто:
 current_node.right_child = Узел (значение)
еще:
 self._insert (значение, current_node.right_child)


еще:
 Распечатать("Значение уже существует в дереве.")
дефпоиск(я, ценность):
если self.root являетсянетНикто:
возвращаться self._search (значение, self.root)


еще:
возвращатьсяЛОЖЬ
деф_поиск(я, значение, текущий_узел):


если значение == текущий_узел.значение:
возвращатьсяИстинный


Элиф значение < current_node.value и current_node.left_child являетсянетНикто:
возвращаться self._search (значение, current_node.left_child)


Элиф значение > current_node.value и current_node.right_child являетсянетНикто:
возвращаться self._search (значение, current_node.right_child)
еще:
возвращатьсяЛОЖЬ

В этой реализации вы создаете два класса: ДвоичныйПоискДерево класс, управляющий операциями вставки и поиска, и Узел класс, который символизирует узел в двоичном дереве поиска.

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

Выберите оптимальную структуру данных

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

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

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