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

[Yuri Bushmelev]

В сообщении от Воскресенье 11 января 2009 Dmitriy M. Maslennikov написал(a):
> При создании графических инструментов управления Tartarus есть задача
> показать пользователю список наиболее часто используемых записей. Для
> меня задача вычисления такого списка показалась нетривиальной.
>
> Формулирую задачу:
>
> Пользователь время от времени использует элементы, которые можно
> идентифицировать числами. В некоторый момент времени возникает задача
> показать ему некоторое количество (например, 10) наиболее используемых
> в последнее время элементов, от сортированных по "используемости".
> Необходимо учитывать, число использований, устаревание информации об
> использовании во времени: элемент очень часто использовавшийся месяц
> назад не должен попасть в список, если имеется десяток использованных
> сегодня и т. п. факторы. При этом алгоритм должен быть достаточно
> быстрым - пользователь должен получать список на экране без заметных
> задержек (часть информации можно вычислять при старте программы, а
> затем только содержать эту информацию в актуальном состоянии)
>
> Какие будут соображения?

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

При выводе для сортировки используем функцию для выбора top-10, зависящую от 
времени последнего использования и счетчика. Пусть она 
возвращает "приоритет". Простейший пример - кол-во дней с момента 
последнего использования * 10 000 000 + кол-во использований. Правда, если 
элемент вчера использовали 10 000 011 раз, то он все равно обгонит всех 
сегодняшних, использованных по одному разу. Поэтому надо придумать что-то 
более умное, но тут бы теоретика надо :)

Периодически отдельным потоком (thread'ом) можно этот 
список "перетрахивать", дабы не хранить там кучу старья. Можно просто 
выбирать top-10 и удалять остальное. Ибо счетчик использования не 
уменьшается.

Вот как-то так :)

-- 
С уважением,
Бушмелев Юрий