Jump to content

    
Sign in to follow this  
a9d

Организация упорядоченной таблицы хешей ?

Recommended Posts

Здравствуй.

 

Мне нужно хранить во flash памяти таблицу хешей и осуществлять быстрый поиск по ней. Пока таблица маленькая проблем нет. Но при увеличении появляются огромные проблемы.

 

 

1) При добавлении хеша приходится сортировать таблицу. Операция Write работает намного медленней чем Read, также потребляет намного больше энергии. В итоге большую таблицу сортировать нельзя, это сорвет все тайминги.

2) Нужен бинарный поиск а без сортировки его никак не получить.

 

Есть ли какой-то способ организации таблицы, чтоб свести количество операций Write к минимуму в случае добавления записи и при этом можно было быстро найти нужную запись?

 

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

Edited by a9d

Share this post


Link to post
Share on other sites

Вам может помочь уход от классической идеи сортировки "на каждом шагу",

когда таблица должна быть упорядочена с приходом любого нового значения.

 

Если у вас контроллер - и проблема с энергией (ради интереса уточните область

вашего применения), то я бы пошел по пути периодического "накопления-перераспределения",

когда например вами выбрано максимально допустимое время на сортировку, пусть

100 строк, и далее вы копите данные до 100 строк и выполняете банальный перебор

всех значений подряд. Далее, когда появилось 101 значение - выполняете бинарное

деление на две таблицы и снова накапливаете в них данные до 99 строк

(пусть время анализа 1й строки = времени логического выбора одной из двух таблиц).

И т.д. - получаете итерационный процесс.

 

Конечно метод имеет существенное ограничение, если хеши будут однотипные, но

если бинарное деление выполнять "с конца" хеша - то перемешивание должно быть

удовлетворительным.

 

Если у вас "тайминги" настолько критичны что нельзя будет выделить время на

периодическую сортировку данных - то нужно пересмотреть и оптимизировать проект.

 

 

 

Share this post


Link to post
Share on other sites
Мне нужно хранить во flash памяти таблицу хешей и осуществлять быстрый поиск по ней. Пока таблица маленькая проблем нет. Но при увеличении появляются огромные проблемы.

...

Есть ли какой-то способ организации таблицы, чтоб свести количество операций Write к минимуму в случае добавления записи и при этом можно было быстро найти нужную запись?

Сортировать в ОЗУ указатели на хэши.

Придётся вести, н-р, битмап занятых записей в таблице. Заодно малой кровью реализуется циклическая запись хэшей по всей выделенной под них области флэш памяти.

Share this post


Link to post
Share on other sites
Сортировать в ОЗУ указатели на хэши.

 

На данный момент у меня в шапке таблицы хранятся указатели которые я сортирую. А сам хэш записывается в первую попавшуюся свободную ячейку.

 

 

У меня появилась мысль разбить таблицу на маленькие по 256 записей(под размер страницы). В начале таблицы содержаться указатели от 0..0xFF. При добавлении новой записи нужно найти таблицу со свободным местом. Далее добавить в нее запись и отсортировать указатели. При таком подходе будет перезаписано только две страницы.

Поиск конечно немного пострадает.

 

Ну еще нужно будет выровнять все адреса, чтоб вычисление полного адреса сводилось к операции смещения и OR.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this