Easyelectronics.ru

Электроника для всех
Текущее время: 23 янв 2018, 05:25

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



    • JLCPCB - Платы прототипов всего за 2$ c бесплатной доставкой (при первом заказе)
    • 10 PCBs за $2 для 2 слоев, $15 для 4 слойной, $74 для 6 слойной платы.
    • Крупнейший китайский производитель прототипных плат. 290000+ клиентов & 8000+ заказов в день!
    • LCSC - Крупнейший китайский онлайн магазин радиодеталей.

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

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 180
Я получаю пакеты данных. Эти пакеты я должен хранить в 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
Сообщения: 2326
Откуда: Санкт-Петербург
Какой ещё базы? Хэш-таблица или дерево. Всё равно у базы внутри оно же.
И почему у вас хэш-таблица громадная получается? Её размер вы выбираете сами, при слишком маленьком просто будет чуть медленнее работать (но всяко быстрее связного списка).


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

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


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

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


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

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


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

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


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

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


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

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

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
Сообщения: 1307
jenya77 писал(а):
Комбинаций все равно будет 10000*256 - как от этого уйдешь?

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


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

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

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


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

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


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

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

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

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


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

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


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

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

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

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


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

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


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

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


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

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


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

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


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

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


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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

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