В этой статье я покажу очередь с приоритетом с использованием linked list. Алгоритм простой и позволяет получить приоритетные сообщения раньше, чем остальные сообщения.
Я сначала поискал в интернете реализацию такого алгоритма. Первое, что я нашел, это решение на c++ с обычными массивами. То есть создается шаблонный класс и в нем создается два массива, один для чисел, другой для приоритетности. Мне показалось, что решение не очень хорошее, потому что при добавлении нового числа, создается новый массив и из старого копируются данные в новый массив. Чем больше очередь, тем больше копирования каждый раз. Ещё проблема при использовании массива - это что нельзя использовать в другом потоке очередь, пока ты не выполнишь полностью функцию вставки данных в очередь, так как смениться указатель на массив и так далее.
Алгоритм - очередь с приоритетом достаточно простой, мы создаем структуру, я опять буду показывать пример кода на C, и входящие данные будут числа. Итак.
struct queue {
unsigned long number;
unsigned long priority;
struct queue *parent;
struct queue *child;
};Также создаем глобальный указатель на начало очереди, прошу заметить, это всего лишь пример, разумеется в C++ можно создать это в классе, но так как в C будет только одна очередь, то она становиться глобальной как само собой разумеющееся. И также создаем pri указатель на указатель. Он будет хранить хвост каждого приоритета, чтобы можно было в linked-list сразу в нужное место всегда добавлять новые данные.
struct queue *root;
struct queue **pri;теперь создаем функцию и начальные значения. Здесь мы также ищем близжайший приоритет. например если у нас первым был приоритет 20, потом 14, а теперь 10. то мы линейно доходим до 14 и становимся в его хвост и добавляемся уже рядом с ним.
static void add_number (int number, int priority, int max)
{
register struct queue *n = root;
register struct queue *prev = NULL;
register struct queue *temp = NULL;
register struct queue *temp1 = NULL;
int prr = priority + 20;
while ((n = pri[prr]) == NULL)
{
prr++;
if (prr >= max) break;
}
if (n == NULL) n = root;Теперь можно в бесконечном цикле идти по списку и добавлять в нужную позицию наше число. Начнем с того, если указатель n равен нулю.
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
if (prev)
{
prev->child = n;
n->parent = prev;
}
pri[priority + 20] = n;
if (root == NULL) root = n;
return;
}Здесь в указываем чтобы root указывал на него как на начало. Отсюда начнется следующий отсчет.
Далее мы смотрим, если добавляемый приоритет выше, чем наше сообщение в очереди, то перед ним установим новый приоритет.
while (n->priority < priority)
{
temp = n;
prev = n;
n = n->parent;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->child = temp;
temp->parent = n;
root = n;
pri[priority + 20] = n;
return;
}
}Также можно заметить, что в этом случае root опять меняет свою позицию, указав себя как начало в списке.
Далее смотрим если добавляемый приоритет ниже чем текущий приоритет.
while (n->priority > priority)
{
temp = n;
prev = n;
n = n->child;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
temp->child = n;
pri[priority + 20] = n;
return;
} else if (n->priority <= priority)
{
temp = n->parent;
temp1 = n;
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
n->child = temp1;
temp->child = n;
temp1->parent = n;
pri[priority + 20] = n;
return;
}
}Здесь всё должно быть понятно, что мы добавляем наше число куда нужно.
И осталось последнее.
while (n->priority == priority)
{
temp = n;
prev = n;
n = n->child;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->child = NULL;
n->parent = n;
temp->child = n;
pri[priority + 20] = n;
return;
} else if (n->priority != priority)
{
temp = n->parent;
temp1 = n;
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
n->child = temp1;
pri[priority + 20] = n;
return;
}
}Здесь мы смотрим, если он равен нашему приоритету, то дадим сначала выйти из очереди первому добавленному с таким приоритетом, а этот добавим за ним.
Теперь создадим функцию по выдачи из очереди нашего числа.
static int get_number_from_queue ()
{
if (!root) return -1;
register struct queue *n = root;
root = root->child;
register unsigned long number = n->number;
free (n);
return number;
}Всё, здесь мы выдаем номер и смещаем наш root. Так как это без много поточности, то здесь я не использовал мьютексы, но по хорошему, нужно поставить мьютекс на смену root и всё.
Теперь создадим остальное.
struct arr {
int num;
int priority;
} arr[] = {
{ -14, -14},
{ -4, -4},
{ 0, 0 },
{ 1, 1 },
{ 2, 2 },
{ 3, 3 },
{ 4, 4 },
{ 14, 14 },
{ 5, 5 },
{ 5, 5 },
{ 6, 6 },
{ 7, 7 },
{ 8, 8 },
{ 9, 9 },
{ 10, 10 }
};
int main (int argc, char **argv)
{
pri = calloc (41, sizeof (struct queue *));
for (int i = 0; i < 41; i++)
{
pri[i] = NULL;
}
int size = sizeof (arr) / sizeof (struct arr);
for (int i = 0; i < size; i++)
{
add_number (arr[i].num, arr[i].priority);
}
for (int i = 0; i < size; i++)
{
printf ("%d: %d\n", i, get_number_from_queue());
}
}Чтобы было удобней проверить код, то выкладываю полный код.
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
struct queue {
unsigned long number;
long priority;
struct queue *parent;
struct queue *child;
};
struct queue *root;
struct queue **pri;
static void add_number (int number, int priority)
{
register struct queue *n = root;
register struct queue *prev = NULL;
register struct queue *temp = NULL;
register struct queue *temp1 = NULL;
int prr = priority + 20;
while ((n = pri[prr]) == NULL)
{
prr++;
if (prr >= max) break;
}
if (n == NULL) n = root;
while (1)
{
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
if (prev)
{
prev->child = n;
n->parent = prev;
}
pri[priority + 20] = n;
if (root == NULL) root = n;
return;
}
while (n->priority < priority)
{
temp = n;
prev = n;
n = n->parent;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->child = temp;
temp->parent = n;
root = n;
pri[priority + 20] = n;
return;
}
}
while (n->priority > priority)
{
temp = n;
prev = n;
n = n->child;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
temp->child = n;
pri[priority + 20] = n;
return;
} else if (n->priority <= priority)
{
temp = n->parent;
temp1 = n;
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
n->child = temp1;
temp->child = n;
temp1->parent = n;
pri[priority + 20] = n;
return;
}
}
while (n->priority == priority)
{
temp = n;
prev = n;
n = n->child;
if (n == NULL)
{
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->child = NULL;
n->parent = n;
temp->child = n;
pri[priority + 20] = n;
return;
} else if (n->priority != priority)
{
temp = n->parent;
temp1 = n;
n = calloc (1, sizeof (struct queue));
n->number = number;
n->priority = priority;
n->parent = temp;
n->child = temp1;
pri[priority + 20] = n;
return;
}
}
}
}
static int get_number_from_queue ()
{
if (!root) return -1;
register struct queue *n = root;
root = root->child;
register unsigned long number = n->number;
free (n);
return number;
}
struct arr {
int num;
int priority;
} arr[] = {
{ -14, -14},
{ -4, -4},
{ 0, 0 },
{ 1, 1 },
{ 2, 2 },
{ 3, 3 },
{ 4, 4 },
{ 14, 14 },
{ 5, 5 },
{ 5, 5 },
{ 6, 6 },
{ 7, 7 },
{ 8, 8 },
{ 9, 9 },
{ 10, 10 }
};
int main (int argc, char **argv)
{
pri = calloc (41, sizeof (struct queue *));
for (int i = 0; i < 41; i++)
{
pri[i] = NULL;
}
int size = sizeof (arr) / sizeof (struct arr);
for (int i = 0; i < size; i++)
{
add_number (arr[i].num, arr[i].priority);
}
for (int i = 0; i < size; i++)
{
printf ("%d: %d\n", i, get_number_from_queue());
}
}разумеется надо знать какие приоритеты доступны, то есть например я выбираю, что доступны приоритеты от -20 до 20. создаю массив pri и заполняю нулями указатели. Когда мы вставляем новое число с приоритетом, то оно сравнивается, есть ли такой приоритет, если есть, то мы попадаем сразу в конец этого приоритета и добавляем свой.
Комментарии (14)
Politura
21.11.2021 10:02+13Для очереди с приоритетом используют двоичные кучи, по-сравнению с linked list здесь следующие преимущества:
Добавление элемента в сортированный linked list дает линейную сложность, тогда как двоичная куча - логарифмическую. То есть, имея очередь из миллиона элементов, чтоб добавить элемент в конец для linked list понадобится миллион итераций, а для кучи - всего 20.
Кучу очень удобно хранить в массиве что приводит к существенно меньшему количеству ре-аллокаций памяти, по сравнению с linked list. Ну и в целом данные будут компактнее, т.к. нет нужны для каждого элемента хранить адрес следующего элемента.
Я думаю то, что вы видели пример с массивом, на самом деле был пример с кучей. И в случае с массивом нет нужны при каждом новом элементе увеличивать его всего на один элемент. Обычно увеличивают в 2 раза, просто используется не все место сразу.
На хабре есть хорошие статьи про кучи, например эта: https://habr.com/ru/post/112222/ очень понятно рассказывает на пальцах как она работает, с примерами кода и где чаще всего применяется.
demotu
21.11.2021 23:32Если говорить про типичную реализацию связанного списка как стуктуры данных, а не как АТД (т.е. память под каждый элемент выделяется отдельно и связаны они через указатели), то как раз для списка реалокаций памяти не будет совсем (будут только аллокации для элементов списка). Для массива же придется иногда делать реалокации и это его недостаток (если не выделять память с запасом). Компенсируется это тем, помимо прочего, что данные лежат плотно, а это хорошо для кеш-памяти процессора - он может легко предсказать адрес следующей порции данных и загрузить её в кеш до того как она фактически понадобится в вычислениях.
xverizex Автор
21.11.2021 23:37ну вот смотрите, в массиве в некоторых случаях как я понял, нужно копировать из одного массива в другой все элементы, это разве правильно? в моем случае ничего копировать не надо. ну конечно это я поменял немного алгоритм, посмотрите как стало и да, можете привести пример алгоритма вашего, чтобы я сравнил?
wataru
22.11.2021 12:54Да, при исчерпании capacity придется копировать весь массив. Но за счет одной маленькой хитрости можно добиться, что это копирование произойдет O(1) для каждого элемента. Практически бесплатно, если учесть огромное увеличение скорости работы с массивом засчет локальности данных.
Хитрость называется "удвоение" — вы каждый раз, когда вам надо копировать массив, выделяете памяти в 2 раза больше текущего. Тогда следующий раз копировать массив придется совсем не скоро. При добавлении n элементов в массив за время работы программы будет максимум log(n) копирований массива. А если учесть размеры копируюмых массивов, то получится суммарно O(n) копирований элементов.
На практике используют не 2, а какой-то меньший множитель. Скажем, 1.7, но это принципиально ничего не меняет.
amarao
21.11.2021 18:13очереди с приоритетом используют min heap (https://en.wikipedia.org/wiki/Binary_heap), и насколько я знаю, это общепризнанно самый быстрый метод.
Списки точно медленные, потому что шмотки памяти, которые вам выглядят как элементы списка, на самом деле, внутри вот это: https://sourceware.org/glibc/wiki/MallocInternals и там мнооого всего.
aamonster
21.11.2021 22:38Точно min heap, кстати? Я тут погуглил на предмет аналогов кучи с устойчивой сортировкой (элементы с одним приоритетом – в FIFO), так наткнулся на интересную конструкцию: The Bently-Saxe method, https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap
Не гарантирует худшее время (но амортизированное Ok), зато stable sort и вроде даже проще кучи.
sergio_nsk
22.11.2021 04:19Ключевое слово `register` - устаревшее. Сейчас он не оказывает никого эффекта на компилятор. Он знает лучше.
Очень много повторяющегося кода с незначительными измененями в правой части присваиваний - кандидат на отдельную фунцию. Её можно полностью протестировать. Без неё - есть верояность ошибки при копировании.
Shiny2
22.11.2021 13:48-3Пипец, чувак нашёл общий паттерн и обернул его во что-то осмысленное, набежали деды и заминусили, хабр как он есть
Druj
22.11.2021 14:00+2Какой общий паттерн? Во что осмысленное он обернут? По факту написан абзац текста и куча простого кода которую автор ещё и продублировал, зачем — непонятно, ценность — нулевая. Минусы осуждаю, но в комментариях пояснили правильно. Да, хабр как он есть.
aamonster
Я не знаю, как вы искали, но в C++ из коробки есть std::priority_queue.
ЗЫ: ну а linked list... Никто не использует его в качестве контейнера, это медленно. Максимум – "прошнуровывают" данные, хранящиеся где-то ещё.
xverizex Автор
вы можете сказать чем мой вариант медленней чем решение с массивами? Мне просто такое тестовое задание хотели дать на собеседовании, но не дали.
aamonster
Я так и не понял, что именно вы нашли. Наивное решение с "раздвиганием" массива, что ли? Самое смешное – оно, как и ваше, работает за O(n), и не поручусь даже, что в среднем медленнее (данные лежат компактно – это преимущество)
Упомянутая тут же двоичная куча гарантирует вставку за O(log n). У неё, правда, есть недостаток – если придёт несколько элементов с одним приоритетом, то не факт, что они выйдут в том же порядке (типа unstable sort). Но для многих задач это неважно, а при необходимости можно решить так же, как для сортировки – заменив приоритет на пару (приоритет, номер по порядку), сортируемую лексикографически.
Для конкретных же задач есть свои решения. Например, если уровней приоритета мало – выгодно сделать несколько простых очередей по уровням.
А вообще прочитайте Кнута, на многие вопросы появятся базовые ответы, сможете с ходу подбирать если не оптимальное, то приемлемое решение.
xverizex Автор
Я улучшил алгоритм, посмотрите, если интересно. Теперь он работает быстрее. я сделал что приоритет можно устанавливать от -20 до 20. если у нас уже есть такой приоритет, то мы добавляемся в хвост последнему, если нет, то просто по массиву пробегаемся и потом к root устанавливаемся. Я пока думаю над этим решением, но оно теперь почти не ходит по указателям как в linked list, но в тоже время им считается. Можете показать алгоритм с двоичной кучей, который вы приводите за log n? я бы сравнил эту реализацию с моей.
Druj
Биномиальная на указателях из gcc
Бинарная на массиве из rust std
Если без шуток то: бинарная, биномиальная