6 заметок с тегом

структуры данных

Коллекции в C#

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

Для решения этих задач в C# есть коллекции. Они позволяют динамически изменять свой размер. Также они удобны тем что некоторые из них представляют из себя готовые реализации стандартных структур данных, таких как список, хеш таблица, стек, очередь.

Все коллекции лежат в нескольких пространствах имен:

  • System.Collections — простые необобщенные коллекции.
  • System.Collections.Generic — обобщенные коллекции.
  • System.Collections.Specialized — специальные коллекции.
  • System.Collections.Concurrent — коллекции для работы в многопоточной среде.

Устройство коллекций

Все коллекции, так или иначе, реализую интерфейс ICollection, некоторые реализуют интерфейсы IList и IDictionary (которые внутри наследуют ICollection). Этот интерфейс предоставляет минимальный набор методов, которые позволяют реализовать коллекцию.

В свою очередь, ICollection расширяет интерфейс IEnumerable. Он предоставляет нумератор, который позволяет обходить коллекции элемент за элементом. Именно этот интерфейс позволяет использовать коллекции в цикле foreach.

Вместительность коллекций

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

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

Поэтому коллекции, которые основаны на массивах имеют сложность вставки:

  • O(1) — когда вместительности достаточно.
  • O(n) — когда вместительности недостаточно и нужно копировать данные в массив побольше.

Чтобы избежать уменьшения производительности нужно при создании коллекции указать необходимую нам вместительности. Это позволит уменьшить количество копирований.

Сравнивание и сортировка элементов коллекций

Сравнение
Такие методы как Contains, IndexOf, LastIndexOf, and Remove используют сравнение элементов для свое работы. Если коллекция является обобщенной, то используются два механизма сравнения:

  • Если тип реализует интерфейс IEquatable тогда механизм сравнения использует метод Equals этого интерфейса.
  • Если тип не реализует интерфейс IEquatable тогда для сравнения используется Object.Equals

Некоторые коллекции имеют конструктор, который принимает имплементацию IEqualityComparer который используется для сравнения.

Сортировка
Сортировка работает похожим образом, как и сравнение, но делиться на два вида: явную сортировку и сортировка по умолчанию.

Сортировка по умолчанию подразумевает, что типы хранящиеся в коллекции реализуют интерфейс IComparable, чьи методы под капотом используют коллекции для сравнения.

Явная сортировка подразумевает, что наши элементы не реализуют интерфейс IComparable, поэтому в качестве параметра метода сортировки нужно передать объект, который реализует интерфейс IComparer.

Если тип не реализует интерфейс IComparable и мы не передали явно тип, который реализует IComparer, то при вызове метода сортировки вылетит исключение.

System.InvalidOperationException: Failed to compare two elements in the array.
	System.ArgumentException: At least one object must implement IComparable.

Алгоритмическая сложность коллекций

Список List

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

var linkedList = new List<string>();
linkedList.Add("A");
linkedList.Add("B");
linkedList.Add("C");

Для своей работы списки используют обычные массивы. Это значит что могут быть проблемы с производительностью из-за частого создания нового массива. Также у списков есть еще два нюанса:

  • Вставка элемента в середину списка приведет к созданию нового массива и копирование данных, что негативно влияет на производительность.
  • Списки не могут хранить экстремально огромное количество элементов из-за фрагментации адресного пространства.

Если эти проблемы существенны для вас, то стоит присмотреться к LinkedList или ImmutableList

Связанный список LinkedList

Класс LinkedList реализует простой двухсвязный список, каждый элемент которого имеет ссылка на предыдущий и следующий элемент.

Каждый элемент списка оборачивается в специальный класс LinkedListNode, который имеет ссылку на следующий элемент (Next), на предыдущий элемент (Previous) и само значение (Value).

var linkedList = new LinkedList<string>();
linkedList.AddFirst("A");
linkedList.AddLast("B");
linkedList.AddLast("C");
		
Console.WriteLine(linkedList.First.Previous == null); // True
Console.WriteLine(linkedList.Last.Next == null);   // True

Связанный список позволяет вставлять и удалять элементы со сложностью O (1). Также мы можем удалить элемент и заново вставить в тот же или другой список без дополнительного выделения памяти.

Словарь Dictionary

Словари хранят данные в виде ключ-значение. Каждый элемент словаря представляет из себя объект структуры KeyValuePair.

