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

Question

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

ПРИМЕЧАНИЕ. Замена-ключ рассчитывается при вставке или доступе к объекту и хранится рядом с объектом. Объект с наименьшим replaceKey выселяется.

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

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

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

Answer 2

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

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

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

Это классический подход статистики: сначала просмотреть данные для ИДЕНТИФИКАЦИИ модели, а затем использовать эту модельОЦЕНИТЬ конкретную реализацию модели.На эту тему есть большие книги.