Почему мы используем структуры данных?(когда динамическое распределение не требуется)

Question

Я почти уверен, что это глупый вопрос новичка, но я не знал его, поэтому мне пришлось спросить ...

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

Я имею в виду: не было бы быстрее, если бы мы сохранили одну переменную для одного объекта? Разве это не ускорит время доступа? Например: BST, возможно, должен сначала пройти через несколько указателей, прежде чем он доберется до фактических данных.

За исключением случаев, когда требуется динамическое распределение, есть ли причина их использовать?

Например: использование связанного списка / BST / std :: vector в ситуации, когда можно использовать простой (не динамический) массив.

Answer 1

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

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

Простая аналогия может помочь понять. Вы можете, например, организовать все ваши важные документы, поместив каждый из них в отдельный шкаф для документов. Если бы вы сделали это, вам пришлось бы запомнить (т.е. жестко закодировать) шкаф, в котором можно найти каждый предмет, чтобы эффективно их использовать. Кроме того, вы можете хранить каждый из них в одном и том же шкафу для хранения документов (например, в общем массиве). Это лучше в том, что они все в одном месте, но все же не оптимально, так как вы должны искать их все каждый раз, когда хотите их найти. Еще лучше было бы организовать их по темам, помещая одинаковые предметы в одну и ту же файловую папку (отдельные массивы, разные структуры). Таким образом, вы можете найти папку с файлами для правильной темы, а затем найти в ней искомый элемент. В зависимости от ваших потребностей вы можете использовать различные методы регистрации (структуры данных / алгоритмы), чтобы лучше организовать информацию для ее предполагаемого использования.

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

Answer 2

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

Как это можно сделать, не требуя от программистов массового (и нетривиального) перезаписи тонн кода, как только количество разрешенных элементов изменяется? Даже когда вам нужно исправить размеры структуры данных во время компиляции (например, массивы в C), вы можете использовать константу. Затем для изменения этого размера достаточно изменить одну константу и перекомпилировать (если код был написан с учетом этого). При вашем подходе нам придется печатать сотни или даже тысячи строк каждый раз, когда изменяется размер. Не говоря уже о том, что весь этот код будет невероятно трудным для чтения, записи, обслуживания и проверки. Старый трюизм «больше строк кода = больше места для ошибок» в такой настройке занимал до одиннадцати.

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

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

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

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

Answer 3

Основным преимуществом структур данных, на мой взгляд, является то, что вы их реляционно группируете. Например, вместо 10 отдельных переменных класса MyClass вы можете иметь структуру данных, которая группирует их все. Эта группировка позволяет выполнять определенные операции , поскольку они структурированы вместе.

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

И последнее, но не менее важное: что бы вы предпочли делать?

string string1 = "string1";
string string2 = "string2";
string string3 = "string3";
string string4 = "string4";
string string5 = "string5";

Console.WriteLine(string1);
Console.WriteLine(string2);
Console.WriteLine(string3);
Console.WriteLine(string4);
Console.WriteLine(string5);

Или ...

List<string> myStringList = new List<string>() { "string1", "string2", "string3", "string4", "string5" };

foreach (string s in myStringList)
    Console.WriteLine(s);