В качестве ключа можно использовать любой объект. Ключи должны быть уникальными в рамках коллекции.

var linkedList = new Dictionary<string, string>();
linkedList.Add("key1", "A");
linkedList.Add("key2", "B");
linkedList.Add("key3", "C");

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

Для адресации значений внутри коллекции используются хеш коды ключей. Это значит что объект ключа не должен изменяться, потому что это приведет к изменению хеш кода, что в свою очередь приведет к потере данных.

Исходники Dictionary

Стек Stack и Очередь Queue

Очереди и стеки полезны, когда нужно временно хранить какие-то элементы, то есть удалять элемент после его извлечения. Также они позволяют определить строгую очередность записи и извлечения элементов.

Стеки Stack — реализуют подход LIFO (last in — first out).

var stack = new Stack<int>();
stack.Push(1); // stack = [1]
stack.Push(2); // stack = [1,2]
var item = stack.Pop(); // stack = [1], item = 2

Очереди Queue — реализуют подход (first in — first out).

var queue = new Queue<int>();
queue.Enqueue(1); // queue = [1]
queue.Enqueue(2); // queue = [1,2]
item = queue.Dequeue(); // queue = [2], item = 1

Внутри они реализованы с помощью обычных массивов.

Множества HashSet и SortedSet

Эти классы реализуют математические множества. По своей природе множество — набор уникальных элементов с общими характеристиками, в нашем случае одного типа.

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

Внутренняя реализация этих классов отличается:

  • HashSet — множество, построенное на базе хеш-таблицы.
  • SortedSet — отсортированное множество, построенное на базе красно-черного дерева.


ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
 
set.UnionWith(new[] { 5, 6 });              // set = { 1, 2, 3, 4, 5, 6 }
set.IntersectWith(new[] { 3, 4, 5, 6, 7 }); // set = { 3, 4, 5, 6 }
set.ExceptWith(new[] { 6, 7 });             // set = { 3, 4, 5 }
set.SymmetricExceptWith(new[] { 4, 5, 6 }); // set = { 3, 6 }

Можно заметить что LINQ предоставляет несколько похожих операций (Distinct, Union, Intersect, Except), которые можно выполнить с любой коллекцией. Но HastSet предоставляет намного больший набор операций с множествами.

Основная разница в том что методы множеств изменяют текущую коллекцию, в то время как LINQ методы всегда создают новый экземпляр коллекции.

KeyedCollection

KeyedCollection это абстрактный класс, который позволяет построить собственную коллекцию.

Эта коллекция является гибридом между списками (IList) и словарями (IDictionary). От списков ей досталась возможность получать элементы по индексу, а от словарей возможность получать элемент по ключу.

В отличие от словарей, элемент KeyedCollection коллекции не является парой ключ-значение, вместо этого весь элемент является значением, а в качестве ключа используется его поле, свойство или любое другое значение. Для получения ключа используется абстрактный метод, который является обязательным для реализации. GetKeyForItem

var keyedCollection = new UserCollection();
keyedCollection.Add(new User {
	Id = 1,
	Name = "A"
});
keyedCollection.Add(new User {
	Id = 2,
	Name = "B"
});
		
Console.WriteLine(keyedCollection[2].Name); // B
	
public class UserCollection: KeyedCollection<int, User>
{
	protected override int GetKeyForItem(User user) => user.Id;
}
	
public class User
{
	public int Id {get;set;}
	public string Name {get;set;}
}

Внутри KeyedCollection построен на базе двух структур данных. Для быстрого получения данных по ключу используется словарь, а для получение элемента по индексу используется массив.

NameValueCollection

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

Особенной эту коллекцию делает то что однин ключ может содержать несколько эллементов.

var namedCollection = new NameValueCollection();
namedCollection.Add("key1", "value1");
namedCollection.Add("key2", "value2");
namedCollection.Add("key1", "value3");

Console.WriteLine(namedCollection.Count);   // 2
Console.WriteLine(namedCollection["key1"]); // value1,value3

Иммутабельные коллекции

Иммутабельные коллекции не входят в стандартную библиотеку классов (BCL). Для их использования нужно установить System.Collections.Immutable NuGet пакет.

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

