Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 08:01
Оценка:
Добрый день.
Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи? Гугл пока не помог, видимо потому что "правильно сформулированный вопрос — уже половина ответа", а я не могу его сформулировать

Заранее благодарю за ответы.
Re: Heap?
От: Qbit86 Кипр
Дата: 17.06.16 08:40
Оценка: 2 (1)
Здравствуйте, Tujh, Вы писали:

T>Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи?


Возможно, тебе подойдёт куча. Операция произвольного доступа по ключу (порядковому номеру) тебе всё равно вряд ли нужна. А поиск минимума (самого раннего из последних 16 сообщений), возможно, пригодится.
Глаза у меня добрые, но рубашка — смирительная!
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: szag  
Дата: 17.06.16 08:40
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Добрый день.

T>Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи? Гугл пока не помог, видимо потому что "правильно сформулированный вопрос — уже половина ответа", а я не могу его сформулировать

T>Заранее благодарю за ответы.

непонятно зачем нужна сортировка, мы подобную задачу решаем через вектор, который заполняется (в вашем случае) по айди пакета
vector<int> vec;
vec.resize(10);

vec[2] = ... // пакет с айди 2
vec[5] = .. // пакет с айди 5
Re[2]: Вектор
От: Qbit86 Кипр
Дата: 17.06.16 08:44
Оценка:
Здравствуйте, szag, Вы писали:

S>непонятно зачем нужна сортировка, мы подобную задачу решаем через вектор, который заполняется (в вашем случае) по айди пакета

S>
S>vector<int> vec;
S>vec.resize(10);
S>vec[5] = .. // пакет с айди 5


vec[19937] = .. // пакет с айди 19937?
Глаза у меня добрые, но рубашка — смирительная!
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 17.06.16 08:46
Оценка: +3
Здравствуйте, Tujh, Вы писали:

T>Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов.


По моим ощущениям, с учетом того что тебе нужны N последних пакетов, искомая структура данных это циклический буффер. Его можно взять прямиком из BOOST
// Create a circular buffer with a capacity for 3 integers.
boost::circular_buffer<int> cb(3);

// Insert threee elements into the buffer.
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);

int a = cb[0];  // a == 1
int b = cb[1];  // b == 2
int c = cb[2];  // c == 3

// The buffer is full now, so pushing subsequent
// elements will overwrite the front-most elements.

cb.push_back(4);  // Overwrite 1 with 4.
cb.push_back(5);  // Overwrite 2 with 5.

// The buffer now contains 3, 4 and 5.
a = cb[0];  // a == 3
b = cb[1];  // b == 4
c = cb[2];  // c == 5
Re[2]: Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 09:18
Оценка:
Здравствуйте, szag, Вы писали:
S>непонятно зачем нужна сортировка
Это же UDP , легко пакет "10" может придти раньше пакета "1", а затем придут "3", "8", "2", "5" и "9", а "4", "6" и "7" вообще потеряются по дороге.
Re[2]: Heap?
От: Tujh Голландия  
Дата: 17.06.16 09:24
Оценка:
Здравствуйте, Qbit86, Вы писали:

Q>Возможно, тебе подойдёт куча.

О, как-то я об этом вообще забыл, но там опять же "древесная" сортировка вроде, сейчас почитаю по подробнее.

Q>Операция произвольного доступа по ключу (порядковому номеру) тебе всё равно вряд ли нужна. А поиск минимума (самого раннего из последних 16 сообщений), возможно, пригодится.

Не возможно, а именно это и надо, ещё поиск потерянного пакета, но отдельная тема.
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: BulatZiganshin  
Дата: 17.06.16 09:27
Оценка:
Здравствуйте, Tujh, Вы писали:

T> Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов.


если тебе нужна только вставка и извлечение пакета с мин. номером, то наиболее эффективен несортированный вектор, на втором месте — сортированный
Люди, я люблю вас! Будьте бдительны!!!
Re[2]: Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 09:31
Оценка:
Здравствуйте, kaa.python, Вы писали:

KP>По моим ощущениям, с учетом того что тебе нужны N последних пакетов, искомая структура данных это циклический буффер.

