Придумать факторы для взвешенного алгоритма?

Question

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

Существуют разные атрибуты, которые должны повлиять на это решение. Например:

• Т: время с момента прошлого доступ. (Лучше всего заменить то, к чему не было доступно через некоторое время.)
• N: количество раз, доступ к которому. (Лучше всего заменить то, к чему не было доступно много раз.)
• R: Количество элементов, которые необходимо удалить, чтобы освободить место для нового элемента. (Лучше всего заменить наименьшее количество элементов. В идеале это также должно принять во внимание атрибуты T и N замены каждого элемента.)

У меня есть 2 проблемы:

1. Выяснить, сколько веса придать каждому из этих атрибутов.
2. Выяснить, как рассчитать вес для элемента.

(1) Я понимаю, что придумывание веса для чего -то подобного очень субъективно, но я надеялся, что есть стандартный метод или что -то, что может помочь мне решить, какой вес придать каждому атрибуту. Например, я думал, что один из методов может заключаться в том, чтобы придумать набор из двух образцов элементов, а затем вручную сравнить их и решить, какой из них в конечном итоге должен быть выбран. Вот пример:

Элемент A: n = 5, t = 2 часа назад.
Элемент B: n = 4, t = 10 минут назад.

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

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

Оба эти метода не кажутся такими хорошими, и я надеюсь, что есть лучшее решение.

(2) Как только я выясню вес, я не уверен, какой способ лучше рассчитать вес. Я должен просто добавить все? (В этих примерах я предполагаю, что какой бы элемент имеет самый высокий replacementWeight должен быть тот, который будет заменен.)

replacementWeight = .4*T - .1*N - 2*R

или все умножьте?

replacementWeight = (T) * (.5*N) * (.1*R)

Как насчет того, чтобы не использовать константы для весов? Например, конечно «время» (T) может быть важно, но как только определенное количество времени пройдет, оно начинает не иметь большого значения. По сути, я бы сбил все это в мусорное ведро «много времени». (Например, несмотря на то, что 8 часов и 7 часов имеют разницу между ними, эта разница может быть не такой значительной, как разница между 1 минутами и 5 минутами, так как эти два гораздо более поздравились.) (Или другой пример: замена (r ) 1 или 2 элемента - это нормально, но когда я начинаю заменить 5 или 6, это должно быть сильно увлечено ... поэтому это не должно быть линейным.)

replacementWeight = 1/T + sqrt(N) - R*R

Очевидно, (1) и (2) тесно связаны, поэтому я надеюсь, что есть лучший способ придумать такой алгоритм.

Answer 1

Вы описываете классическую проблему выбора Политика замены кеша. Анкет Какая политика лучше всего подходит для вас, зависит от ваших данных, но следующее обычно работает хорошо:

Во -первых, всегда храните новый объект в кэше, выселяя R Худший (ы). Невозможно узнать априори, должен ли объект храниться или нет. Если объект бесполезен, он скоро снова выпадет из кеша.

Популярный кеш кальмара орудия Следующие алгоритмы замены кэша:

• Наименьшее недавно (LRU):
  • replacementKey = -T
• Наименьшее часто используется с динамическим старением (Lfuda):
  • replacementKey = N + C
• Жадный двойной частота (GDSF):
  • replacementKey = (N/R) + C

C относится к Фактор возраста кэша здесь. C в основном replacementKey из предмета, который был высечен последним (или нулевым).

ПРИМЕЧАНИЕ. SpeeplacementKey рассчитывается, когда объект вставлен или доступен, и хранится вместе с объектом. Объект с наименьший SpectamentKey высечен.

LRU прост и часто достаточно хорош. Чем больше ваш кеш, тем лучше он работает.

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

Если ни один из них не соответствует вашим потребностям, вы можете рассчитать оптимальные значения для T, N а также R (и сравните различные формулы для их объединения), минимизируя сожалеть, разница в производительности между вашей формулой и оптимальный алгоритм, используя, например, Линейная регрессия.

Answer 2

Это совершенно субъективная проблема - как вы сами указываете. И особая возможность состоит в том, что если ваши тестовые примеры состоят из пар (a, b), где вы предпочитаете A до b, вы можете обнаружить, что вы предпочитаете A до b, b до c, но и C, то есть, это не заказа

Если вы не осторожны, ваша функция может не существовать!

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

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