Сами же коллекции можно поделить на несколько видов:

  • Mutable — обычные коллекции которые поддерживают изменения.
  • Immutable — коллекции, которые полностью запрещают изменения. Хотя на самом деле любое изменение иммутабельной коллекции приводит к созданию новой.
  • ReadOnly — обертки над стандартными коллекциями, которые не дают поменять данные. Из-за того что это всего лишь обертка мы можем поменять данные в оригинальной коллекции и ead only коллекция подтянет изменения.

Детальнее можно ознакомиться в статье: Read only, frozen, and immutable collections.

Иммутабельные стеки ImmutableStack и очереди ImmutableQueue

Ничем не отличаются от обычных стеков и очередей, кроме того, что являются не изменяемыми.

Для реализации иммутабельных стеков/очередей массивы не подойдут. Причина заключается в том, что на каждое изменение придётся делать полную копию массива что очень неэффективно.

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

Иммутабельные списки ImmutableList

Под капотом используют сбалансированное бинарное дерево вместо массива или связанного списка.

Массивы не подходят из-за накладных расходов на их использование. Связанный список тоже не подойдет, потому что ImmutableList поддерживает обращение по индексу из-за чего нужно долго перебирать связанные элементы. Поэтому для нормальной работы иммутабельных списков используют сбалансированное бинарное дерево.

Иммутабельные массивы ImmutableArray

По сути, это небольшая прослойка над обычными массивами и все. Любые мутабельные операции приводят к копированию массива. Из-за этого скорость добавления элементов равна O (n), но в то же время получение элемента по индексу занимает O (1).

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

Иммутабельные словари ImmutableDictionary

Неизменяемые словари внутри работают на базе сбалансированного дерева, но с одной особенностью. Каждый элемент внутри коллекции представлен в виде отдельного дерева (ImmutableList>). Так что по своей сути иммутабельные словари — это деревья деревьев.

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

Особенности использования

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

var immutableList = new[] { 1, 2, 3 }.ToImmutableList();
immutableList = immutableList.Add(4);

По идее чтобы было проще, мы можем объединить все изменения в цепочку:

immutableList = immutableList
    .Add(5)
    .Add(6)
    .Add(7);

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

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

immutableList = immutableList.AddRange(new[] { 5, 6, 7 });

Но такие методы позволяют сделать только один вид изменения. Например у нас нет единого метода, который позволяет добавить и удалить одну запись:

immutableList = immutableList
    .Add(6)
    .Remove(2);

Для решения этой проблемы иммутабельные коллекции предоставляют билдеры (builders).

var builder = immutableList.ToBuilder();
builder.Add(6);
builder.Remove(2);
immutableList = builder.ToImmutable();

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

Источники и доп. материалы

  • How to Choose the Right .NET Collection Class? Отличная статья про то какую коллекцию выбрать в .NET. И вообще хорошо хоть и поверхностно описаны конкурентные и неизменяемые коллекции.
  • .NET Collections: comparing performance and memory usage. Сравнивались коллекции-словари и среди них лучше всего отработал Dictionary, SortedList в свою очередь в среднем потреблял в два раза меньше памяти чем обычный словарь. Хуже всего себя показал отсортированный словарь SortedDictionary.
  • Collections and Data Structures. Отличное описание коллекций на MSDN.
 Нет комментариев    162   2 мес   dotnet   программирование   структуры данных

Небольшая заметка об индексах в ms sql

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

Что из себя представляет индекс?

Внутри сервера они представлены в виде B-tree, где B означает сбалансированное, а не бинарное дерево.

Например мы хотим найти запись с Id = 2581.
Начиная с корня, выполняется поиск наименьшего значения ключа, большего или равного требуемому. Так мы найдем узел 18316, потом спустимся в узел 9031 и там мы увидим что есть прямая ссылка на лежащие данные по ключу 2581, после чего осуществляем вычитку данных.

Кластерный индекс

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

Не кластерный индекс

Структура такая же как и кластерного индекса, но с двумя отличиями:

  1. Не изменяет физическое упорядочивание данных.
  2. Страницы индекса состоят из ключа индекса и ссылки на строку.

SQL Server использует индекс для нахождения записей, совпадающих с условиями запроса.

Составной ключ в индексе

SQL Server позволяет создавать индексы по нескольким колонкам. Но в таком случае у нас появляется ограничение. Длинна составного ключа не должна быть больше 900 байт. Но бывают исключения, например у нас есть две колонки, каждая из которых длинной в 500 байт. Сервер создаст индекс, в случае если нет данных, которые будут превышать длину в 900 байт.