В первую очередь мне нужны отсортированные пакеты, а количество — дело второе. Так бы и обычная дека подошла, но за напоминание — спасибо, я буст плохо знаю, было пару моментов когда делали проект на нём, столкнулся с некоторыми очень специфическими особенностями (вряд ли кто-то столкнётся, так как проблема была в комплексе с оборудованием и на обычном компе вряд ли проявится, поэтому нет смысла описывать) и больше не смотрел. Почитаю, может найду что подходящее моеё задаче
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: Zhendos  
Дата: 17.06.16 09:35
Оценка: 2 (1)
Здравствуйте, Tujh, Вы писали:

T>Добрый день.

T>Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его.


[url=http://en.cppreference.com/w/cpp/container/priority_queue][priority_queue] ?
Re[3]: Использование std::map для сортировки сообщений в реал-тайм?
От: uzhas Ниоткуда  
Дата: 17.06.16 09:48
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Это же UDP , легко пакет "10" может придти раньше пакета "1", а затем придут "3", "8", "2", "5" и "9", а "4", "6" и "7" вообще потеряются по дороге.


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

в зависимости от этого уже можно было бы тюнить
стандартные контейнеры, которые могут пригодиться
1) queue
2) priority_queue (heap)
3) curcular_buffer
4) flat_map (sorted_vector)
5) map (probably with custom allocator if number of elemements is not high)
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: chaotic-kotik  
Дата: 17.06.16 10:06
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи? Гугл пока не помог, видимо потому что "правильно сформулированный вопрос — уже половина ответа", а я не могу его сформулировать


Существует множество алгоритмов, способных решить эту проблему. Как уже писали, можно использовать priority queue, можно класть в map, если мап небольшой, то вставка и удаление будут выполняться быстро. Помимо этого можно воспользоваться тем, что UDP пакеты чаще всего будут приходить упорядоченными — тупо складывать все в вектор/дек/циклический буфер и потом досортировывать, если что-то пришло не по порядку. Можно сортировать любым адаптивным алгоритмом сортировки (например с помощью shell sort или даже insertion sort) и получить сложность сортировки O(N), так как у тебя будет практически отсортированный массив.
Re[3]: Вектор
От: szag  
Дата: 17.06.16 10:16
Оценка:
Здравствуйте, Qbit86, Вы писали:

Q>
vec[19937] = .. // пакет с айди 19937?


получение айли пакета зависит от логики, конечно он не 1 в 1 запрашивается из мапа. Ниже уже предлагали circular buffer, по сути тоже самое можно сделать на векторе, если есть понимае как обрабатываются пакеты и прочая БЛ.
Re[3]: Использование std::map для сортировки сообщений в реал-тайм?
От: szag  
Дата: 17.06.16 10:17
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Здравствуйте, szag, Вы писали:

S>>непонятно зачем нужна сортировка
T>Это же UDP , легко пакет "10" может придти раньше пакета "1", а затем придут "3", "8", "2", "5" и "9", а "4", "6" и "7" вообще потеряются по дороге.
это не важно, при каком условии и как вы используете пакеты? что делаете в случае потери пакетов и как детектите потерю?
Re[4]: Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 10:24
Оценка:
Здравствуйте, uzhas, Вы писали:

U>в чем цель контейнера пакетов? вы там складируете те пакеты, очередность которых еще не определена и которые не готовы к обработке?

Да.

U>а как определяется потеря пакета 6? по таймауту, начатому от момента получения пакета с бОльшим номером ?

Пока, просто по приходу пяти пакетов с бОльшими номерами. Дальше включается механизм восстановления пакетов из уже полученных и приход настоящего пакета "6" уже может быть проигнорирован.

U>тут можно сделать закладки на статистические моменты — как часто теряются пакеты и как часто они перемешиваются и даже если перемешиваются, то как глубоко

Думал об этом, но не представляю как это сделать, так как сфера применения не однородная. В самом простом случае — потом данных непосредственно по WiFi от источника (возможны потери, но маловероятно перемешивание), средний вариант — с использованием промежуточного звена в виде радиомодема (много потерь, маловероятно перемешивание) и самый сложный вариант — трансляция потока через Интернет не на постоянной площадке, как пример — репортажная съёмка в реал-тайм с вещанием на постоянный сервер, то есть точка вещания постоянно перемещается и условия передачи данных различаются в каждом конкретном случае.

U>в зависимости от этого уже можно было бы тюнить

Эх, знать бы ещё что тюнить

U>1) queue

Нет порядка пакетов

U>2) priority_queue (heap)

Уже подсказали про heap, почитал, сейчас склоняюсь к этому варианту.

U>3) curcular_buffer

