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

[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() - аппаратная или программная реализация пересылки ?

[jcxz]

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

Я говорю о том, что не нужно дважды вызывать memmove(): сначала для удаления старой записи из массива поиска (и сжатия массива), а потом для раздвижки этого массива и вставки нового значения. Достаточно одного вызова memmove() для диапазона элементов от удаляемого до вставляемого.

memmove() применяется к массиву в РАМ. Тут уж какя бы ни была платформа а функция должна взять каждый элемент и сдвинуть.

Если разговор о платформе Cortex-M и IAR, то внутри библиотечной memcpy() (и думаю что и memmove() тоже), копирование может идти с использованием нескольких регистров процессора (читается-пишется сразу по несколько 32-битных слов). См. дизасм.

Ну смотрите. Поиск будет занимать 9 сравнений. Считайте, что это бесплатно. Теперь memmove. Ну при хорошей реализации для ARM он примерно два байта за такт процессора пересылает (ну чуть меньше, чем два, но сейчас это пофиг).

Да ладно! Какой компилятор? IAR-овский memcpy() может использовать до 4х или даже 8и регистров (точно не помню) процессора для копирования.
Посчитайте сколько это байт. Конечно он предварительно смотрит на размер пересылки и, в зависимости от него, выбирает тот или иной цикл копирования.
Побайтно будет для ОЧЕНЬ маленьких размеров.