Быстрый доступ к элементу. Опции

[Jenya7]

Я получаю пакеты данных. Эти пакеты я должен хранить в 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

[Rst7]

1. Зачем хранить указатели на пакеты? Вместо них лучше индексы. Тогда один элемент таблицы поиска можно ужать до 32 бит:
log(10000)/log(2)+8+9 = 31бит

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

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

Конечно.

[Jenya7]

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

Конечно.

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

[jcxz]

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

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

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

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

[Jenya7]

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

копирование трех элементов плюс запись нового не получиться - таки надо раздвинуть.

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


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

то есть сдвинуть все элементы вправо от искомого. а при удалении все элементы влево от искомого.

наверно это все равно будет быстрее чем с несортированным массивом.

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

[jcxz]

то есть сдвинуть все элементы вправо от искомого. а при удалении все элементы влево от искомого.

Я уже несколько раз написал - это можно сделать за одну операцию memmove(): сдвиг элементов в массиве поиска от добавляемого до удаляемого. Всего одна memmove.

[k155la3]

. . . . это можно сделать за одну операцию memmove(): сдвиг элементов в массиве поиска от добавляемого до удаляемого. Всего одна memmove.

Это зависит от платформы ? - в смысле содержимого memmove() - аппаратная или программная реализация пересылки ?