Также стоит помнить что индексы типа (Col1, Col2) и (Col2, Col1) разные.

Уникальные индексы

Такие индексы создаются для реализации целостности данных. Таким образом сервер гарантирует уникальные значение для указанной колонки или составного ключа.

Статьи, которые советую почитать чтобы глубже разобраться в теме

  1. Очень хорошая статья о всех типах индексов, когда их стоит создавать и как использовать
  2. Индексы. Теоретические основы.
 Нет комментариев    256   2019   sql   программирование   структуры данных

GIN индекс

Это обратный индекс, использует PostgreSQL для реализации полнотекстового поиска. Суть заключается в том что мы для каждой лексемы указывает список документов в который она входит.

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

Хорошая аналогия для этого метода — алфавитный указатель в конце книги, где для каждого термина приведен список страниц, где этот термин упоминается.

 Нет комментариев    191   2019   программирование   структуры данных

Алгоритм поиска Ли

Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.

Алгоритм состоит из 3 шагов:

  1. Инициализация
  2. Распространение волны
  3. Восстановление пути

Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.

Ортогональный поиск.
Ортогонально-диагональный поиск.

Псевдокод

Взято из Википедии.

Инициализация

Пометить стартовую ячейку 
d := 0

Распространение волны

ЦИКЛ
  ДЛЯ каждой ячейки loc, помеченной числом d
    пометить все соседние свободные непомеченные ячейки числом d + 1
  КЦ
  d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)

Восстановление пути

ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден

Пример кода, который реализует алгоритм и выводит на экран путь (C#).

 Нет комментариев    166   2019   алгоритмы   программирование   структуры данных

Хеш-таблица

Хеш-таблица — специальная структура данных, в которой данные хранятся в виде хеш — значение. Очень похожа на словарь, но в ее основе используется хеш функция для ускорения поиска.

Есть два основных способа реализации хеш-таблицы:

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

В .NET уже существует готовая реализация этой структуры: System.Collections.HasTable. Но с появлением обобщенных коллекций стал устаревшим. На его место пришел словарь — Dictionary. Так как в базовом объекте есть 2 метода Equal и GetHashCode мы можем в качестве ключа словаря использовать любой тип данных.

 Нет комментариев    148   2019   dotnet   программирование   структуры данных

Структуры данных: связанные списки

Связанные списки — структура данных, элемент которой содержит собственные данные, так и одну или две ссылки на следующий и/или предыдущий элемент. Связанный список работает как массив, который растет и уменьшаться при необходимости из произвольной точки массива.

Наиболее используемые типы списков:

  1. Односвязный список
+-------+------+    +-------+-------+ 
| Hello |  *---+--->| world | null  +
+-------+------+    +-------+-------+
  1. Двусвязный список
+----------+---------+       +----------+----------+ 
|          |     *---|------>|          |          |
|  Hello   |         |       |          |  world   |
|          |         |<------|---*      |          |
+----------+---------+       +----------+----------+
  1. Кольцевой список
.        +-------<----------<--------------<--------+
         |                                          |
+-----+--+---+    +-----+------+    +-----+-----+   |
| 12  |  *---+--->| 15  |   *--+--->| 25  |  *--+---+
+-----+------+    +-----+------+    +-----+-----+



Быстродействие

  • Добавляет элемент в конец/начало списка — O(1)
  • Удаляет первый элемент списка со значением, равным переданному — O(n)
  • Поиск элемента — O(n)
  • Копирование а массив — O(n)
  • Получить количество — O(1)

Преимущества

  1. Элементы могут быть удалены или добавлены из середины списка
  2. Нет необходимости объявлять разvер списка при инициализации
  3. Эффективное удаление и добавление элементов

Недостатки

  1. Связанные списки не имеют возможности произвольного доступа к элементам — т. е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него.
  2. Для работы списков требуется динамическое выделение памяти, что может привести к утечкам памяти.

Ссылки

  1. https://metanit.com/sharp/algoritm/2.1.php
  2. https://rtfm.co.ua/c-svyazannye-spiski/
  3. https://ru.wikipedia.org/wiki/Связный_список
  4. https://tproger.ru/translations/linked-list-for-beginners/
  5. https://medium.com/outco/reversing-a-linked-list-easy-as-1-2-3-560fbffe2088
 Нет комментариев    147   2019   программирование   структуры данных