Всем привет! Сегодня статья, не связанная с Revit. Поговорим о структурах данных, которые наиболее часто используются в языке C#.
Дисклеймер: статья написана в основном для начинающих программистов под Revit на основе моего опыта. Если вы лучше меня знаете, что всё на самом деле не так или не совсем так, то делитесь подробностями в комментарии, или оставляйте там ссылки на свои блоги. При кажущейся простоте, тема сложная, и осветить прям все-все аспекты довольно тяжело.
Введение
Когда я начинал программировать, я сначала немного изучил Python, а потом начал переходить на C#. Одна из вещей, которая меня довольно сильно смущала: почему в питоне только один тип списков, который легко увеличивается в размере, а в C# имеющий похожий синтаксис массив не меняется, да и вообще зачем все эти ICollection, IList, List<T>, Array и так далее. За Python, конечно, не поясню, а вот про C# расскажу.
Массивы
Это самая база языка. Большинство структур данных содержат массив под капотом, поэтому хорошей практикой является использование массивов там, где не требуется функционал других структур.
Массив в C# представляет собой заранее выделенный фрагмент памяти размера mN, где N — размер массива, а m — объём памяти для одного элемента. Благодаря этому мы имеем очень быстрый доступ к элементам массива по индексу — массив легко вычисляет адрес памяти, где лежит нужный элемент. Так же мы не можем просто так взять и увеличить размер массива — ведь после массива в памяти может лежать что угодно, и мы не можем просто так взять и переписать эти данные.
Обычно с массивом работают через индексы или в цикле foreach:
var arr = new int[10]; // объявили массив из 10 int
for (var i =0; i< arr.Length; i++)
{
arr[i] = i; //записали значения в массив
}
Или пример с Ревитом:
var arr = new FilteredElementCollector(Context.Document)
.OfClass(typeof(Wall))
.ToArray();
foreach (var wall in arr)
{
// do something
}
Во втором примере я перевожу элементы в массив, а не в список, потому что мне не нужен функционал списка, связанный с его переменным размером.
Списки
Списки — самая популярная структура данных в C#. По своей сути являются массивами переменного размера.
По факту, внутри списка хранится массив размера Capacity и указатель Count, который показывает, сколько элементов уже заполнено. Когда внутренний массив заполнен, и мы добавляем новый элемент, список создаёт новый массив с размером, в два раза больше предыдущего, переносит туда все существовавшие элементы, и добавляет новый элемент. Новый массив, как и любой другой массив, занимает один целый фрагмент в памяти.
За счёт того, что список — обёртка над массивом, доступ по индексу у него так же занимает константное время и происходит очень быстро. А вот добавление элемента, как вы поняли, уже не такое быстрое и иногда требует выделения памяти.
Удаление элемента по индексу также может занять определённое время, так как при удалении мы сдвигаем в массиве все элементы, находящиеся после удаляемого. Удаление первого элемента в списке размера N повлечёт перемещение N элементов.
Как мы можем улучшить свой код, зная всё это:
- Использовать конструктор листа с явно указанным Capacity, если мы знаем, что нам надо добавить не больше чем N элементов, чтобы избежать пересоздания массива:
var list = new List<int>(25); // создали список с массивом длиной 25 под капотом
- Не использовать список там, где размер нам известен, и изменяться при выполнении программы он не будет.
Ну и парочка примеров:
var list = new List<int>();
list.Add(2);
list.Add(3);
list.Add(4);
list.Remove(2); // удалили число 2 по индексу 0, осталось 2 элемента
list.RemoveAt(0); // удалили число по индексу 0, число 3, остался 1 элемент
Словари
Довольно полезная структура данных, которая представляет собой набор пар ключ-значение. Использовать можем так, как потребуется. Например, создать словарь для получения имени по Id, элемента по Id, да хоть строки по строке, главное задать понятный для себя смысл этим строкам.
Суть в чём: мы храним определённый объекты (значения), и задаём им определённое описание (ключи). Тип значений и тип ключей может быть любым. При обращении по индексу мы указываем не порядковый номер элемента, а ключ, и получаем относящееся к нему значение. Ограничением является то, что ключи должны быть уникальными, иначе мы получим исключение. Вторым ограничением является то, что при попытке получить значение по ключу, которого нет в словаре, так же будет выброшено исключение.
var dict = new Dictionary<string, int>();
dict["Key1"] = 10;
dict["Key2"] = 20;
dict["Key3"] = 30;
if (dict.TryGetValue("Key4", out var intValue))
{
Console.WriteLine(intValue);
}
Для проверки наличия ключа в словаре я рекомендую использовать TryGetValue, а не ContainsKey, потому что в случае TryGetValue мы сразу получаем значение и можем его использовать, а в случае ContainsKey нам надо будет повторно найти это значение по ключу, то есть провести поиск два раза.
Hashset
Главным преимуществом этой структуры данных является то, что она позволяет хранить только уникальные значения. Мы могли бы использовать список, проверять, если там такой элемент, и если нет, то добавлять. Но с хеш-сетом это будет элегантнее и быстрее. Под капотом он вычисляет хеш-функцию, поэтому поиск элементов и проверка их наличия происходит очень быстро, и он не кидает исключений, если элемент уже существует.
Учитывайте нюанс, что при добавлении 2 элементов Ревит, полученных разными путями, мы получим, что добавятся оба, ведь они представляют разные ссылки. Для сохранения только уникальных элементов используйте их Id. ElementId тоже ссылочный тип, но у него переопределены функции Equals и операторы сравнения, поэтому они сравниваются по значению.
var hashSet = new HashSet<int> { 1, 2, 3 };
hashSet.Add(2); // Не добавит, так как 2 уже существует.
Заключение
На этом на сегодня всё. Я не стал рассказывать про популярные в таких статьях стеки и очереди, потому что почти никогда не использовал их на практике для Ревита.
Узнать ещё больше о структурах данных можно на бесплатном курсе на Stepik (автор не я, там довольно сложно, но полезной информации много).
Делитесь в комментариях, если узнали что-то новое, рассказывайте о тех структурах данных, которые нравятся вам, и до новых встреч!
