Здравствуй.

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


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

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

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

Сообщение отредактировал a9d - Dec 16 2012, 23:46

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

Если у вас контроллер - и проблема с энергией (ради интереса уточните область
вашего применения), то я бы пошел по пути периодического "накопления-перераспределения",
когда например вами выбрано максимально допустимое время на сортировку, пусть
100 строк, и далее вы копите данные до 100 строк и выполняете банальный перебор
всех значений подряд. Далее, когда появилось 101 значение - выполняете бинарное
деление на две таблицы и снова накапливаете в них данные до 99 строк
(пусть время анализа 1й строки = времени логического выбора одной из двух таблиц).
И т.д. - получаете итерационный процесс.

Конечно метод имеет существенное ограничение, если хеши будут однотипные, но
если бинарное деление выполнять "с конца" хеша - то перемешивание должно быть
удовлетворительным.

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

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

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


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

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