Устаревание записей в таблице Опции

[ataradov]

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

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

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

[Rst7]

Есть таблица (маршрутизации, но это не важно)

Важно.

Тут палка о многих концах в смысле производительности.

Если у Вас записи в таблице маршрутизации случайно разбросаны (относительно ключа поиска - например, адрес приемника), то прямой поиск будет иметь вычислительные ресурсы O(n). Обычно таблицы маршрутизации хранят в сортированном по ключу виде, дабы при использовании бинарного поиска ресурсов бы требовалось O(log2(n)).

Естественно, в такой таблице простой метод перемещения записей вверх не работает. Надо строить деревья, заводить дополнительные поля (таймер либо счетчик), и т.д. и т.п.

Но! Если у Вас в среднем основную нагрузку на маршрутизацию создают источники, количество который не превышает log2(n), то метод перемещения наиболее часто используемых вверх списка и прямой поиск будет вполне адекватен бинарному по производительности.

Если же это условие не выполняется, то для сохранения производительности с вменяемой тратой ресурсов по ОЗУ можно попробовать рассмотреть группирование записей в группы по частоте использования, а в этих группах записи должны быть сортированы для бинарного поиска.

Скажем, разбить массив на 256 записей на 8 частей (блоков) по 32 записи. Сначала ищется запись в блоках (худший случай - 8*5=40 операций), затем запись переносится из текущего блока (в котором нашли) в предыдущий. Первый блок будет содержать самые часто используемые записи, второй - менее, и так далее. Причем, имеется один финт ушами для оптимизации - найденное бинарным поиском место, в котором могла бы быть данная запись в предыдущем блоке надо запомнить - туда будет вставляться найденная запись. Запись рядом с вставляемой записью переносится в блок, из которого вытащена найденная запись - это еще +5 операций поиска.

Как-то так.