Я получаю пакеты данных. Эти пакеты я должен хранить в RAM. Глубина хранения не определена но пока что это 512 пакетов.
То есть в RAM я создал массив 512 пакетов.
У каждого пакета есть два поля ID - ID1/ID2. Значения инденцификационных полей варьируются ID1=0-10000, ID2=0-255.
Мне приходит команда - добавь пакет 700/12, удали пакет 700/12, редактируй пакет 700/12. Команда приходит довольно часто - худший случай - каждую милисекунду поэтому время поиска элемента критично.
Проблема в быстром поиске пакета. Сделать хэш таблицу ID1-ID2 <=> индекс - громадная таблица получиться.
Сейчас к чему я пришел - самое оптимальное связанный список.
И тут я вспомнил работу с SQL базами данных - это ж просто праздник какой то. Добавляй, удаляй, редактируй записи сколько влезет и очень быстро.
В принципе это может быть non-SQL база данных - у меня всего одна таблица.
Есть реализация базы данных для эмбедед? кто нибудь видел такое? может даже реализовывал?

P.S. Погуглил эту тему. Вроде как советуют SQLLite. Но я не нашел примеров SQLLite для эмбеддед в С.

Сообщение отредактировал Jenya7 - Oct 22 2017, 09:02

Сделайте таблицу преобразования ID1/ID2 -> индекс пакета в массиве. ID1/ID2 в таблицу добавляйте отсортированными по возрастанию.
Тогда поиск можно делать методом последовательного приближения: в худшем случае будет около 9 шагов цикла поиска.


Бред. Любая "библиотека" для такой задачи будет однозначно тормознее специализированного решения. А уж всякие SQL-и сюда тащить - верх глупости.
Ну если конечно руки не совсем уж кривые....

Это только кажется. Поиск - да, быстрый, ибо при правильном применении индексов он логарифмический. Т.е. в Вашем случае на поиск нужного элемента будет всего 9 сравнений. А вот добавление/удаление может затянуться, ибо надо перебалансировать дерево.

В Вашем случае SQL - это сильно избыточно. Реализуйте это сами, там всего-то на полстраницы кода. Ключевое слово для гугля - "бинарное дерево поиск добавление удаление элемента". Хотя лично я бы возможно поступил чуть по-другому. Вместо дерева имел бы сортированный массив (ключ + указатель на пакет) и тупо добавлял/удалял из него элементы через memmove. Потому что даже большой memmove (в данной ситуации худший случай будет 511*(sizeof(int)+sizeof(*pkt))=2кБайт) может оказаться куда быстрее перебалансирования дерева.

переберите все сочитания 0-10000 и 0-255. Уж не помню, факториал по моему дает результат но таблица получиться громадная.


ключ + указатель на пакет - это легко сказать. а как создать?

Вы не поняли. Не надо хранить таблицу размером 10000*256. Нужен лишь всего массив структур {int key; PKT *p;} размером в 512 элементов. Если этот массив хранить по возрастанию key (или убыванию), то поиск элемента в нем потребует только 9 сравнений. key - это id1*256+id2, если что.



Для Ваших целей в качестве ключа вполне пойдет линейная комбинация id1 и id2. Т.к. диапазон id2 у Вас 0...255, то самый простой способ - key=id1*256+id2. Это с запасом лезет в 32хбитный int.

1. Зачем хранить указатели на пакеты? Вместо них лучше индексы. Тогда один элемент таблицы поиска можно ужать до 32 бит:
log(10000)/log(2)+8+9 = 31бит
2. При каждом добавлении нового пакета, будет удаляться из массива один из пришедших ранее.
Алгоритм выбора удаляемого элемента ТС не привёл, предположим что это - самый старый из записанных пакетов.
Тогда добавление нового элемента - это просто кольцевой буфер пакетов в массиве хранения пакетов.
Плюс - необходим ещё один массив для обратного преобразования "индекс пакета" -> ID1/ID2 (для поиска позиции удаляемого пакета в таблице поиска).
А операция memmove() для таблицы поиска будет выполняться для участка: от добавляемого элемента до удаляемого элемента.


Зачем?

ааа. то есть сортировать массив по ключу и делать бинарный поиск?

В данном случае это O(1).



Конечно.

допустим мы создали ID из двух полей. Я получил команду - редактируй элемент с этим ID. Я все равно в должен перебрать все элементы и найти искомый ID.

Нет. Вам тут уже несколько раз сказали: максимум потребуется 9 шагов цикла поиска.
Гуглите "поиск методом последовательного приближения" или "бинарный поиск".

Допустим у меня массив с ID 3 5 7 13 25 178 1355. Пришел ID 18. Я должен вставить его в свободное место и потом сортировать весь массив? А при удалении элемента сдвинуть все элементы влево?
Это займет много время.

В данном случае за 3 сравнения (бинарным поиском) Вы находите место для вставки элемента с ID 18 (между 13 и 25). После чего Вам его просто нужно вставить (копирование трех элементов плюс запись нового). Массив остается отсортированным.

Не в свободное место, а раздвинув существующие. И не все надо сдвигать, а от позиции нового пришедшего, до позиции удаляемого.


Исходить надо из случая заполненности всего массива (имеются все 512 кадров). И при старте делать инициализацию, заполнив первоначально массив недопустимыми индексами (с ID1 > 10000 например).

В данном случае я показываю на примере ТСа. "Допустим у меня массив".

Укладывайте пакеты при приеме в связный упорядоченный (сортировка по требуемому полю) список.
При "укладке" одновременно ведите индексный файл, но не "в сплошную" а по блокам в списке (10-20 пакетов в блоке)
чтобы размер этого индекса был приемлем.
Грубый поиск - по индексному файлу / массиву.
Точный - внутри блока по списку.