Опять же — не будет соблюдён порядок, да и размер "буфера" не так критичен что бы циркулярку использовать.

U>4) flat_map (sorted_vector)

Сейчас так и есть.

U>5) map (probably with custom allocator if number of elemements is not high)

Постоянная пересортировка дерева в мапе как-то напрягает, может зря, поэтому и возник вопрос.
Re[4]: Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 10:32
Оценка:
Здравствуйте, szag, Вы писали:

S>это не важно, при каком условии и как вы используете пакеты? что делаете в случае потери пакетов и как детектите потерю?

для меня порядок важен, детектируется пока по приходу пяти пакетов с бОльшим номером чем ожидаемый. В случае обнаружения потерянного предпринимается попытка его восстановить по дополнительной информации в уже принятых пакетах.
Re: Использование std::map для сортировки сообщений в реал-тайм?
От: so5team https://stiffstream.com
Дата: 17.06.16 10:38
Оценка:
Здравствуйте, Tujh

Походу, у вас никакой не реал-тайм, ибо в реал-тайме вас бы волновали вопросы работы с динамической памятью. Обычно в реал-тайм задачах динамическая память не используется, т.к. поведение аллокаций/деаллокаций плохопредсказуемо. А т.к. std::map со аллокатором по-умолчанию работает именно через динамическую память, то применение std::map в действительно реал-тайме под вопросом именно по этому параметру.

Что до вашего вопроса, то за время, пока вы его обсуждаете на RSDN, уже можно было написать несколько простейших бенчмарков и сравнить поведение std::map, vector (сортированный и несортированный), priority_queue (он же heap), circular_buffer и иже с ними. Ведь никто из форумчан не знает ни объема ваших данных, ни платформы, ни компилятора, ни библиотек, которые у вас в наличии.
Re[5]: Использование std::map для сортировки сообщений в реал-тайм?
От: szag  
Дата: 17.06.16 10:42
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Здравствуйте, szag, Вы писали:


S>>это не важно, при каком условии и как вы используете пакеты? что делаете в случае потери пакетов и как детектите потерю?

T>для меня порядок важен, детектируется пока по приходу пяти пакетов с бОльшим номером чем ожидаемый. В случае обнаружения потерянного предпринимается попытка его восстановить по дополнительной информации в уже принятых пакетах.
так это можно сделать и без знания порядка сохраненных пакетов, тут важно, что в пакетах образовалась дырка и что пришло n пакетов, которые эту дырку еще не закрыли.
А вообще, вы точно уврены, что текущее ваше решение слишком медленное? пробовали нагрузочные тесты? Какой-нибудь performance analyzer? В 90% случаев самое простое решение и есть самое лучшее.
Re[2]: Использование std::map для сортировки сообщений в реал-тайм?
От: Tujh Голландия  
Дата: 17.06.16 11:05
Оценка:
Здравствуйте, so5team, Вы писали:

S>Здравствуйте, Tujh


S>Походу, у вас никакой не реал-тайм

Если имеется в виду RTOS и QNX то да, у меня обычный Embedded Linux. Аллокатор скорее будет свой, так как embedded, хотя там куча высокоуровневой обвязки на Java будет (не моё решение), поэтому вот вообще не могу сказать по этому поводу.

S>Что до вашего вопроса, то за время, пока вы его обсуждаете на RSDN, уже можно было написать несколько простейших бенчмарков

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

S>Ведь никто из форумчан не знает ни объема ваших данных, ни платформы, ни компилятора, ни библиотек, которые у вас в наличии.

Это понятно, вопрос скорее обобщённый, на "поспрашивать про опыт других".
Re[5]: Использование std::map для сортировки сообщений в реал-тайм?
От: uzhas Ниоткуда  
Дата: 17.06.16 11:11
Оценка:
Здравствуйте, Tujh, Вы писали:

T>Постоянная пересортировка дерева в мапе как-то напрягает, может зря, поэтому и возник вопрос.


тут нужен профайлер.
в целом, если в мапе мало элементов, то перебалансировка не будет жрать ресурсы, тут уже жрет new/delete, именно поэтому порекомендовал использовать аллокатор с free list. для частых вставок\удалений очень шустро работает. если еще аллокатор выделяет сразу страницами по несколько узлов, то еще и локализация данных будет хорошей, что хорошо сказывается на скорость пробега по дереву (косвенные переходы между узлами)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.