Алгоритми та Структури Даних

Очередь с приоритетом

Tue, 05 Jul 2022 16:29:29 -0400

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

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

Второй вариант тоже использует обычный массив, только элементы в нем хранятся уже в отсортированном виде. В таком случае сложность меняется зеркально. Добавление нового элемента будет занимать O(n), а получение O(1).

Оба варианта не совсем эффективны, особенно когда очень много данных. Здесь на помощь приходят очереди с приоритетом.

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

Двоичная куча

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

Для хранения данных кучи удобно использовать обычные массивы. Такой подход занимает мало места и сам по себе достаточно элегантный. На как определить какой элемент массива на какой ссылается? Для этого есть две простые формулы.

2i + 1 — позволяет найти позицию левого дочернего элемента
2i + 2 — позволяет найти позицию правого дочернего элемента

Сортировка дерева

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

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

Как это выглядит в коде:

private void SortHeap(int i)
{
var size = values.Count;
var left = 2 * i + 1;
var right = 2 * i + 2;
var largest = i;

if (left < size && values[left] > values[largest])
largest = left;

if (right < size && values[right] > values[largest])
largest = right;

if (largest != i)
{
var temp = values[i];
values[i] = values[largest];
values[largest] = temp;
SortHeap(largest);
}
}

Делаем кучу из обычного массива

Мы умеем сортировать элементы в поддеревьях, теперь применим этот метод для того, чтобы с обычного массива сделать кучу. Так как потомки гарантированно есть у первых (n/2 — 1) элементов, то достаточно только для них вызвать метод SortHeap.

private void MakeHeap()
{
for (int i = values.Count / 2 - 1; i >= 0; i--)
{
SortHeap(i);
}
}

Добавление нового элемента

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

if (values.Count == 0)
{
// Просто добавляем в элемент в массив, если он пустой
values.Add(value);
}
else
{
// Добавляем элемент в конец массива и запускаем сортировку дерева
values.Add(value);
for (int i = values.Count / 2 - 1; i >= 0; i--)
{
SortHeap(i);
}
}

Удаление элемента

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

var size = values.Count;

var last = values.Count - 1;
var temp = values[0];
values[0] = values[last];
values[last] = temp;
values.RemoveAt(last);

for (int i = size / 2 - 1; i >= 0; i--)
SortHeap(i);

return temp;

Итого

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

Enqueue — обычная вставка в кучу, ничего даже менять не нужно.
Dequeue — обычное удаление элемента с кучи, только удаляем мы всегда элемент с 0 индексов.

Посмотреть полную реализацию можно на dotnetfiddle.

Бинарный поиск и бинарное дерево поиска

Sat, 11 Jun 2022 14:00:56 -0400

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

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

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

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

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

А теперь живой пример. Есть отсортированный массив и нужно найти число 9. Берем элемент из середины — 8, сравниваем, 9 больше 8, значит нужно продолжить поиск в правой части.

Снова берем элемент из середины — 11, 9 меньше 11, значит нужно искать в левой части нашего подмассива.

Берем элемент из середины — 9, сравниваем, элементы равны, число 9 есть в массиве и храниться по индексу 4. Мы нашли нужный элемент всего за 3 шага.

Если пробовать оценить скорость работы алгоритма, то получается что она равна O(log n). Для сравнения, обычный поиск перебором имеет скорость O(n), это значит что нужно перебрать все элементы массива. Что это значит на практике?

Посмотреть реализацию на C# можно на dotnetfiddle.

Как оптимизировать сортировку?

Массив всегда должен быть отсортированным чтобы поиск работал, а это значит что при каждом добавлении нового элемента нужно запускать сортировку. Возникает вопрос, а что если сразу вставлять новый элемент в правильное место? Тогда у нас всегда будет отсортированный массив и не нужно каждый раз прогонять сортировку.

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

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

Как работает поиск в дереве?

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

Вставка нового элемента работает так же как и поиск. Сравниваем новый элемент с текущим и опускаемся по дереву вниз пока не найдем подходящее место. В итоге при каждом добавлении у нас будет отсортированный набор данных.

