[Tartarus] Алгоритм для вычисления наиболее используемых записей

[Ivan A. Melnikov]

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

Нас интересует действительная функция

priority(id, time),

где id -- идентификатор элемента;
    time -- время, в которое приоритет был вычислен.

Предлагается следующая реализация.

Храним состояние -- множество троек

( id, time, priority(id, time) ).

Текущий приоритет определяется как

priority(id, now) = update(priority(id, time), now - time)

где now -- текущее время;
    update(x,t) -- вещественная функция двух вещественных аргументов,
        которую мы определим ниже.

Если текущий приоритет меньше определённого порога (да, это оно,
достаточно малое \varepsilon), то запись можно удалить, при условии,
что общее число записей превосходит число отображаемых записей.

В случае использования элемента, для которого запись уже существует, эта
запись заменяется на

( id, now, priority(id, now) + 1.0 )

где priority(id, now) определяется по предыдущей формуле. Если же запись
не существовала, добавляется новая запись

( id, now, 1.0 )

Осталось определиться с выражением для update(x,t). Нам требуется
следующее:
 1. update(x,t) определена для всех неотрицательных x и t и
    неотрицательна на области определения;
 2. update(0,t) = 0 для любого t >= 0;
 3. update(x,0) = x для любого x >= 0;
 4. для каждого фиксированного x, функция f(t) = update(x,t) монотонно
    убывает с ростом t;
 5. для каждого фиксированного t, функция g(x) = update(x,t) монотонно
    возрастает с ростом x;
 6. update(update(x, t_1), t_2) = update(x, t_1 + t_2);
 7. для каждого фиксированного x, update(x,t) -> 0 при t -> +inf.

Из функций, удовлетворяющих этим свойствам, мне сходу в голову приходит
только что-то вроде

update(x,t) = x * exp(-k*t),

где k > 0.

Действительно,
update(update(x, t_1), t_2) =
    = x * exp(-k*t_1) * exp(-k*t2) = x * exp(-k(t_1 + t_2)) =
    = update(x, t_1 + t_2).

Остальные свойства проверить ещё легче.

P.S. Не факт, что это всё будет хорошо работать на практике...

-- 
Best Regards,
Ivan A. Melnikov
Subdepartment of Differential Equations and Applied Mathematics
Saratov State University