Тест реализации очередей

Question

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

Чтобы сузить область, я в основном использую C, но я могу использовать C ++, stl и любую библиотеку. У меня есть несколько обращений к библиотекам структур данных, таким как GLib и C-Generic-Library , и, конечно, к контейнерам STL. Кроме того, если кто-либо из вас разработал / знает более быструю очередь, чем те, пожалуйста, сообщите:)

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

Answer 1

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

Без необходимости блокировать очередь (не нужно беспокоиться о других потоках), простой кольцевой буфер будет трудно превзойти по производительности. Если по какой-то причине очередь должна увеличиваться после создания, это немного сложнее, но вам не составит труда найти реализацию очереди с циклическим буфером (или создать свою собственную). Если либо вставка, либо извлечение выполняются в обработчике сигналов (или в подпрограмме обработки прерываний), вам, возможно, потребуется защитить индексы позиций чтения и / или записи, но если вы хорошо знаете свою цель, вы можете определить, что это не так. случай (когда сомневаешься защищать, хотя). Защитой будет либо временная блокировка сигналов, либо прерывания, которые могут поставить вещи в вашу очередь. (Вам действительно нужно заблокировать это, если вам необходимо изменить размер очереди)

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

У меня нет каких-либо реальных тестов и я не могу давать никаких предложений о каких-либо реализациях библиотеки, но оба метода O (1) для вставки и извлечения. Первый - более дружественный кэш (и пейджер памяти), если размер вашей очереди не намного больше, чем нужно. Второй метод менее дружествен к кешу, поскольку каждый член очереди может находиться в другой области ОЗУ.

Надеюсь, это поможет вам оценить или создать собственную очередь.