Различия между статическими и динамическими структурами данных

Question

Каковы основные различия, преимущества и недостатки статических и динамических структур данных?

К каким категориям относятся наиболее распространенные структуры данных?

Как я мог узнать, в какой ситуации использовать каждый?

Answer 1

Для начала с упрощением:

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

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

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

• Статика требует, чтобы максимальный размер был известен заранее, в то время как динамический может адаптироваться на лету
• Static не перераспределяет память, несмотря на то, что вы можете иметь гарантированные требования к памяти

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

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

Итак, резюмируем:

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

Редактировать: Я не упомянул графы, другой вид динамической структуры данных, которая, возможно, не может быть составлена ​​из более простых частей (по определению, дерево имеет ровно одну ссылку, идущую "в" любой узел, кроме корня в то время как графики могут иметь более одного). Тем не менее, графы не могут действительно сравниваться с другими структурами в сценарии «что было бы лучше использовать», потому что вы либо должны использовать граф, либо нет (другие структуры могут демонстрировать разную производительность, но в итоге все они поддерживают тот же набор операций).

Answer 2

Статические структуры данных (SDS) имеют фиксированный размер (например, массивы), объем выделенной им памяти не может изменяться во время выполнения, тогда как динамические структуры данных (DDS) (например, связанные списки) имеют гибкий размер, они могут увеличиваться или увеличиваться. сжиматься по мере необходимости, чтобы содержать данные для хранения.

SDS - это линейные структуры данных, которые обеспечивают быстрый доступ к элементам, хранящимся в них, но операции вставки / удаления стоят дороже по сравнению с DDS, где доступ к элементам медленнее, но вставка / удаление быстрее.

Большинство DS являются динамическими DS.

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

Answer 3

Простые советы

Динамические структуры данных имеют следующие характеристики:

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

Статические структуры данных имеют следующие характеристики:

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

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

Answer 4

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