В .NET 6 появилась новая коллекция — PriorityQueue<TElement,TPriority>. До этого очереди с приоритетами уже были в .NET, но только в виде внутренних классов — они использовались под капотом разных механизмов в WPF, Rx.NET и в других частях фреймворка.
Но в .NET 6 PriorityQueue стала новой коллекцией, которой теперь можно пользоваться из клиентского кода. Давайте посмотрим, что предлагает эта очередь, как она устроена внутри и насколько быстро работает. Под катом будет постепенное погружение: от примеров использования в коде к введению n-арные деревья.
Что это такое
PriorityQueue — это коллекция элементов, каждый из которых имеет значение и приоритет. Элементы добавляются в очередь с определенным приоритетом и извлекаться из неё “последовательно” — вначале будут извлечены элементы с наименьшим приоритетом, добавленные первыми. То есть, PriorityQueue — это модификация обычной FIFO (first-in-first-out) очереди, в которой элементы с меньшим приоритетом будут оказываться перед всеми элементами с большим приоритетом и извлекаться первыми.
В каких задачах может пригодиться PriorityQueue? Если коротко, то в тех же, что и обычная очередь, когда часть элементов нужно обработать “вне очереди”. С большой вероятностью такой сценарий понадобится как часть инфраструктурного кода. Вот пара примеров использования PriorityQueue:
Организация очереди обработки запросов веб-сервером, в которой входящие запросы из Lisnter’а складываются в очередь и приоритезириуются на основе оставшегося лимита времени запроса или явного приоритета запроса (запрос демона или запрос фронта).
Алгоритм Дейкстры — если пишите логистический сервис или просто ищите путь в графе обработчиков в вашем workflow (а это может быть и вывод правил в экспертных системах, и парсинг сайтов/данных).
Любая абстрактная система асинхронной обработки данных/событий/запросов, в которой может быть класс обслуживания — например, если вы хотите дать возможность выполнить в своей системе какой-то служебный запрос перед всеми на случай забитой очереди.
Как работает PriorityQueue
Обычная очередь извлекает элементы в порядке их добавления — first in first out. Очередь с приоритетами извлекает элементы в порядке приоритета от меньшего к большему. При этом PriorityQueue не гарантирует сохранение порядка извлечения для элементов с одинаковым приоритетом.
var queue = new PriorityQueue<string, int>();
queue.Enqueue("Миша", 30);
queue.Enqueue("Маша", 29);
queue.Enqueue("Дима", 31);
queue.Enqueue("Коля", 30);
queue.Enqueue("Паша", 31);
while (queue.TryDequeue(out var name, out var age))
{
Console.WriteLine($"{name}, age {age}");
}Вывод на консоль:
Маша, age 29
Миша, age 30
Коля, age 30
Дима, age 31
Паша, age 31Как PriorityQueue сравнивает приоритеты
Чтобы определить наименьший приоритет нужно как-то сравнивать приоритеты между собой. PriorityQueue использует для этого стандартный интерфейс IComparer<T>:
public interface IComparer<in T>
{
int Compare(T? x, T? y);
}По умолчанию используется дефолтный компоратор System.Collections.Generic.Comparer<TPriority>.Default. Если приоритет задается сложным типом (например, классом ServerHealthState), то можно передать в конструктор PriorityQueue свою реализацию компоратора:
// ServerHealthStateComparer реализует IComparer<ServerHealthState>
var comparer = new ServerHealthStateComparer();
var queue = new PriorityQueue<ServerInfo, ServerHealthState>(comparer);Контракт PriorityQueue
Создать новый экземпляр PriorityQueue можно тремя способами: инициализировать пустую очередь, задать начальное количество элементов чтобы избежать дополнительного расширения массива при добавлении новых элементов или инициализировать очередь готовым набором значений с приоритетом:
public PriorityQueue<TElement,TPriority>()
public PriorityQueue<TElement,TPriority>(int initialCapacity)
public PriorityQueue<TElement,TPriority>(IEnumerable<ValueTuple<TElement,TPriority>> items)Каждый конструктор имеет перегрузку с компаратором в качестве дополнительного элемента:
public PriorityQueue<TElement,TPriority>(IComparer<TPriority>? comparer)
public PriorityQueue<TElement,TPriority>(int initialCapacity, IComparer<TPriority>? comparer)
public PriorityQueue<TElement,TPriority>(IEnumerable<ValueTuple<TElement,TPriority>> items, IComparer<TPriority> comparer)Интересной особенностью очереди с приоритетом является то, что в случае пустой очереди начальное хранилище оказывается пустым и расширяется до 4 элементов при первом добавлении:
_nodes = Array.Empty<(TElement, TPriority)>();У PriorityQueue есть несколько свойств для получения информации об очереди:
// Получает компоратор приоритетов, используемый в текущем экземпляре PriorityQueue
public IComparer<TPriority> Comparer { get; }
// Получает количество элементов в очереди
public int Count { get; }
// Получает коллекцию, которая перечисляет элементы очереди в неупорядоченном виде.
public PriorityQueue<TElement,TPriority>.UnorderedItemsCollection UnorderedItems { get; }Новые элементы можно добавить либо по одному, либо сразу множеством — с общим приоритетом или отдельным значением приоритета для каждого элемента:
// Добавляет в очередь элемент с заданным приоритетом
public void Enqueue(TElement element, TPriority priority);
// Добавляет в очередь последовательность элементов с заданным приоритетом
public void EnqueueRange(System.Collections.Generic.IEnumerable<TElement> elements, TPriority priority);
// Добавляет в очередь последовательность элементов с заданными приоритетами
public void EnqueueRange(System.Collections.Generic.IEnumerable<(TElement Element, TPriority Priority)> items);Кроме извлечения очередного элемента из очереди есть привычный метод Peek, который получает элемент из очереди, не удаляя его. В случае с пустой очередью попытка извлечения элемента закончится исключением InvalidOperationException, для безопасного извлечения есть аналогичные методы с префиксом Try:
// Удаляет из очереди и возвращает элемент с наименьшим приоритетом
public TElement Dequeue();
// Пытается удалить из очереди и возвращает элемент с наименьшим приоритетом.
// Возвращает результат операции: true при успешном удалении и false если очередь пуста
public bool TryDequeue(out TElement element, out TPriority priority);
// Возвращает элемент с наименьшим приоритетом, не удаляя его из очереди
public TElement Peek();
// Пытается вернуть элемент с наименьшим приоритетом, не удаляя его из очереди
// Возвращает результат операции: true при успешном извлечении и false если очередь пуста
public bool TryPeek(out TElement element, out TPriority priority);Можно быстро очистить очередь при помощи метода Clear:
// Удаляет все элементы из очереди
public void Clear();Есть и несколько специализированных методов, которые можно использовать для увеличения эффективности работы с очередью — быстро расширить внутреннее хранилище до определенного значения, обрезать внутреннее хранилище или одновременно извлечь элемент и добавить новый:
// Добавляет в очередь элемент с заданным приоритетом и извлекает элемент с наименьшим приоритетом
public TElement EnqueueDequeue(TElement element, TPriority priority);
// Гарантирует, что очередь может хранить capacity элементов без дополнительного расширения внутреннего хранилища
// Расширяет текущее внутреннее хранилище до размера capacity, если его ёмкость была меньше
// Возвращает capacity внутреннего хранилища
public int EnsureCapacity(int capacity);
// Устанавливает capacity внутренннего хранилища на фактическое количество элементов в очереди, если это меньше 90% от текущей capacity
public void TrimExcess ();Что внутри PriorityQueue
Как устроена очередь с приоритетами внутри?
Самая простая реализация “в лоб”, которую можно придумать — это связный список элементов. Новые элементы добавляются в хвост списка за константное время, а при извлечении нужно найти первый элемент с наименьшим приоритетом, перебрав для этого все элементы за линейное время. Peek тоже будет линейным.
Можно ли сделать извлечение элементов быстрее, чем O(n)? Для этого понадобится держать список в отсортированном упорядоченном состоянии. Если мы используем в качестве структуры данных связный список, то для добавления понадобится последовательно перебирать элементы в поиске нужного места для вставки и асимптотика Enqueue будет O(n), так что теперь добавление в очередь становится слишком дорогостоящей операцией. Если заменять список на динамический массив, то вставка потребует “раздвигания” элементов и всё равно останется O(n)-операцией.
На самом деле, для решения задачи хранения элементов с приоритетом, “быстрого” добавления новых элементов и извлечения первого элемента с наименьшим приоритетом идеально подходит такая структура данных, как куча. Есть несколько типов универсальных куч, а ещё специализированные кучи, которые предоставляют дополнительную функциональность или работают эффективнее, но имеют ограничения. Например, в качестве типа приоритета могут использоваться только целочисленные значения.
Чаще всего в библиотеках разных языков программирования используются универсальные кучи — бинарные или d-арные. Во-первых, они позволяют извлекать и добавлять элемент за O(log n), а, во-вторых, благодаря свойствам кучи для их хранения достаточно массива элементов. Навигация между родительскими и дочерними элементами для каждого узла происходит по простым формулам.
В .NET 6 в основе PriorityQueue лежит 4-арная min-куча (то есть куча, где каждый узел может иметь 4 элемента уровнем ниже и содержит минимальный элемент своего поддерева), представленная в виде массива кортежей (TElement Element, TPriority Priority)[] _nodes, которая инициализируются пустым массивом по-умолчанию и расширяется при недостаточном Capacity по стандартному правилу List<T> — в 2 раза, но не менее, чем на 4 элемента.
4-арная min-куча всегда удовлетворяет двум свойствам:
Свойство формы: 4-арная куча — это полное 4-арное дерево, то есть такое дерево, где все уровни полностью заполнены, за исключением, возможно, последнего уровня. Узлы заполняются слева направо.
Свойство кучи: значение (приоритета), хранящееся в каждом узле, меньше или равно его дочерним элементам.
Сложность операций в PriorityQueue связана с сложностью операций в куче:
Enqueue(TElement, TPriority): O(log4 N)Dequeue(): O(log4 N)Peek(): O(1)Count: O(1)
Читать словесное описание алгоритмов кучи — сомнительное удовольствие, а иллюстрации для 4-арной кучи не прибавляют понятности, поэтому иллюстрации к алгоритмам будут на основе биарной min-кучи, а в примерах кода можно увидеть, что работа бинарной и 4-арной кучи отличается только методами навигации по куче, то есть получения индекса родительского и дочерних элементов.
Методы для навигации по куче в PriorityQueue:
private const int Arity = 4;
private const int Log2Arity = 2;
private static int GetParentIndex(int index) => (index - 1) >> Log2Arity;
private static int GetFirstChildIndex(int index) => (index << Log2Arity) + 1;Чтобы добавить элемент в кучу, нужно выполнить операцию увеличения кучи (есть разные термины: up-heap, bubble-up, heapify-up):
Если куча пуста, то новый элемент становится её корнем (root)
Добавляем новый элемент на нижний уровень кучи в первое доступное место.
Сравниваем добавленный элемент с его родителем. Если они в правильном порядке, то операция завершена.
Если нет, то меняем добавленный элемент с родительским элементом местами и возвращаемся к предыдущему шагу.
private void MoveUpCustomComparer((TElement Element, TPriority Priority) node, int nodeIndex)
{
while (nodeIndex > 0)
{
int parentIndex = GetParentIndex(nodeIndex);
(TElement Element, TPriority Priority) parent = _nodes[parentIndex];
if (_comparer.Compare(node.Priority, parent.Priority) < 0)
{
_nodes[nodeIndex] = parent;
nodeIndex = parentIndex;
}
else
break;
}
_nodes[nodeIndex] = node;
}Количество требуемых операций зависит только от количества уровней, на которые должен подняться новый элемент чтобы привести кучу в согласованное состяоние.
Итоговая временная сложность в худшем случае составляет O(log N).
Для извлечения минимального значения из min-heap достаточно обратиться к _nodes[0]. Алгоритм удаления корневого (минимального) элемента из кучи:
Удаляем значение корневого элемента
Заменяем текущий удаляемый (корневой) элемент последним элементом кучи (_nodes[0] = _nodes[_size - 1];
Сравниваем текущий элемент с его потомками. Если они не в правильном порядке (то есть, существуют потомки меньше текущего элемента), то меняем текущий элемент с наименьшим из потомков и повторяем шаг.
Если они в правильном порядке, то операция завершена.
На примере бинарного min-дерева из иллюстрации после извлечения значения [0]-го элемента на его место встает последний ([14]-ый). Из потомков [1]-го и [2]-го выбирается наименьший — [2]-ой, т.к. приоритет [0]-го 26, а [2]-го 18, то они заменяются местами, а [2]-ой элемент становится текущим. Затем из его потомков, [5]-го и [6]-го элементов выбирается тот, у которого приоритет ниже, это [6]-ой элемент. Так как приоритет [2]-го теперь 26, а [6]-го 22, то они меняются местами, а [6]-ой элемент становится текущим. Теперь у текущего элемента только 1 потомок, [13]-ый. Его приоритет выше, чем приоритет текущего, поэтому алгоритм заканчивается.
// node = _nodes[--_size] — последний элемент кучи,
// nodeIndex = 0 — корневой элемент
private void MoveDownCustomComparer((TElement Element, TPriority Priority) node, int nodeIndex)
{
int i;
while ((i = GetFirstChildIndex(nodeIndex)) < size)
{
// Ищем дочернюю ноду с минимальным приоритетом
(TElement Element, TPriority Priority) minChild = _nodes[i];
int minChildIndex = i;
int childIndexUpperBound = Math.Min(i + Arity, _size);
while (++i < childIndexUpperBound)
{
(TElement Element, TPriority Priority) nextChild = _nodes[i];
if (_comparer.Compare(nextChild.Priority, minChild.Priority) < 0)
{
minChild = nextChild;
minChildIndex = i;
}
}
if (_comparer.Compare(node.Priority, minChild.Priority) <= 0)
{
break;
}
_nodes[nodeIndex] = minChild;
nodeIndex = minChildIndex;
}
_nodes[nodeIndex] = node;
}
В PriorityQueue есть пара интересных оптимизаций. Например, при добавлении множества элементов с помощью public void EnqueueRange(IEnumerable<(TElement Element, TPriority Priority)> items!!) в пустую очередь или при создании очереди из множества элементов фактически коллекция копируется в исходном виде в _nodes, а уже потом массив _nodes один раз перестраивается в кучу с помощью приватного метода Heapify, который строит кучу за один проход. Это позволяет избежать новых перестроений и расширения кучи, как происходило бы при поэлементном добавлении новых значений.
private void Heapify()
{
int lastParentWithChildren = GetParentIndex(_size - 1);
if (_comparer == null)
for (int index = lastParentWithChildren; index >= 0; --index)
MoveDownDefaultComparer(_nodes[index], index);
else
for (int index = lastParentWithChildren; index >= 0; --index)
MoveDownCustomComparer(_nodes[index], index);
}Метод EnqueueDequeue сравнивает добавляемый элемент с текущим корневым элементов. Если добавляемый элемент имеет меньший приоритет, то он сразу будет извлечен и перестроения кучи не понадобится, а если нет — то вместо двух перестроений для извлечения и добавления элемента понадобится только одно:
public TElement EnqueueDequeue(TElement element, TPriority priority)
{
// Если очередь пустая, то сразу вернется добавляемый элемент
if (_size != 0)
{
(TElement Element, TPriority Priority) root = _nodes[0];
if (_comparer == null)
{
// Если приоритет добавляемого элемента меньше приоритета корневого,
// то куча не будет перестраиваться
if (Comparer<TPriority>.Default.Compare(priority, root.Priority) > 0)
{
MoveDownDefaultComparer((element, priority), 0);
_version++;
return root.Element;
}
}
else
{
// Если приоритет добавляемого элемента меньше приоритета корневого,
// то куча не будет перестраиваться
if (_comparer.Compare(priority, root.Priority) > 0)
{
MoveDownCustomComparer((element, priority), 0);
_version++;
return root.Element;
}
}
}
return element;
}Да кто такой этот ваш UnorderedItemsCollection
У новой PriorityQueue есть свойство, которое возвращает элементы очереди в неупорядоченном виде. Но возвращает свойство не массив или енумератор, а вложенный в очередь тип UnorderedItemsCollection. Всё из-за специального енумератора, который отслеживает, что очередь не изменилась во время перебора (не изменилась переменная _version, а перечисление не вышло за пределы очереди) поскольку внутренний массив содержит capacity элементов, а не _size элементов.
public bool MoveNext()
{
PriorityQueue<TElement, TPriority> localQueue = _queue;
if (_version == localQueue._version && ((uint)_index < (uint)localQueue._size))
{
_current = localQueue._nodes[_index];
_index++;
return true;
}
return MoveNextRare();
}
private bool MoveNextRare()
{
if (_version != _queue._version)
throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
_index = _queue._size + 1;
_current = default;
return false;
}Итератор перебирает элементы внутреннего представления кучи _nodes, так что говорить, что UnorderedItemsCollection действительно Unordered не совсем правильно. На самом деле, итератор будет всегда упорядочен в соответствии с правилами хранения 4-арной min-кучи в массиве.
(Очевидные?) ограничения
TPriority может быть любым типом, в том числе изменяемым. Можно, например, сделать такую очередь:
public class TaskPriority
{
public TaskPriority(int businessValue)
{
BusinessValue = businessValue;
}
public int BusinessValue { get; set; }
}
public class TaskPriorityComparer : IComparer<TaskPriority>
{
public int Compare(TaskPriority x, TaskPriority y) => x.BusinessValue.CompareTo(y.BusinessValue);
}
var queue = new PriorityQueue<string, TaskPriority>(new TaskPriorityComparer());И очередь перестраивает кучу при каждой операции. Но, например, при извлечении элемента куча будет перестраиваться только после извлечения элемента с минимальным приоритетом, даже если приоритет другого элемента изменился и стал минимальным:
var mutablePriority = new TaskPriority(30);
queue.Enqueue("Фронтенд", new TaskPriority(10));
queue.Enqueue("Бэкенд", new TaskPriority(20));
queue.Enqueue("CI", mutablePriority);
mutablePriority.BusinessValue = 5;
queue.Dequeue(); // (Фронтенд, 10)
queue.Dequeue(); // (CI, 5)
queue.Dequeue(); // (Бэкенд, 20)При добавлении нового элемента куча перестраивается только до уровня, который нужен добавляемому элементу и всё ломается ещё сильнее:
var mutablePriorityCI = new TaskPriority(30);
var mutablePriorityDocs = new TaskPriority(40);
queue.Enqueue("Фронтенд", new TaskPriority(10));
queue.Enqueue("Бэкенд", new TaskPriority(20));
queue.Enqueue("CI", mutablePriorityCI);
queue.Enqueue("Документация", mutablePriorityCI);
mutablePriorityCI.BusinessValue = 5;
mutablePriorityDocs.BusinessValue = 15;
queue.Enqueue("Тесты", new TaskPriority(12));
queue.Dequeue(); // (Фронтенд, 10)
queue.Dequeue(); // (CI, 5)
queue.Dequeue(); // (Документация, 15)
queue.Dequeue(); // (Тесты, 12)
queue.Dequeue(); // (Бэкенд, 20)Поэтому ну их изменяемые приоритеты, лучше используйте для TPriority что-нибудь иммутабельное.
Хорошая новость об этом ограничении: в план работ по .NET 7 добавлен issue, позволяющий работать с элементами с изменяемым приоритетом.
