Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Подскажите какую структуру данных выбрать

73K
27 февраля 2012 года
bolt7
33 / / 20.02.2012
Здравствуйте. Стоит такая задача. Приходят данные по сети (на сокет, в канал, почтовый ящик, в общем случае транспорт не имеет значения) в виде сообщений (состоит из несколько служебных полей и сами данные), читаю данные и помещаю их в очередь. Вроде все хорошо когда необходимо последовательно доставать сообщения из очереди, а когда необходимо найти сообщение по одному из служебных полей(например от кого), не знаю как лучше организовать поиск. Тупой перебор делать проходя от начала о конца не вариант если сообщений много, к тому же заполнение очереди производит альтернативный поток, и что бы не повредить данные, приходится блокирывать всю очередь на время поиска. Служебные поля - 2 целых 4байтных числа. Как можно организовать все сообщения в оптимальную, для поиска, систему или есть может какието спец алгоритмы.
79K
28 февраля 2012 года
last_lord
6 / / 27.02.2012
Предлагаю добавить к сообщению "номер пакета", который будет постоянно расти -- маркер.
Сделать отдельную структуру, из служебных полей и номера маркера, сортированную по служебным полям.
Бинарным поиском находишь маркер в добавочной структуре, потом по номеру маркера начального пакета можно вычислить необходимое смещение.

Острые углы: блокировка, переполнение маркера.
73K
28 февраля 2012 года
bolt7
33 / / 20.02.2012
спасибо за предложение, но меня первое что смущает это сортировка (сортируют обычно стичные данные, а тут будут приходить постоянно новые сообщение которые тоже надо будет всунуть на свое место), потом, если я правильно понял, нужно хранить список в массиве, что тоже совсем не хорошо, опять таки будут приходить новые сообщения и удалятся запрашиваемые.
79K
29 февраля 2012 года
last_lord
6 / / 27.02.2012
Тогда можно сделать вспомогательную структуру так:
 
Код:
struct fnd{
    fnd* lnk_prev;
    int sl_1,sl_2;
    int marker; // или void* lnk_message;
    fnd* lnk_next;
};

При поиске придется просматривать все по порядку, но очередь не надо блокирывать.
Для добавления новнового эл-та в цепочку так же придется пройтись поиском.
73K
29 февраля 2012 года
bolt7
33 / / 20.02.2012
а почему не надо блокировать, я не написал в явном виде (мой косяк), что заполнением списка и поиском занимаются разные потоки, если им пригленется один и тот же елемент(добавить после него/забрать как найденный) будет беда. если 2 потока шарятся в ресурсе, для записи, синхронизация нужна в любом случае, или я не правильно понял предложеный метод?
79K
01 марта 2012 года
last_lord
6 / / 27.02.2012
Цитата: bolt7
почему не надо блокировать

Метод вставки. создаем новую fnd. Ищем то место где она должна быть. Заполняем поля новой fnd. Меняем ссылочные поля соседей.
Максимальная ошибка: поток поиска не найдет элемент, вставляемый в данный момент.
Метод удаления. Удаляем fnd, на которую указывает буферный указатель (fnd с прошлрго шага). Ищем удаляемую fnd. Присваиваем буферному указателю ссылку на неё. Меняем ссылочные поля соседей.
Структура таким образом живет до удаления следуюшего сообщения.
Ошибка: поток поиска будет на структуре в момент удаления. После удаления из цепи lnk_next и lnk_prev по прежнему указывают на существующие элементы. Поиск продолжится.
С основной очередью можно поступить так же (я про буфер удаления).

Написал много текста и только сейчас понял суть вопроса.
Сделать по одному буферу удаления удаления в каждом потоке. Поток А проверяет буфер потока Б после вывода fnd из цепочки. Двойной вывод не страшен, а при выполнении условия дублирующая ссылка затирается. Косяк может возникнуть если поток А вклинится в поток Б между проверкой условия и занулением ссылки (обе ссылки занулятся -- утечка памяти), но по мойму это решаемо.

