Easyelectronics.ru

Электроника для всех
Текущее время: 21 янв 2019, 19:16

Часовой пояс: UTC + 5 часов




Начать новую тему Ответить на тему  [ Сообщений: 18 ] 
Автор Сообщение
 Заголовок сообщения: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 13:59 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
Я получаю пакеты данных. Эти пакеты я должен хранить в 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 для эмбеддед в С.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 14:09 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Какой ещё базы? Хэш-таблица или дерево. Всё равно у базы внутри оно же.
И почему у вас хэш-таблица громадная получается? Её размер вы выбираете сами, при слишком маленьком просто будет чуть медленнее работать (но всяко быстрее связного списка).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 14:12 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
ну переберите все сочитания 0-10000 и 0-255. Уж не помню, факториал по моему дает результат но число получиться громадное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 14:47 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
А слово "хэш" в термине хэш-таблица вы не видите?
Хоть в википедии почитайте, что такое хэш-таблица. (не забудьте раздел "разрешение коллизий").


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 14:54 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Вы можете взять простейшую реализацию - хэш-таблицу на N бинов (N подберёте или ставьте, сколько памяти есть), каждый бин - связный список. Итого поиск - посчитать хэш от пары ID1, ID2, взять его по модулю N и посмотреть в коротеньком связном списке блоков с тем же значением хэша (у вас N списков - при правильном выборе хэша и N обычно в них будет по 0-1 элементу, редко по 2-3.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 14:59 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
не очень представляю как это сделать. а что значит хэш от пары ID1, ID2? Комбинаций все равно будет 10000*256 - как от этого уйдешь?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 15:20 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Хэш же. Ну прочитайте!
Например, (ID1*313+ID2) mod N, где N=1024.
(Для скорости, разумеется, писать (ID1*313+ID2)&1023)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 15:35 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
вы меня дико извиняйте, я наверно ужасно туплю, но какой хэш сократит количество элементов?

ID1 ID2
0 0
.............
10000 0

0 1
..............
10000 1
и так далее. какой хэш сократит нам количество элементов?
я вижу хэш так
0/0->0
1/0->1
...............
10000/0->10000


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 16:32 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2473
jenya77 писал(а):
Комбинаций все равно будет 10000*256 - как от этого уйдешь?

Вам не на форум, а в библиотеку, читать Кнута, алгоритмы поиска и сортировки. Для начала.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 16:47 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Ну посчитайте по формуле. В эксель её вбейте и поэкспериментируйте. Увидите, что для некоторых пар хэши повторяются (например, hash(0,0)==0==hash(3,85)) - это нормально, см. "разрешение коллизий".

И НАЧНИТЕ, НАКОНЕЦ, ЧИТАТЬ!
Если статья в википедии непонятна - вбейте в гугл "хэш-таблица" и поищите что попроще. Например, http://algolist.manual.ru/ds/s_has.php


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 16:54 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
так это плохо что хэши повторяются! это значит что пакет hash(0,0) и hash(3,85) займут одну и ту же ячейку в массиве? разные ID - разные ячейки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 17:17 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Блджад, прочитайте, наконец, хоть одну статью! Раздел "разрешение коллизий", который раз говорю!

Ну, попадёт у вас в ячейку не один пакет, а два или три. Долго ли пройти список из трёх элементов? Куда быстрее, чем из 512, верно? Вот!
А если таблицу взять побольше (скажем, N=4096) - то и вероятность этого невелика.
Впрочем, даже маленькая табличка даст вам заметный выигрыш по сравнению с линейным списком. Грубо говоря, вместо обхода 512 элементов - один раз посчитать хэш, один раз получить указатель из таблицы и обойти в среднем 512/N элементов. Т.е. табличка на 16 указателей ускорит вам поиск почти в 16 раз!

P.S. Все оценки скорости - для среднего случая. В худшем (почти невероятном для нормальной хэш-функции) всё плохо. Если нужна гарантированная скорость - есть другие структуры данных, например, красно-чёрные деревья. Но они сложнее (и в среднем помедленнее).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 17:56 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
Мы наверно не понимаем друг друга. У меня есть массив из 512 элементов. Каждый элемент Х байт. Массив массивов, скажем так.
По уникальному ИД состоящему из двух ИД (полей) элемент должен попасть в свою ячейку. Скажем если ИД (hash(0,0)) был записан по индексу 10 array_of_elements[10]
то на это место не может быть записан ИД (hash(3,85)) - он затрет мне предидущие данные.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 18:20 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
512 элементов - это у вас массив принятых пакетов (кольцевой буфер или как вы там их храните).
Хэш-таблица - это совершенно отдельная структура. Массив размера N (скажем, 1024, или вообще сколько не жалко), в нём храним номера блоков из первого массива.
Плюс в первом массиве понадобится дополнение: в каждом блоке хранить номер следующего _с тем же значением хэша_ (т.е. внутри первого массива вы получите пачку связных списков, в каждом пакеты с одинаковым значением хэша).
Итого, когда вам нужно найти блок ID1:ID2 - считаете хэш, смотрите значение в хэш-таблице - получаете номер пакета в первом массиве (или отметку, что ничего нет). Смотрите в этом пакете, если ID1 и ID2 совпали - ура, иначе смотрим в нём указатель на следующий элемент с тем же хэшом, и так далее.

Вроде разжевал. Но это всё ж в статьях есть!!!

P.S. Аналогия, которая, может, будет вам понятна: хэш-таблица - это индекс в базе данных, а не сама таблица с данными.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 22 окт 2017, 19:39 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
по моему понял. спасибо. попробую сделать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 23 окт 2017, 11:52 
Заглядывает иногда

Зарегистрирован: 07 фев 2014, 15:45
Сообщения: 120
Во первых надо внимательно рассмотреть структуру ключа, по которому вы собираетесь искать данные в таблице. Далее уже выбирать соответствующую этому структуру данных. В вашем случае ,я думаю, Вам поможет двоичная куча - поиск элемента за логарифмическое время. Ну либо сбалансированное двоичное дерево. Что конкретно зависит от требований к операциям и поступающим данным.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 23 окт 2017, 12:28 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
yatsok, сбалансированное дерево товарищу пока сложновато будет, а обычное у него наверняка разбалансируется.
А насчёт двоичной кучи - вы попутали, она для быстрого получения максимума (минимума), а не поиска произвольного элемента.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый доступ к элементу.
СообщениеДобавлено: 23 окт 2017, 13:48 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 816
Если пакеты приходят упорядочено, то двоичный поиск по кольцевому буферу может оказаться проще и оптимальнее. Но, хэштаблица - это, конечно, универсальное решение.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ] 

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: Driver_gv


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB