![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png\")
\n<\/div>\n<\/div>Такой список достаточно просто реализовать с помощью обычного массива. Задачи будем хранить в случайном порядке, а в момент получения текущей задачи будем искать самую приоритетную. В таком случае добавление новой задачи будет иметь сложность O(1), а вот получение O(n), потому что каждый раз нужно искать элемент с самым большим приоритетом.<\/p>\n
Второй вариант тоже использует обычный массив, только элементы в нем хранятся уже в отсортированном виде. В таком случае сложность меняется зеркально. Добавление нового элемента будет занимать O(n), а получение O(1).<\/p>\n
Оба варианта не совсем эффективны, особенно когда очень много данных. Здесь на помощь приходят очереди с приоритетом.<\/p>\n
Очереди с приоритетом строятся на базе такой структуры данных как куча. Поэтому важно рассмотреть ее устройство. Куч есть большое множество, но нас сейчас интересует только двоичная куча.<\/p>\n
Двоичная куча<\/h2>\n
Двоичная куча представляет из себя двоичное дерево где каждый элемент имеет два дочерних элемента и хранит значение не меньшее чем в дочерних. Они также делятся на два типа: максимальная и минимальная. В первой хранятся элементы в порядке убывания, а во второй в порядке возрастания.<\/p>\n
![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-max-min-2.png\")
\n<\/div>\n<\/div>Для хранения данных кучи удобно использовать обычные массивы. Такой подход занимает мало места и сам по себе достаточно элегантный. На как определить какой элемент массива на какой ссылается? Для этого есть две простые формулы.<\/p>\n
- \n
- 2i + 1 — позволяет найти позицию левого дочернего элемента<\/li>\n
- 2i + 2 — позволяет найти позицию правого дочернего элемента<\/li>\n<\/ul>\n\n
![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-array-structure-3.png\")
\n<\/div>\n<\/div>Сортировка дерева<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-sorting-4.png\")
\n<\/div>\n<\/div>Когда добавляем или удаляем элемент из очереди, свойства кучи могут нарушиться. В таком случае нужно привести ее в порядок. Представим, что есть метод MakeHeap, который принимает на вход индекс элемента и он сортирует его поддерево.<\/p>\n
Берем элемент по текущему индексу и сравниваем его с дочерними элементами. Если какой-то дочерний элемент больше текущего, меняем его местами с текущим и спускаемся дальше, чтобы проверить поддерево. Таким образом, мы доходим до конца изначального поддерева сортируя все его поддеревья.<\/p>\n
Как это выглядит в коде:<\/p>\n
private void SortHeap(int i)\r\n{\r\n\tvar size = values.Count;\r\n\tvar left = 2 * i + 1;\r\n\tvar right = 2 * i + 2;\r\n\tvar largest = i;\r\n\t\r\n\tif (left < size && values[left] > values[largest])\r\n\t\tlargest = left;\r\n\t\t\r\n\tif (right < size && values[right] > values[largest])\r\n\t\tlargest = right;\r\n\t\t\r\n\tif (largest != i)\r\n\t{\r\n\t\tvar temp = values[i];\r\n\t\tvalues[i] = values[largest];\r\n\t\tvalues[largest] = temp;\r\n\t\tSortHeap(largest);\r\n\t}\r\n}<\/code><\/pre>Делаем кучу из обычного массива<\/h2>\n
Мы умеем сортировать элементы в поддеревьях, теперь применим этот метод для того, чтобы с обычного массива сделать кучу. Так как потомки гарантированно есть у первых (n\/2 — 1) элементов, то достаточно только для них вызвать метод SortHeap.<\/p>\n
private void MakeHeap()\r\n{\r\n\tfor (int i = values.Count \/ 2 - 1; i >= 0; i--)\r\n\t{\r\n\t\tSortHeap(i);\r\n\t}\r\n}<\/code><\/pre>Добавление нового элемента<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-insert-5.png\")
\n<\/div>\n<\/div>Новый элемент сначала добавляется в конец массива, после чего запускаем сортировку дерева. Алгоритм получается достаточно простым:<\/p>\n
if (values.Count == 0)\r\n{\r\n\t\/\/ Просто добавляем в элемент в массив, если он пустой\r\n\tvalues.Add(value);\r\n}\r\nelse\r\n{\r\n\t\/\/ Добавляем элемент в конец массива и запускаем сортировку дерева\r\n\tvalues.Add(value);\r\n\tfor (int i = values.Count \/ 2 - 1; i >= 0; i--)\r\n\t{\r\n\t\tSortHeap(i);\r\n\t}\t\t\r\n}<\/code><\/pre>Удаление элемента<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/heap-remove-5.png\")
\n<\/div>\n<\/div>Чтобы удалить элемент нужно поменять его с последним элементов в куче, потом удалить и запустить сортировку кучи. Так как мы делаем очередь, то будем всегда удалять первый (корневой) элемент кучи.<\/p>\n
var size = values.Count;\r\n\t\t\r\nvar last = values.Count - 1;\r\nvar temp = values[0];\r\nvalues[0] = values[last];\r\nvalues[last] = temp;\r\nvalues.RemoveAt(last);\r\n\r\nfor (int i = size \/ 2 - 1; i >= 0; i--)\r\n\tSortHeap(i);\r\n\r\nreturn temp;<\/code><\/pre>Итого<\/h2>\n
Куча обладает необходимыми свойствами для создания очереди с приоритетом. Она хранит данные в отсортированном виде, работает быстрее чем обычный массив. Достаточно реализовать такие же методы как в обычной очереди и у нас получиться очередь с приоритетом:<\/p>\n
- \n
- Enqueue — обычная вставка в кучу, ничего даже менять не нужно.<\/li>\n
- Dequeue — обычное удаление элемента с кучи, только удаляем мы всегда элемент с 0 индексов.<\/li>\n<\/ul>\n
Посмотреть полную реализацию можно на dotnetfiddle<\/a>.
\n <\/p>\n", "date_published": "2022-07-05T16:29:29-04:00", "date_modified": "2022-07-05T16:28:12-04:00", "tags": [ "dotnet", "алгоритми та структури даних", "програмування" ], "image": "https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png", "_date_published_rfc2822": "Tue, 05 Jul 2022 16:29:29 -0400", "_rss_guid_is_permalink": "false", "_rss_guid": "271", "_e2_data": { "is_favourite": false, "links_required": [ "system\/library\/highlight\/highlight.js", "system\/library\/highlight\/highlight.css" ], "og_images": [ "https:\/\/www.stefaniuk.website\/pictures\/heap-pic-1.png", "https:\/\/www.stefaniuk.website\/pictures\/heap-max-min-2.png", "https:\/\/www.stefaniuk.website\/pictures\/heap-array-structure-3.png", "https:\/\/www.stefaniuk.website\/pictures\/heap-sorting-4.png", "https:\/\/www.stefaniuk.website\/pictures\/heap-insert-5.png", "https:\/\/www.stefaniuk.website\/pictures\/heap-remove-5.png" ] } }, { "id": "252", "url": "https:\/\/www.stefaniuk.website\/all\/collection-in-csharp\/", "title": "Коллекции в C#", "content_html": "В C# для хранения набора однотипных данных можно использовать массивы. Но с ними не всегда удобно работать потому, что они имеют фиксированный размер и часто бывает сложно угадать, какого размера нужен массив.<\/p>\n
Для решения этих задач в C# есть коллекции. Они позволяют динамически изменять свой размер. Также они удобны тем что некоторые из них представляют из себя готовые реализации стандартных структур данных, таких как список, хеш таблица, стек, очередь.<\/p>\n
Все коллекции лежат в нескольких пространствах имен:<\/p>\n
- \n
- System.Collections — простые необобщенные коллекции.<\/li>\n
- System.Collections.Generic — обобщенные коллекции.<\/li>\n
- System.Collections.Specialized — специальные коллекции.<\/li>\n
- System.Collections.Concurrent — коллекции для работы в многопоточной среде.<\/li>\n<\/ul>\n
Устройство коллекций<\/h2>\n
Все коллекции, так или иначе, реализую интерфейс ICollection, некоторые реализуют интерфейсы IList и IDictionary (которые внутри наследуют ICollection). Этот интерфейс предоставляет минимальный набор методов, которые позволяют реализовать коллекцию.<\/p>\n
В свою очередь, ICollection расширяет интерфейс IEnumerable. Он предоставляет нумератор, который позволяет обходить коллекции элемент за элементом. Именно этот интерфейс позволяет использовать коллекции в цикле foreach.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-interfaces.png\")
\n<\/div>\n<\/div>Вместительность коллекций<\/h2>\n
Одна из ключевых особенностей коллекций это изменяемый размер. Когда создается экземпляр коллекции она внутри себя инициализирует какую-то структуру данных, зачастую это массив. По умолчанию этот массив имеет определённую вместительность, которую можно просмотреть с помощью свойства Capacity.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-capacity.png\")
\n<\/div>\n<\/div>После активного наполнения коллекции наступает момент, когда внутренний массив заполнен и мы не можем добавить новый элемент. В таком случае коллекция создаёт новый массив с большей вместительностью (обычно в два раза больше) и копирует туда данные со старого массива.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collections-capacity-copy.png\")
\n<\/div>\n<\/div>Поэтому коллекции, которые основаны на массивах имеют сложность вставки:<\/p>\n
- \n
- O(1) — когда вместительности достаточно.<\/li>\n
- O(n) — когда вместительности недостаточно и нужно копировать данные в массив побольше.<\/li>\n<\/ul>\n
Чтобы избежать уменьшения производительности нужно при создании коллекции указать необходимую нам вместительности. Это позволит уменьшить количество копирований.<\/p>\n
Сравнивание и сортировка элементов коллекций<\/h2>\n
Сравнение<\/b>
\nТакие методы как Contains, IndexOf, LastIndexOf, and Remove используют сравнение элементов для свое работы. Если коллекция является обобщенной, то используются два механизма сравнения:<\/p>\n- \n
- Если тип реализует интерфейс IEquatable тогда механизм сравнения использует метод Equals этого интерфейса.<\/li>\n
- Если тип не реализует интерфейс IEquatable тогда для сравнения используется Object.Equals<\/li>\n<\/ul>\n
Некоторые коллекции имеют конструктор, который принимает имплементацию IEqualityComparer
который используется для сравнения.<\/p>\n Сортировка<\/b>
\nСортировка работает похожим образом, как и сравнение, но делиться на два вида: явную сортировку и сортировка по умолчанию.<\/p>\nСортировка по умолчанию подразумевает, что типы хранящиеся в коллекции реализуют интерфейс IComparable, чьи методы под капотом используют коллекции для сравнения.<\/p>\n
Явная сортировка подразумевает, что наши элементы не реализуют интерфейс IComparable, поэтому в качестве параметра метода сортировки нужно передать объект, который реализует интерфейс IComparer.<\/p>\n
Если тип не реализует интерфейс IComparable и мы не передали явно тип, который реализует IComparer, то при вызове метода сортировки вылетит исключение.<\/p>\n
System.InvalidOperationException: Failed to compare two elements in the array.\r\n\tSystem.ArgumentException: At least one object must implement IComparable.<\/code><\/pre>Алгоритмическая сложность коллекций<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/collection-compexity-4.png\")
\nИсточник: Runtime Complexity of .NET Generic Collection<\/a><\/div>\n<\/div>\nСписок List
<\/h2>\n Класс List
представляет из себя простейший список однотипных элементов, которые можно получить по индексу. Предоставляет методы для поиска, сортировки и изменения списка.<\/p>\n var linkedList = new List<string>();\r\nlinkedList.Add("A");\r\nlinkedList.Add("B");\r\nlinkedList.Add("C");<\/code><\/pre>Для своей работы списки используют обычные массивы. Это значит что могут быть проблемы с производительностью из-за частого создания нового массива. Также у списков есть еще два нюанса:<\/p>\n
- \n
- Вставка элемента в середину списка приведет к созданию нового массива и копирование данных, что негативно влияет на производительность.<\/li>\n
- Списки не могут хранить экстремально огромное количество элементов из-за фрагментации адресного пространства.<\/li>\n<\/ul>\n
Если эти проблемы существенны для вас, то стоит присмотреться к LinkedList
или ImmutableList <\/p>\n Связанный список LinkedList
<\/h2>\n Класс LinkedList
реализует простой двухсвязный список, каждый элемент которого имеет ссылка на предыдущий и следующий элемент.<\/p>\n Каждый элемент списка оборачивается в специальный класс LinkedListNode
, который имеет ссылку на следующий элемент (Next), на предыдущий элемент (Previous) и само значение (Value).<\/p>\n var linkedList = new LinkedList<string>();\r\nlinkedList.AddFirst("A");\r\nlinkedList.AddLast("B");\r\nlinkedList.AddLast("C");\r\n\t\t\r\nConsole.WriteLine(linkedList.First.Previous == null); \/\/ True\r\nConsole.WriteLine(linkedList.Last.Next == null); \/\/ True<\/code><\/pre>Связанный список позволяет вставлять и удалять элементы со сложностью O (1). Также мы можем удалить элемент и заново вставить в тот же или другой список без дополнительного выделения памяти.<\/p>\n
Словарь Dictionary
Словари хранят данные в виде ключ-значение. Каждый элемент словаря представляет из себя объект структуры KeyValuePair
В качестве ключа можно использовать любой объект. Ключи должны быть уникальными в рамках коллекции.<\/p>\n
var linkedList = new Dictionary<string, string>();\r\nlinkedList.Add("key1", "A");\r\nlinkedList.Add("key2", "B");\r\nlinkedList.Add("key3", "C");<\/code><\/pre>Внутри словари построены на базе хеш-таблицы, что позволяет очень быстро вставлять элементы и получать по ключу (сложность O (1)). Сами же хеш-таблицы, в свою очередь, реализованы с помощью массивов.<\/p>\n
Для адресации значений внутри коллекции используются хеш коды ключей. Это значит что объект ключа не должен изменяться, потому что это приведет к изменению хеш кода, что в свою очередь приведет к потере данных.<\/p>\n
Исходники Dictionary<\/a><\/p>\n
Стек Stack
и Очередь Queue <\/h2>\n Очереди и стеки полезны, когда нужно временно хранить какие-то элементы, то есть удалять элемент после его извлечения. Также они позволяют определить строгую очередность записи и извлечения элементов.<\/p>\n
Стеки Stack
— реализуют подход LIFO (last in — first out).<\/p>\n var stack = new Stack<int>();\r\nstack.Push(1); \/\/ stack = [1]\r\nstack.Push(2); \/\/ stack = [1,2]\r\nvar item = stack.Pop(); \/\/ stack = [1], item = 2<\/code><\/pre>Очереди Queue
— реализуют подход (first in — first out).<\/p>\n var queue = new Queue<int>();\r\nqueue.Enqueue(1); \/\/ queue = [1]\r\nqueue.Enqueue(2); \/\/ queue = [1,2]\r\nitem = queue.Dequeue(); \/\/ queue = [2], item = 1<\/code><\/pre>Внутри они реализованы с помощью обычных массивов.<\/p>\n
Множества HashSet
и SortedSet <\/h2>\n Эти классы реализуют математические множества. По своей природе множество — набор уникальных элементов с общими характеристиками, в нашем случае одного типа.<\/p>\n
Также множества отличаются от обычных списков тем что они предоставляют набор методов, которые реализуют операции с теории множеств<\/a>.<\/p>\n
Внутренняя реализация этих классов отличается:<\/p>\n
- \n
- HashSet
— множество, построенное на базе хеш-таблицы.<\/li>\n - SortedSet
— отсортированное множество, построенное на базе красно-черного дерева.<\/li>\n<\/ul>\n
<\/p>\nISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };\r\n \r\nset.UnionWith(new[] { 5, 6 }); \/\/ set = { 1, 2, 3, 4, 5, 6 }\r\nset.IntersectWith(new[] { 3, 4, 5, 6, 7 }); \/\/ set = { 3, 4, 5, 6 }\r\nset.ExceptWith(new[] { 6, 7 }); \/\/ set = { 3, 4, 5 }\r\nset.SymmetricExceptWith(new[] { 4, 5, 6 }); \/\/ set = { 3, 6 }<\/code><\/pre>Можно заметить что LINQ предоставляет несколько похожих операций (Distinct, Union, Intersect, Except), которые можно выполнить с любой коллекцией. Но HastSet предоставляет намного больший набор операций с множествами.<\/p>\n
Основная разница в том что методы множеств изменяют текущую коллекцию, в то время как LINQ методы всегда создают новый экземпляр коллекции.<\/p>\n
KeyedCollection
KeyedCollection это абстрактный класс, который позволяет построить собственную коллекцию.<\/p>\n
Эта коллекция является гибридом между списками (IList
) и словарями (IDictionary ). От списков ей досталась возможность получать элементы по индексу, а от словарей возможность получать элемент по ключу.<\/p>\n В отличие от словарей, элемент KeyedCollection коллекции не является парой ключ-значение, вместо этого весь элемент является значением, а в качестве ключа используется его поле, свойство или любое другое значение. Для получения ключа используется абстрактный метод, который является обязательным для реализации. GetKeyForItem<\/p>\n
var keyedCollection = new UserCollection();\r\nkeyedCollection.Add(new User {\r\n\tId = 1,\r\n\tName = "A"\r\n});\r\nkeyedCollection.Add(new User {\r\n\tId = 2,\r\n\tName = "B"\r\n});\r\n\t\t\r\nConsole.WriteLine(keyedCollection[2].Name); \/\/ B\r\n\t\r\npublic class UserCollection: KeyedCollection<int, User>\r\n{\r\n\tprotected override int GetKeyForItem(User user) => user.Id;\r\n}\r\n\t\r\npublic class User\r\n{\r\n\tpublic int Id {get;set;}\r\n\tpublic string Name {get;set;}\r\n}<\/code><\/pre>Внутри KeyedCollection построен на базе двух структур данных. Для быстрого получения данных по ключу используется словарь, а для получение элемента по индексу используется массив.<\/p>\n
NameValueCollection<\/h2>\n
Представляет из себя коллекцию, которая похожа на словарь но в качестве ключей и значений используются строки. Элементы можно получить как по индексу так и по ключу.<\/p>\n
Особенной эту коллекцию делает то что однин ключ может содержать несколько эллементов.<\/p>\n
var namedCollection = new NameValueCollection();\r\nnamedCollection.Add("key1", "value1");\r\nnamedCollection.Add("key2", "value2");\r\nnamedCollection.Add("key1", "value3");\r\n\r\nConsole.WriteLine(namedCollection.Count); \/\/ 2\r\nConsole.WriteLine(namedCollection["key1"]); \/\/ value1,value3<\/code><\/pre>Иммутабельные коллекции<\/h2>\n
Иммутабельные коллекции не входят в стандартную библиотеку классов (BCL). Для их использования нужно установить System.Collections.Immutable NuGet пакет.<\/p>\n
Они позволяют безопасно работать в многопоточной среде. Вместо того чтобы использовать блокировки синхронизации, как это делают многопоточные коллекции, неизменяемые коллекции не могут быть изменены после создания. Это автоматически делает их безопасными для использования в многопоточных сценариях, так как нет возможности другому потоку изменить коллекцию.<\/p>\n
Сами же коллекции можно поделить на несколько видов:<\/p>\n
- \n
- Mutable — обычные коллекции которые поддерживают изменения.<\/li>\n
- Immutable — коллекции, которые полностью запрещают изменения. Хотя на самом деле любое изменение иммутабельной коллекции приводит к созданию новой.<\/li>\n
- ReadOnly — обертки над стандартными коллекциями, которые не дают поменять данные. Из-за того что это всего лишь обертка мы можем поменять данные в оригинальной коллекции и ead only коллекция подтянет изменения.<\/li>\n<\/ul>\n
Детальнее можно ознакомиться в статье: Read only, frozen, and immutable collections<\/a>.<\/p>\n
Иммутабельные стеки ImmutableStack
и очереди ImmutableQueue <\/b><\/h2>\n Ничем не отличаются от обычных стеков и очередей, кроме того, что являются не изменяемыми.<\/p>\n
Для реализации иммутабельных стеков\/очередей массивы не подойдут. Причина заключается в том, что на каждое изменение придётся делать полную копию массива что очень неэффективно.<\/p>\n
Поэтому для работы иммутабельных стеков\/очередей используется связанный список. При изменении коллекции нужно всего лишь создать новый элемент, который ссылается на предыдущее значение. В итоге не происходит никакого копирования и экономится память.<\/p>\n
Иммутабельные списки ImmutableList<\/b><\/h2>\n
Под капотом используют сбалансированное бинарное дерево вместо массива или связанного списка.<\/p>\n
Массивы не подходят из-за накладных расходов на их использование. Связанный список тоже не подойдет, потому что ImmutableList поддерживает обращение по индексу из-за чего нужно долго перебирать связанные элементы. Поэтому для нормальной работы иммутабельных списков используют сбалансированное бинарное дерево.<\/p>\n
Иммутабельные массивы ImmutableArray<\/b><\/h2>\n
По сути, это небольшая прослойка над обычными массивами и все. Любые мутабельные операции приводят к копированию массива. Из-за этого скорость добавления элементов равна O (n), но в то же время получение элемента по индексу занимает O (1).<\/p>\n
Итерация по массиву работает в несколько раз быстрее чем у других неизменяемых коллекциях.<\/p>\n
Иммутабельные словари ImmutableDictionary<\/b><\/h2>\n
Неизменяемые словари внутри работают на базе сбалансированного дерева, но с одной особенностью. Каждый элемент внутри коллекции представлен в виде отдельного дерева (ImmutableList
Из-за своей особенности иммутабельные словари потребляют очень много памяти и долго работают. Поэтому стоит аккуратно их использовать.<\/p>\n
Особенности использования<\/b><\/h2>\n
Как было выше сказано все операции изменения коллекций приводят к созданию новой коллекции. Нужно помнить, что необходимо использовать новый экземпляр вместо старого.<\/p>\n
var immutableList = new[] { 1, 2, 3 }.ToImmutableList();\r\nimmutableList = immutableList.Add(4);<\/code><\/pre>По идее чтобы было проще, мы можем объединить все изменения в цепочку:<\/p>\n
immutableList = immutableList\r\n .Add(5)\r\n .Add(6)\r\n .Add(7);<\/code><\/pre>Однако такого способа стоит избегать, потому что каждый вызов метода создает новый экземпляр коллекции. Хотя неизменяемые коллекции реализованы таким образом, чтобы повторно использовать как можно большую часть оригинальной коллекции при создании нового экземпляра, некоторые выделения памяти все же необходимы. Это означает больше работы для сборщика мусора.<\/p>\n
Чтобы минимизировать проблему стоит использовать методы, которые могут выполнить нужные изменения за один вызов. Например:<\/p>\n
immutableList = immutableList.AddRange(new[] { 5, 6, 7 });<\/code><\/pre>Но такие методы позволяют сделать только один вид изменения. Например у нас нет единого метода, который позволяет добавить и удалить одну запись:<\/p>\n
immutableList = immutableList\r\n .Add(6)\r\n .Remove(2);<\/code><\/pre>Для решения этой проблемы иммутабельные коллекции предоставляют билдеры (builders).<\/p>\n
var builder = immutableList.ToBuilder();\r\nbuilder.Add(6);\r\nbuilder.Remove(2);\r\nimmutableList = builder.ToImmutable();<\/code><\/pre>Внутри себя билдеры используют соответствующую мутабельную коллекцию, что позволяет выполнить все операции над одним экземпляром коллекции. Только после вызова метода ToImmutable экземпляр снова будет неизменяемым. Таким образом можно сократить объем работы уборщика мусора.<\/p>\n
Источники и доп. материалы<\/h2>\n
- \n
- How to Choose the Right .NET Collection Class?<\/a> Отличная статья про то какую коллекцию выбрать в .NET. И вообще хорошо хоть и поверхностно описаны конкурентные и неизменяемые коллекции.<\/li>\n
- .NET Collections: comparing performance and memory usage<\/a>. Сравнивались коллекции-словари и среди них лучше всего отработал Dictionary, SortedList в свою очередь в среднем потреблял в два раза меньше памяти чем обычный словарь. Хуже всего себя показал отсортированный словарь SortedDictionary.<\/li>\n
- Collections and Data Structures<\/a>. Отличное описание коллекций на MSDN.<\/li>\n<\/ul>\n", "date_published": "2021-04-21T11:10:51-04:00", "date_modified": "2021-04-26T07:16:48-04:00", "tags": [ "dotnet", "алгоритми та структури даних", "програмування" ], "image": "https:\/\/www.stefaniuk.website\/pictures\/collections-linked-list.png", "_date_published_rfc2822": "Wed, 21 Apr 2021 11:10:51 -0400", "_rss_guid_is_permalink": "false", "_rss_guid": "252", "_e2_data": { "is_favourite": false, "links_required": [ "system\/library\/highlight\/highlight.js", "system\/library\/highlight\/highlight.css" ], "og_images": [ "https:\/\/www.stefaniuk.website\/pictures\/collections-linked-list.png", "https:\/\/www.stefaniuk.website\/pictures\/collectios-dict.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-keyed.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-named.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-list.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-interfaces.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-capacity.png", "https:\/\/www.stefaniuk.website\/pictures\/collections-capacity-copy.png", "https:\/\/www.stefaniuk.website\/pictures\/collection-compexity-4.png" ] } }, { "id": "224", "url": "https:\/\/www.stefaniuk.website\/all\/zhiznenny-cikl-zaprosov-v-asp-net-core-mvc\/", "title": "Жизненный цикл запросов в ASP.NET Core", "content_html": "
Жизненный цикл — это цепочка событий, этапов и компонентов, которые взаимодействуют друг с другом, чтобы обработать запрос пользователя и предоставить ему ответ.<\/p>\n
Общий вид на жизненный цикл ASP.NET Core MVC приложений:<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/main-cycle.png\")
\n<\/div>\nОн содержит в себе несколько этапов:<\/p>\n
- \n
- Middlewares<\/li>\n
- Routing<\/li>\n
- Controller Initialization<\/li>\n
- Controller action execution<\/li>\n
- Result Execution<\/li>\n
- View Rendering<\/li>\n<\/ul>\n
Middlewares<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/middlewares.png\")
\n<\/div>\nMiddlewares представляют из себя базовые блоки, с помощью которых строится HTTP пайплайн. Такой пайплайн представляет из себя конвейер, который обрабатывает каждый запрос. Каждый блок получает запрос и смотрит на него, если может предоставить ответ — возвращает его, если нет, передаёт запрос следующему блоку.<\/p>\n
В ASP.NET Core у нас есть 4 метода, с помощью которых мы можем создавать свои middlewares.<\/p>\n
- \n
- Use<\/li>\n
- Run<\/li>\n
- Map<\/li>\n
- MapWhen<\/li>\n<\/ul>\n
Официальная документация<\/a><\/p>\n
Routing<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/Routing.png\")
\n<\/div>\nМаршрутизация позволяет найти для каждого URL подходящий обработчик, а также извлекает все параметры из URL и красиво их нам предоставляет. Для работы роутинга нам нужны две middleware:<\/p>\n
- \n
- UseRouting<\/li>\n
- UseEndpoints<\/li>\n<\/ul>\n
Как все это работает?<\/b><\/p>\n
UseRouting встраивает класс EndpointRoutingMiddleware, он смотрит на конечные точки, которые есть в приложении и выбирает подходящую. Выбор происходит на основании URL и заголовков. После того как нужный обработчик найден (Request delegate) его присваивают свойству Endpoint(IEndpointFeature) внутри текущего HttpContext. В дальнейшем мы можем получить его значения с помощью метода GetEndpoint.<\/p>\n
UseEndpoints встраивает EndpointMiddleware. Он отвечает за выполнение установленной ранее конечной точки.<\/p>\n
Официальная документация<\/a><\/p>\n
Controller initialization<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/ControllerInitialization.png\")
\n<\/div>\nДля обеспечения работы контроллеров у есть два класса: ResourceInvoker, ControllerActionInvoker.<\/p>\n
ResourceInvoker<\/b> является абстрактным классом, который содержит общую логику работы с ресурсом, обработку исключений и результата.<\/p>\n
ControllerActionInvoker<\/b> наследует ResourceInvoker и добавляет в него логику работы с контроллерами и их методами.<\/p>\n
Каждый из этих классов содержит машину состояний, где каждое состояние отвечает за свой этап жизненного цикла контроллера.<\/p>\n
Исходники классов можно посмотреть на github (ResourceInvoker<\/a>, ControllerActionInvoker<\/a>).<\/p>\n
Action workflow<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/action-life-cycle.png\")
\n<\/div>\nРабота каждого метода контроллера состоит из своего жизненного цикла. Основой которого являются фильтры. Каждый фильтр может отрабатывать как и перед запуском действия, так и после.<\/p>\n
Общий вид этого жизненного цикла:<\/p>\n
- \n
- Фильтры авторизации<\/li>\n
- Фильтры ресурсов<\/li>\n
- Привязки моделей<\/li>\n
- Фильтры действий<\/li>\n
- Выполнение метода контроллера<\/li>\n
- Фильтры исключений<\/li>\n
- Фильтры результатов<\/li>\n
- Выполнение результата<\/li>\n
- Фильтры результатов<\/li>\n<\/ul>\n
Детальнее про фильтры можно почитать на метаните<\/a>.<\/p>\n
Result execution<\/h2>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/action-result.png\")
\n<\/div>\nМетоды контроллера возвращают объекты результата, которые в дальнейшем преобразовываются в соответствующее представление. Объект результата должен наследовать абстрактный класс ActionResult. Фреймворк предоставляет нам большое множество готовых классов.<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/action-results.png\")
\n<\/div>\nОбщий вид того как происходит рендеринг представлений:<\/p>\n
\n![\"\"](\"https:\/\/www.stefaniuk.website\/pictures\/Render-cycle.png\")
\n<\/div>\nИсточники<\/h2>\n
- \n
- Официальная документация<\/a><\/li>\n
- Курс на pluralsight<\/a><\/li>\n<\/ul>\n", "date_published": "2020-06-12T16:38:19-04:00", "date_modified": "2023-03-12T18:36:23-04:00", "tags": [ "asp.net core", "dotnet" ], "image": "https:\/\/www.stefaniuk.website\/pictures\/main-cycle.png", "_date_published_rfc2822": "Fri, 12 Jun 2020 16:38:19 -0400", "_rss_guid_is_permalink": "false", "_rss_guid": "224", "_e2_data": { "is_favourite": true, "links_required": [], "og_images": [ "https:\/\/www.stefaniuk.website\/pictures\/main-cycle.png", "https:\/\/www.stefaniuk.website\/pictures\/middlewares.png", "https:\/\/www.stefaniuk.website\/pictures\/Routing.png", "https:\/\/www.stefaniuk.website\/pictures\/ControllerInitialization.png", "https:\/\/www.stefaniuk.website\/pictures\/action-life-cycle.png", "https:\/\/www.stefaniuk.website\/pictures\/action-result.png", "https:\/\/www.stefaniuk.website\/pictures\/action-results.png", "https:\/\/www.stefaniuk.website\/pictures\/Render-cycle.png" ] } }, { "id": "207", "url": "https:\/\/www.stefaniuk.website\/all\/async-programming-in-csharp\/", "title": "Асинхронное программирование в C#", "content_html": "
Небольшой конспект доклада об асинхронности в .NET. Cоветую его посмотреть, будет полезен как новичкам, так и уже опытным ребятам.<\/p>\n
\n - Курс на pluralsight<\/a><\/li>\n<\/ul>\n", "date_published": "2020-06-12T16:38:19-04:00", "date_modified": "2023-03-12T18:36:23-04:00", "tags": [ "asp.net core", "dotnet" ], "image": "https:\/\/www.stefaniuk.website\/pictures\/main-cycle.png", "_date_published_rfc2822": "Fri, 12 Jun 2020 16:38:19 -0400", "_rss_guid_is_permalink": "false", "_rss_guid": "224", "_e2_data": { "is_favourite": true, "links_required": [], "og_images": [ "https:\/\/www.stefaniuk.website\/pictures\/main-cycle.png", "https:\/\/www.stefaniuk.website\/pictures\/middlewares.png", "https:\/\/www.stefaniuk.website\/pictures\/Routing.png", "https:\/\/www.stefaniuk.website\/pictures\/ControllerInitialization.png", "https:\/\/www.stefaniuk.website\/pictures\/action-life-cycle.png", "https:\/\/www.stefaniuk.website\/pictures\/action-result.png", "https:\/\/www.stefaniuk.website\/pictures\/action-results.png", "https:\/\/www.stefaniuk.website\/pictures\/Render-cycle.png" ] } }, { "id": "207", "url": "https:\/\/www.stefaniuk.website\/all\/async-programming-in-csharp\/", "title": "Асинхронное программирование в C#", "content_html": "
- Официальная документация<\/a><\/li>\n
- .NET Collections: comparing performance and memory usage<\/a>. Сравнивались коллекции-словари и среди них лучше всего отработал Dictionary, SortedList в свою очередь в среднем потреблял в два раза меньше памяти чем обычный словарь. Хуже всего себя показал отсортированный словарь SortedDictionary.<\/li>\n
- How to Choose the Right .NET Collection Class?<\/a> Отличная статья про то какую коллекцию выбрать в .NET. И вообще хорошо хоть и поверхностно описаны конкурентные и неизменяемые коллекции.<\/li>\n
- SortedSet
- HashSet