Я пытаюсь придумать взвешенный алгоритм для приложения. В приложении есть ограниченное количество места, доступного для различных элементов. Как только все пространство занято, алгоритм должен выбрать лучший элемент (элементы) для удаления, чтобы освободить место для новых элементов.
Существуют различные атрибуты, которые должны повлиять на это решение. Например:
- T: время с момента последнего доступа. (Лучше всего заменить то, к чему давно не обращались.)
- N: количество обращений. (Лучше всего заменить то, к чему не обращались много раз.)
- R: Количество элементов, которые необходимо удалить, чтобы освободить место для нового элемента. (Лучше всего заменять наименьшее количество элементов. В идеале это также должно учитывать атрибуты T и N каждого заменяемого элемента.)
У меня есть 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 минутами, поскольку эти два события произошли гораздо позже.) (Или другой пример: замена (R ) 1 или 2 элемента - это нормально, но когда мне нужно заменить 5 или 6, это должно сильно утяжелиться... поэтому оно не должно быть линейным.)
replacementWeight = 1/T + sqrt(N) - R*R
Очевидно, что (1) и (2) тесно связаны, поэтому я надеюсь, что есть лучший способ придумать такой алгоритм.