Но что будет если всегда добавлять элементы с все большим и большим значением? Наше дерево будет выглядеть вот так:

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

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

Итог

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

Если тема интересная, то можно копнуть дальше и разобраться с:

Красно черными деревьями
Кучами
B-деревьями
и т. д.

Бонус

На сайте https://idea-instructions.com есть объяснения разных алгоритмов в стиле инструкций с икеи. Например AVL дерево

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

Wed, 21 Apr 2021 11:10:51 -0400

В 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.

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

Источник: Runtime Complexity of .NET Generic Collection

Список 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.

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

Sat, 21 Sep 2019 06:20:03 -0400

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GIN индекс

Mon, 09 Sep 2019 05:34:33 -0400

GIN (Generalized Inverted Index) — инвертированный индекс, который позволяет реализовать что-то на подобии полнотекстового поиска. Активно используется в PostgreSQL.

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

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

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

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

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

Ниже небольшая реализация самого простого индекса на C#:

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

Fri, 06 Sep 2019 03:32:10 -0400

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

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

Хеш-таблица

Wed, 21 Aug 2019 03:51:53 -0400

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

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

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

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

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

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

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

Когда использовать?

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

Простая реализация: What is an example of a Hashtable implementation in C#?

Алгоритмы сортировки

Wed, 31 Jul 2019 16:05:53 -0400

Классификация

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

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

Сортировка пузырьком
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Быстрая сортировка

Ссылка на сайт с гифками, которые демонстрируют работу алгоритмов: https://www.toptal.com/developers/sorting-algorithms

Сортировка пузырьком

Самая стандартная и простая сортировка. Выполняет проходы по массиву и перемещает наибольший элемент в конец массива.

	Лучший вариант	Средний вариант	Худший вариант
Степень сложности	O(n)	O(n^2)	O(n^2)
Рост памяти	O(1)	O(1)	O(1)

public void Sort(int[] inputArray)
{
for (int i = 0; i < inputArray.Length; i++) {
for (int j = 1; j < inputArray.Length; j++) {
if (inputArray[j-1] > inputArray[j]) {
Swap(inputArray, j-1, j);
}
}
}
}

public void Swap(int[] inputArray, int indexLeft, int indexRight)
{
if (indexLeft == indexRight) return;
var temp = inputArray[indexLeft];
inputArray[indexLeft] = inputArray[indexRight];
inputArray[indexRight] = temp;
}

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

	Лучший вариант	Средний вариант	Худший вариант
Степень сложности	O(n)	O(n^2)	O(n^2)
Рост памяти	O(1)	O(1)	O(1)

public static void Sort(int[] inputArray)
{
int currentElementIndex= 1;
while (currentElementIndex < inputArray.Length)
{
if (inputArray[currentElementIndex] < inputArray[currentElementIndex - 1]) {
var newIndex = FindIndex(inputArray, inputArray[currentElementIndex]);
Insert(inputArray, newIndex, currentElementIndex);
}
currentElementIndex++;
}
}

public static int FindIndex(int[] inputArray, int element)
{
for (int i = 0; i < inputArray.Length; i++)
{
if (inputArray[i] > element) {
return i;
}
}
return 0;
}

public static void Insert(int[] inputArray, int indexLeft, int indexRight)
{
if (indexLeft == indexRight) return;
var temp = inputArray[indexLeft];
inputArray[indexLeft] = inputArray[indexRight];
for (int current = indexRight; current > indexLeft; current--) {
inputArray[current] = inputArray[current-1];
}
inputArray[indexLeft + 1] = temp;
}

Сортировка выбором
На каждом своем шаге отыскивает наименьший элемент в неотсортированной части массива и устанавливает его в соответствующую позицию массива.

	Лучший вариант	Средний вариант	Худший вариант
Степень сложности	O(n)	O(n^2)	O(n^2)
Рост памяти	O(1)	O(1)	O(1)

public static void Sort(int[] input) {
for (int i = 0; i < input.Length; i++) {
var smallestElementIndex = FindIndexOfSmallestElement(input, i);
Swap(input, smallestElementIndex, i);
}
}

