Различия между Статическими и Динамическими структурами данных
Каковы основные отличия, преимущества и недостатки между статическими и динамическими структурами данных?
Под которыми категориями падают наиболее распространенные структуры данных?
Как я мог знать в который ситуация использовать каждого?
3 ответа
Начнем с упрощения:
Существует всего несколько основных видов структур данных: массивы, списки и деревья. Все остальное можно составить, используя различные типы этих двух структур (например, хэш-таблица может быть реализована с помощью массива для хэш-значений и одного списка для каждого хэш-значения для обработки коллизий).
Из этих структур массивы являются статическими (т.е. их объем памяти не меняется со временем по мере выполнения операций над ними), а все остальное - динамическими (т.е. в общем случае объем памяти меняется).
Различия между этими двумя видами структур можно вывести из вышесказанного:
- Статические требуют, чтобы максимальный размер был известен заранее, тогда как динамические могут адаптироваться на лету
- Статические не перераспределяют память независимо от того, что происходит, поэтому вы можете иметь гарантированные требования к памяти
Есть и другие различия, которые, однако, вступают в игру, только если ваши данные могут быть отсортированы. Я не могу привести обширный список, поскольку существует множество динамических структур данных, которые демонстрируют различные характеристики производительности для различных операций ("добавить", "удалить", "найти"), и поэтому их нельзя поместить под одну крышу.
Очень заметная разница заключается в том, что сортированные массивы требуют перемещения (возможно, большого количества) материала в памяти для любой операции, кроме "найти", в то время как динамические структуры обычно выполняют меньше работы.
Итак, подведем итоги:
- Если вам нужна гарантия максимального использования памяти, у вас нет другого выбора, кроме массива.
- Если у вас есть жесткий верхний предел для размера данных, подумайте об использовании массива. Массивы могут хорошо подходить для задач, требующих в основном операций добавления/удаления (сохраняйте массив несортированным) и для задач, требующих в основном операций поиска (сохраняйте массив отсортированным), но не для обеих одновременно.
- Если у вас нет жесткого верхнего предела, или если вам требуется, чтобы все операции add/remove/find были быстрыми, используйте соответствующий тип динамической структуры.
Edit: Я не упомянул графы, другой вид динамической структуры данных, который, вероятно, не может быть составлен из более простых частей (по определению, дерево имеет ровно одну ссылку, идущую "в" любой узел, кроме корня, в то время как графы могут иметь более одной). Однако графы нельзя сравнивать с другими структурами в сценарии "что лучше использовать", поскольку граф либо нужен, либо нет (другие структуры могут демонстрировать разную производительность, но в конечном итоге все они поддерживают один и тот же набор операций).
Всегда наоборот, если вы выбираете статическую структуру, то теряете память, а в случае динамической - снижается производительность. Лучшая конструкция будет эффективно использовать структуры данных, идеального ответа не существует.
Статические структуры данных (SDS) имеют фиксированный размер (например, массивы), объем памяти, однажды выделенной для них, не может измениться во время выполнения, тогда как динамические структуры данных ( DDS) (например, связанные списки) имеют гибкий размер, они могут увеличиваться или уменьшаться по мере необходимости для хранения данных.
SDS - это линейные структуры данных, которые обеспечивают быстрый доступ к хранящимся в них элементам, но операции вставки / удаления дороги по сравнению с DDS, где доступ к элементам медленнее, а вставка / удаление - быстрее.
Большинство DS являются динамическими DS.
В случае, если пространство SDS выделяется до фактической вставки данных, поэтому пространство может быть потрачено впустую или может быть недостаточным несколько раз, поэтому их следует использовать только в том случае, если точный объем данных, которые должны быть вставлены, известен заранее, если это чтобы быть известным во время выполнения, следует использовать DDS.