Перейти к содержанию
    

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Проблема в быстром поиске пакета. Сделать хэш таблицу ID1-ID2 <=> индекс - громадная таблица получиться.

Сделайте таблицу преобразования ID1/ID2 -> индекс пакета в массиве. ID1/ID2 в таблицу добавляйте отсортированными по возрастанию.

Тогда поиск можно делать методом последовательного приближения: в худшем случае будет около 9 шагов цикла поиска.

 

Есть реализация базы данных для эмбедед? кто нибудь видел такое? может даже реализовывал?

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

Ну если конечно руки не совсем уж кривые....

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

И тут я вспомнил работу с SQL базами данных - это ж просто праздник какой то. Добавляй, удаляй, редактируй записи сколько влезет и очень быстро.

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Сделайте таблицу преобразования ID1/ID2 -> индекс пакета в массиве. ID1/ID2 в таблицу добавляйте отсортированными по возрастанию.

Тогда поиск можно делать методом последовательного приближения: в худшем случае будет около 9 шагов цикла поиска.

 

 

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

Ну если конечно руки не совсем уж кривые....

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

 

Это только кажется. Поиск - да, быстрый, ибо при правильном применении индексов он логарифмический. Т.е. в Вашем случае на поиск нужного элемента будет всего 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.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Потому что даже большой memmove (в данной ситуации худший случай будет 511*(sizeof(int)+sizeof(*pkt))=2кБайт) может оказаться куда быстрее перебалансирования дерева.

1. Зачем хранить указатели на пакеты? Вместо них лучше индексы. Тогда один элемент таблицы поиска можно ужать до 32 бит:

log(10000)/log(2)+8+9 = 31бит

2. При каждом добавлении нового пакета, будет удаляться из массива один из пришедших ранее.

Алгоритм выбора удаляемого элемента ТС не привёл, предположим что это - самый старый из записанных пакетов.

Тогда добавление нового элемента - это просто кольцевой буфер пакетов в массиве хранения пакетов.

Плюс - необходим ещё один массив для обратного преобразования "индекс пакета" -> ID1/ID2 (для поиска позиции удаляемого пакета в таблице поиска).

А операция memmove() для таблицы поиска будет выполняться для участка: от добавляемого элемента до удаляемого элемента.

 

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

Зачем? :wacko:

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вы не поняли. Не надо хранить таблицу размером 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бит

 

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

 

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

 

Конечно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

1. Зачем хранить указатели на пакеты? Вместо них лучше индексы. Тогда один элемент таблицы поиска можно ужать до 32 бит:

log(10000)/log(2)+8+9 = 31бит

2. При каждом добавлении нового пакета, будет удаляться из массива один из пришедших ранее.

Алгоритм выбора удаляемого элемента ТС не привёл, предположим что это - самый старый из записанных пакетов.

Тогда добавление нового элемента - это просто кольцевой буфер пакетов в массиве хранения пакетов.

Плюс - необходим ещё один массив для обратного преобразования "индекс пакета" -> ID1/ID2 (для поиска позиции удаляемого пакета в таблице поиска).

А операция memmove() для таблицы поиска будет выполняться для участка: от добавляемого элемента до удаляемого элемента.

 

 

Зачем? :wacko:

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Гуглите "поиск методом последовательного приближения" или "бинарный поиск".

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

Конечно.

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

Это займет много время.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Это займет много время.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Укладывайте пакеты при приеме в связный упорядоченный (сортировка по требуемому полю) список.

При "укладке" одновременно ведите индексный файл, но не "в сплошную" а по блокам в списке (10-20 пакетов в блоке)

чтобы размер этого индекса был приемлем.

Грубый поиск - по индексному файлу / массиву.

Точный - внутри блока по списку.

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...