79K
01 марта 2012 года
last_lord
6 / / 27.02.2012
А еще вариант -- потоком поиска просматривать первое сообщение (или 2) основной очереди и если искомое среди них, то отказасться от обработки (ну скоро и так обработается)
73K
01 марта 2012 года
bolt7
33 / / 20.02.2012
Цитата: last_lord
Метод вставки. создаем новую fnd. Ищем то место где она должна быть. Заполняем поля новой fnd. Меняем ссылочные поля соседей.
Максимальная ошибка: поток поиска не найдет элемент, вставляемый в данный момент.


Рассмотрим пример. Поток заполнения нашел место куда вставлять (определенный элемент). И тут его вытиснили. В это время поток поиска наткнулся на этот же элемент и "выковырял" его. Когда первый поток очнется он вставит, оставшийся хвостик к этому элементу, но елемент уже убрали из очереди и вся цепочка за ним потеряется.
Пример 2. Поток заполнения уже меняет ссылки и тут опять его обломали, но он успел хотябы предыдущего соседа направить на себя. Поток поиска проходит все до нашего нового елемента, но так как мы не успели поменять все ссылки, всё что идет за ним нам не известно. В лучшем случае когда вернется первый поток он доделает то, что закончил, и целостность очереди востановится. В худшем случае поток поиска захватит наш новый елемент. Тогда все что было за ним просто пропадет. Зато когда первый опять включится он пропавший конец привяжет к себе (найденому) елементу))))) Про то что после обработки память освобождается и первый поток ко всему еще испортит еще какито данные. Замена должна выполнятся атомарно.

Про буфера удаления вообще ничего непонял, чесно)

79K
02 марта 2012 года
last_lord
6 / / 27.02.2012

Код:
struct fnd{
    fnd* lnk_prev;
    int sl_1,sl_2;
    int marker; // или void* lnk_message;
    fnd* lnk_next;
};

fnd a,b,c,d,e,*buff;
// исходное состояние
b.lnk_prev=&a; b.lnk_next=&d;
d.lnk_prev=&b; d.lnk_next=&e;
// добавляем c между d и b
/* step 1 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&d;// d и b остадись как были
d.lnk_prev=&b; d.lnk_next=&e;
/* step 2 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&с;// b изменилось
d.lnk_prev=&b; d.lnk_next=&e;
/* step 3 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&с;// d изменилось
d.lnk_prev=&c; d.lnk_next=&e;

//Удаляем c
/* step 1 */
buff=&c;// как бы нашли в цепочке
/* step 2 */
b.lnk_next=buff->lnk_next;// те &d
/* step 3 */
d.lnk_prev=buff->lnk_prev;// те &b
// buff живет до следуюшего step 1


Вот так я себе это представлял.
Пример 2 однозначно отработает нормально, если считать изменение ссылки атонарной операцией.
С примером 1 сложнее. Тут нужно чтоб у каждого потока был свой буфер.
поток заполнения нашел место куда вставлять и создал новый элемент (допустим С)
поток поиска "выковыривает" элемент В (соседний) в свой буфер удаления. (цепочка будет A-D-E)
поток заполнения меняет ссылки соседей С (B и D) цепочка получится влево (прямой просмотр) A-D-E, а вправо E-D-C-B-A.
Вот тут нас спасет проверка не находится ли один из соседей в буфере удаления другого потока. Ну, а поскольку В в буфере удаления, но еще не удален (те память не очищена), то можно вернуть цепочку в приемлимое состояние.
Буфера придумывались на случай если потоку поиска и потоку удаления приглянется один и тот же элемент. Оба потока помещают элемент в свои буфера удаления, правят ссылки соседей (одинаковым образом), а потом поток поиска смотрит, что забрал элемент, который уже обрабатывется потоком удаления, и зануляет свой буфер (например).

