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

[ataradov]

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

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

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

[Major]

Как происходит поиск записи в таблице?

Если у вас не хеш, а прямой поиск, то пузырьковая сортировка.
Пусть есть обращение к записи с индексом N, то переносим ее в индекс N-1 (делаем swap(rec[N-1],rec[N])
Пр появлении новой записи она записывается в самый последний индекс, так как в самом низу самая редкая запись.

[ataradov]

Как происходит поиск записи в таблице?

Простым последовательным поиском.

Если у вас не хеш, а прямой поиск, то пузырьковая сортировка.

Спасибо. У меня это в голове вертелось, но я зациклился на переносе в самый верх, а не на одну запись.

[Major]

Думаю что такой метод запатентован (текущее патентное право не одобряю).

[ataradov]

Думаю что такой метод запатентован (текущее патентное право не одобряю).

Да куда не плюнь - все запатентовано, делать-то нужно.

[scifi]

Думаю что такой метод запатентован (текущее патентное право не одобряю).

Даже если запатентовано, спокойно игнорируем патент и работаем дальше. Если объёмы выросли настолько, что начинают приставать с патентами, то это скорее хорошо, чем плохо :-)
Кстати, поиск по патентам иногда выдаёт что-нибудь интересное:
Google Patents

[Rst7]

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

Важно.

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

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

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

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

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

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

Как-то так.

[Major]

Нравиться электроникс тем что почти по любой специфике (постановка эксперимента, основы естественных наук) найдется человек по теме
Чтобы не совсем офф-топ:
Кнута читать надо (или хотя бы Дейкстру). Ощущение что программисты перестали изучать математику и теорию алгоритмов.

[ataradov]

Это все верно для "взрослых" применений, мне-же время поиска не сильно критично, отправка идет через медленный канал в любом случае. В то же время критичен объем программы и ОЗУ, так как исполняется на очень мелких МК.

Но в любом случае всем спасибо за участие.