public static int FindIndexOfSmallestElement(int[] input, int startFrom = 0) {
var smallestElementValue = input[startFrom];
var smallestElementIndex = startFrom;
for (int i = startFrom + 1; i < input.Length; i++)
{
if (smallestElementValue > input[i]) {
smallestElementValue = input[i];
smallestElementIndex = i;
}
}
return smallestElementIndex;
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
if (indexLeft == indexRight) return;
var temp = input[indexLeft];
input[indexLeft] = input[indexRight];
input[indexRight] = temp;
}

Сортировка слиянием
Разбивает массив на подмассивы примерно одинакового размера, рекурсивно разбивает до тех пор, пока размер массива будет равен 1. После этого происходит сортировка частей и их соединение в один.

	Лучший вариант	Средний вариант	Худший вариант
Степень сложности	O(n log n)	O(n log n)	O(n log n)
Рост памяти	O(n)	O(n)	O(n)

public static void Sort(int[] input) {
if (input.Length <= 1) {
return;
}

// Поделили массивы
var leftSize = input.Length / 2;
var rightSize = input.Length - leftSize;
var left = new int[leftSize];
var right = new int[rightSize];

// Скопировали данные из основного массива
Array.Copy(input, 0, left, 0, leftSize);
Array.Copy(input, leftSize, right, 0, rightSize);

Sort(left);
Sort(right);

Merge(input, left, right);
}

public static void Merge(int[] input, int[] left, int[] right) {
var leftIndex = 0;
var rightIndex = 0;
var leftAndRightSize = left.Length + right.Length;

for (int i = 0; i < leftAndRightSize; i++) {
if (leftIndex >= left.Length) {
input[i] = right[rightIndex];
rightIndex++;
}
else if (rightIndex >= right.Length) {
input[i] = left[leftIndex];
leftIndex++;
}
else if (left[leftIndex] < right[rightIndex]) {
input[i] = left[leftIndex];
leftIndex++;
}
else {
input[i] = right[rightIndex];
rightIndex++;
}
}
}

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

Этапы сортировки:
• Случайный выбор опорного элемента массива (pivotValue), относительно которого переупорядочиваются элементы массива.
• Переместить все значения, которые больше опорного, вправо, а все значения, что меньше опорного, влево.
• Повторить алгоритм для неотсортированной левой и правой части массива, пока каждый элемент не окажется на своей позиции.

	Лучший вариант	Средний вариант	Худший вариант
Степень сложности	O(n log n)	O(n log n)	O(n^2)
Рост памяти	O(1)	O(1)	O(1)

public static void Sort(int[] input, int leftIndex, int rightIndex) {
var i = leftIndex;
var j = rightIndex;
var pivot = input[(leftIndex + rightIndex) >> 1];

while (i <= j) {
while (input[i] < pivot) {
i++;
}
while (input[j] > pivot) {
j--;
}

if (i <= j) {
Swap(input, i, j);
j--;
i++;
}

if (leftIndex < j) {
Sort(input, leftIndex, j);
}

if (rightIndex > i) {
Sort(input, i, rightIndex);
}
}
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
if (indexLeft == indexRight) return;
var temp = input[indexLeft];
input[indexLeft] = input[indexRight];
input[indexRight] = temp;
}

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

Mon, 24 Jun 2019 14:18:13 -0400

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

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

Односвязный список

+-------+------+    +-------+-------+ 
| Hello |  *---+--->| world | null  +
+-------+------+    +-------+-------+

Двусвязный список

+----------+---------+       +----------+----------+ 
|          |     *---|------>|          |          |
|  Hello   |         |       |          |  world   |
|          |         |<------|---*      |          |
+----------+---------+       +----------+----------+

Кольцевой список

.        +-------<----------<--------------<--------+
         |                                          |
+-----+--+---+    +-----+------+    +-----+-----+   |
| 12  |  *---+--->| 15  |   *--+--->| 25  |  *--+---+
+-----+------+    +-----+------+    +-----+-----+

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

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

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

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

Недостатки

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

Ссылки