Еще я помню, что видел где-то конструкцию, в которую можно заключить операторы, чтоб они выполнялись без прерывания потока.
73K
02 марта 2012 года
bolt7
33 / / 20.02.2012
критические секции, это я и использую, только я называл это блокировкой очереди, так как пока не поменяются ссылки никто не должен работать со списком.
теперь какие я виже проблемы.
1. Буфер удаления должен существовать пока поток заполнения не востановил очередь. А когда он это сделает неизвестно, и поток поиска вместо того чтоб вернуть элемент какой он нашел, должен сидеть и ждать пока поток вставки разберется со своими проблемами и можно будет очистить свой буфер удаления.
2. Запускаем еще один поиск элемента асинхронно. Пока 1 поток поиска и поток заполнения решают свои разногласия, 2 поток поиска спокойно передвигается по изначальной очереди. Поток заполнения должен знать обо всех потоках поиска. А если их будет N штук он просто срехнется пока обшарит их буфера и добавит этот несчасный элемент, а вместе с ним и я чтоб придумать как это сделать побыстрее.

Я тут коечто придумал, но чуствую критики будет...

Если мы не можем сделать общий случай, нужно рассмотреть частные.
2 служебки, 1 - адрес отправителя, 2 - идентификатор сообщения.
Адрес отправителя задается в виде номера в таблице клиентов, потому что число клиентов конечно, а их ip могут совпадать, если 2 клиента на 1 машине работают.
Идентификатор сообщения тоже можно ограничеть - кто будет использовать все 4 милиарда для идентификации сообщения. Например 32 идентификатора.

структура сообщение
 
Код:
struct _msg_data
{
     //тут разные поля, заголовок, идентификатор, отправитель, информация различная
};

теперь контейнер для него
 
Код:
struct _msg_owner
{
     _msg_data data;
     _msg_owner *nextAddr,*prevAddr;
     _msg_owner *nextID,*prevID;
     _msg_owner *nextAddrID,*prevAddrID;
};

делаем 3 очереди
 
Код:
_msg_owner *Addr[Количество клиентов];
     _msg_owner *ID[32+1];
     _msg_owner *AddrID[Количество клиентов][32+1];

Только масивы будут динаическими так как количество клиентов узнаются уже после создания сессии.

Поток обработки заполнения
1. Читаем данные из источника (сокет, канал,...)
2. Создается структура _msg_owner и заполняется ее поле с данными - нужно пропарсите же поток считанной инфы и разложить по полям.
3. Вход в критическую секцию
4. Правка ссылок 3х очередей
5. Выход из секции.

Поток поиска
1. Вход в крит секцию
2. Берем нужный элемент и правим ссылки в очередях.
3. Выход из секции.

Минусы
1. Нужно поддерживать сразу 3 очереди
2. Раход памяти на очереди
Плюсы
1. Находжение элемента за 1 обращение при любых размерах очереди:
если ищем по адресу
Addr[Адрес]
так же и по идентификатору
ID[идентификатор]
по обоим полям
AddrID[Адрес][идентификатор]

Если используется идентификатор больше 32 то помещаем его в 33 ячейку по порядку, для этого и создавалось 32+1. Но я очень сомневаюсь что хотябы 10 идентикаторов будут использовать, а кто будет спецально брать их такими 99999, будет сидеть и ждать дольше.

Начет минусов - для современных процессоров думаю непроблема 3 раза исправить по 2 ссылки, тем более потоков заполнения можно сделать 2 и тогда пока один получает и парсит данные, другой правит ссылки. Расход памяти по сравнению с современными програмамми (вот щас у меня панель с гаджетами весит 130 Мб) просто ничтожно - при 1000 пользователях и 32 идентификаторов - 129 Кб. Я конечно всегда стараюсь не тратить зря даже 1 байта, но поиск за 1 ображение при ЛЮБЫХ размерах того стоят.

Думаю такая схема будет работать быстрее чем любой поиск в 1 очереди даже с сортировкой.

Что думаете (вообщето я почти уже запрограммировал), я сума сошел уже пока ламал голову?)))))

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог