Комментарии 16
Переоткрытие кольцевого буфера...
Но мы же статьи пишем не только о новых вещах. Если бы были статьи только о новом, то не было бы статей и переводов об уроках по opengl и т.д.
Ага, и начинаем их со слов "ко мне пришла идея", чтобы все знали, кто эти вещи изобрёл :-D
Так тип данных DeQueue или RingBuffer? У них совершенно разная семантика, время доступа к элементам, требования по памяти и разное поведение при переполнении (кольцевого буффера).
del
По-хорошему размеры лучше делать не интами, а size_t
. Из queue_add
возвращать результат, по которому можно узнать, произошла ли ошибка. Например, можно bool
возвращать. Ещё такой момент - создам я очередь, добавлю в неё элемент, тогда q->high
будет равен нулю. Однако, в queue_get
есть такая строчка: `uint8_t a = q->data[q->high--];
, которая сразу приведёт к неверному результату. Плюс неплохо было сделать функцию для освобождения памяти, которую использует очередь
Upd: Сразу не заметил, что вы использовали двойное присваивание `q->low = q->high = size-1`
Upd 2: Очередь с приоритетом страдает от тех же ошибок, что и без приоритета. Плюс ещё парочка замечаний:
queue_get
должен явно сигнализировать, что очередь пуста, а не только в консоль об этом писать.
for (int i = 0; i < size_prio; i++) {
q->data[i] = calloc (size, sizeof (uint8_t));
q->low[i] = q->high[i] = size - 1; // А если size_prio > size?
q->max[i] = size; // Тут тоже
}
Для очередей с приоритетами обычно используют другие структуры данных. Однако ваш способ тоже подходит, если приоритетов строго определённое количество. Если же оно не известно, можно использовать следующие структуры данных: двоичная куча, биномиальная куча и другие кучи.
По-хорошему там на calloc разориться можно. По сути идею инкапсуляции данных в объект queue свели к массиву ее мемберов. Смысл такого финта явно в недопонимании того, чего сам на(ш)кодил.
Однако ваш способ тоже подходит, если приоритетов строго определённое количество
желательно ещё и чтобы это количество было небольшим, порядка ln(N) - логарифм от количества элементов, иначе всё равно неэффективно.
Поменял немного код, теперь побыстрее будет работать. Сделал так, чтобы сразу знать с какого приоритета начинать вести поиск в очереди.
"Мда, ничего не скажешь, а остальное вы уже видели..."
Не знаю как мне приходят такие идеи
На собеседовании спросили разве что? ;)
и я не помню как другие реализуют очередь с приоритетом
Алгоритмы, которые можно вот так взять и изобрести за полчаса - уже изобретены в 70-х годах ;)
Результаты маллоков в C всё же принято проверять.
Ну и ещё, если такой кольцевой буфер делать строго в 2^n элементов, то можно обойтись совсем без count, а вместо size будет достаточно маски для младших битов. Далее разветвление: или иметь максимум ровно в 2^n элементов, тогда указатели low и high должны иметь n+1 незамаскированных бит, или иметь 2^n-1 элеметов, тогда low и high имеют n незамаскированных бит.
Тоже баловался таким, на плюсах только.
Очередь с приоритетом обычно делается через кучу, которая является является инвариантом двоичного дерева. Т. Е. Достаточно просто двоичное дерево реализовать, дальше оно само.
Реализация очереди на C