Структуры данных для приложений реального времени

Question

Мы разрабатываем p2p-приложения, использующие c ++, которые передают голос другому пиру, используя UDP.

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

• Реализация очереди с использованием связанного списка, который поддерживает очередь из объектов OneSecVoice или Image в случае изображения.

• Реализация очереди с использованием статического массива OneSecVoice или Image объектов

OneSecVoice/Image объекты будут содержать общее количество пакетов , пакеты буфер для этого конкретного Image/OneSecVoice.

Поскольку в режиме реального времени один поток будет непрерывно сканировать очередь и извлекает последние завершенные Image/OneSecVoice, выталкивая Image/OneSecVoice из очереди.

Итак, что выбрать Реализация очереди с использованием связанного списка или Реализация очереди с использованием статического массива .

Я и мой друг ссоримся из-за этого, поэтому мы решили опубликовать здесь.

Answer 1

Я бы использовал boost :: round_buffer . Вы получите преимущества кэша с фиксированной областью памяти и без неожиданных выделений памяти.

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

1. Использование фиксированной памяти и неявное или неожиданное распределение памяти.
2. Быстрая вставка в постоянное время и удаление элементы спереди и сзади.
3. Быстрый постоянный произвольный доступ элементы.
4. Пригодность для приложений, критичных для реального времени и производительности.

Возможные применения циркуляр_буфер включает:

• Хранение самых последних полученных сэмплы, перезаписывая самые старые по мере поступления новых сэмплов.
• как базовый контейнер для ограниченного буфера (см. Пример ограниченного буфера).
• Тип кеша, хранящий указанное количество последние вставленные элементы.
• Эффективная фиксированная емкость FIFO (First In, First Out) или LIFO (Last In, First Out) очередь, которая удаляет самые старые (вставляется как первый) элементы при заполнении.

Answer 2

Не реализуйте тоже. Используйте уже существующие реализации в стандартной библиотеке:

std::queue<T, std::list<T> >
std::queue<T, std::deque<T> > // uses deque by default, by the way

Вы можете ввести их, чтобы сделать их замену очень простой:

template <typename T>
struct queue_list
{
    typedef typename std::queue<T, std::list<T> > value_type;
}

template <typename T>
struct queue_array
{
    typedef typename std::queue<T, std::deque<T> > value_type;
}

typedef queue_list<the_type>::value_type container_type; // use one
typedef queue_array<the_type>::value_type container_type;

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

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

typedef typename std::queue<T, std::list<T, boost::pool_allocator<T> > > value_type;

Еще одна структура, которую стоит попробовать, это boost::circular_buffer, как предложено fnieto :

template <typename T>
struct queue_buffer
{
    typedef typename std::queue<T, boost::circular_buffer<T> > value_type;
}    

Answer 3

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

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

Если вы хотите ограничить размер, до которого он может расти, вы можете сделать это в любой схеме.

Answer 4

Связанный список будет каноническим подходом: «Реализация очереди с использованием статического массива» - это на самом деле то, как я бы поступил - чтобы собрать пакеты udp, а затем, вероятно, передать последовательные данные в LL, чтобы они были упорядочены. Как вы собираетесь танцевать «постоянно сканируйте очереди и вынимайте последние завершенные», поскольку вы не можете просто вставить их туда, поскольку udp может прийти в непредвиденной последовательности. Последнее завершение не означает, что «Кофе» следует после «Тип бобов:», так что вы можете где-то запутать некоторые запутанные бобы.