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

[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]

А вообще-то для полной универсальности топикстартеру надо сюда - https://ru.wikipedia.org/wiki/%D0%9A%D1%80%...%B5%D0%B2%D0%BE

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

Вы прикалываетесь? В конкретно данном случае раздвижка и есть копирование трех элементов.

[Jenya7]

А вообще-то для полной универсальности топикстартеру надо сюда - https://ru.wikipedia.org/wiki/%D0%9A%D1%80%...%B5%D0%B2%D0%BE



Вы прикалываетесь? В конкретно данном случае раздвижка и есть копирование трех элементов.

это как? допустим есть элементы 3 5 7 9. я хочу вставить 6. он встанет на место 7. а семь куда встанет?

[Rst7]

это как? допустим есть элементы 3 5 7 9. я хочу вставить 6. он встанет на место 7. а семь куда встанет?

Еще раз.

CODE

#define N (5)

int a[N];

a[0]=3;
a[1]=5;
a[2]=7;
a[3]=9;

i=2; //В эту позицию надо вставить элемент

memmove(a+(i+1),a+i,sizeof(int)*(N-1-i)); //Сдвиг элементов 2,3 на позиции 3,4 - копирование a[2],a[3] в a[3],a[4]
a[i]=6;

После этого массив имеет вид 3,5,6,7,9.

memmove в большинстве случаев - это быстро. Но надо проверять, что конкретная библиотечная реализация действительно оптимальна.

[Jenya7]

Еще раз.

Код

#define N (5)

int a[N];

a[0]=3;
a[1]=5;
a[2]=7;
a[3]=9;

i=2; //В эту позицию надо вставить элемент

memmove(a+(i+1),a+i,sizeof(int)*(N-1-i)); //Сдвиг элементов 2,3 на позиции 3,4 - копирование a[2],a[3] в a[3],a[4]
a[i]=6;

После этого массив имеет вид 3,5,6,7,9.

memmove в большинстве случаев - это быстро. Но надо проверять, что конкретная библиотечная реализация действительно оптимальна.

да но внутри функции memmove - она все равно сдвинет N элементов. она ж не волшебница.
а я понял. ну вот в этом вопрос - насколько это оптимально. получим ли мы выйгрыш в результате всех этих телодвижений.

Вставка элемента - допустим случай *как всегда* - memmove не оптимальна - сдвиг N элементов. Удаление - сдвиг N элементов. Это сопоставимо с перебором элементов в форе.
Идем дальше. Массив пустой. Пришел первый элемент 100. Пришел элемент 90 - сдвинь вправо, вставь элемент. Пришел элемент 80 - сдвинь вправо, вставь элемент.
И так далее.
И все таки это будет быстрее простого перебора?

Посмотрел красно-черное дерево. пишут конечно красиво. маслом. вопрос так ли он быстЁр как кажется.

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

[Rst7]

Посмотрел красно-черное дерево. пишут конечно красиво. маслом. вопрос так ли он быстЁр как кажется.

Ну если реализация вменяема - то быстро. Худшие результаты там гарантированы, они все O(log n). Другое дело, что для небольших массивов (ну как у Вас, 512 элементов) всякие накладные расходы на дерево могут превысить по времени хорошо оптимизированный бинарный поиск плюс memmove.

[Jenya7]

Ну если реализация вменяема - то быстро. Худшие результаты там гарантированы, они все O(log n). Другое дело, что для небольших массивов (ну как у Вас, 512 элементов) всякие накладные расходы на дерево могут превысить по времени хорошо оптимизированный бинарный поиск плюс memmove.

я понял. 512 может превратиться в пару тысяч, это еще TBD. вы говорите на больших размерах можно подумать о красно-черном дереве?