Мне нужна структура данных, которая позволит запрашивать, сколько элементов за последние X минут . Элемент может быть простым идентификатором или более сложной структурой данных, предпочтительно временная метка элемента будет находиться в элементе, а не храниться снаружи (в виде хеш-кода или подобного, не хотелось бы иметь проблемы с несколькими одинаковыми элементами отметка времени).
До сих пор кажется, что с LINQ я мог легко фильтровать элементы с отметкой времени, превышающей заданное время, и объединять счет. Хотя я пока не решаюсь заняться конкретными вещами .NET 3.5 в своей производственной среде. Есть ли другие предложения для подобной структуры данных?
Другая часть, которая меня интересует, - устаревание старых данных. Если я собираюсь запрашивать количество элементов менее 6 часов назад, я бы хотел, чтобы что-то более старое, чем это, было удалено из моей структуры данных, потому что это может быть долгосрочной программой.
Для этого можно использовать простой связанный список.
По сути, вы добавляете новые элементы в конец и удаляете слишком старые элементы с самого начала, это дешевая структура данных.
Пример кода:
list.push_end(new_data)
while list.head.age >= age_limit:
list.pop_head()Если список будет достаточно занят, чтобы оправдать отрубание больших кусков за раз, тогда я согласен с dmo , использую древовидную структуру или что-то подобное, что позволяет выполнять обрезку на более высоком уровне.
Я думаю, что важным фактором будет частота запросов вместо добавления / удаления. Если вы будете часто делать запросы (особенно если у вас большая коллекция), B-дерево может быть подходящим вариантом:
http://en.wikipedia.org/wiki/B-tree
Вы могли бы периодически просить какой-нибудь поток и очистить это дерево или сделать его частью поиска (опять же, в зависимости от использования). По сути, вы выполните поиск по дереву, чтобы найти точку «х минут назад», а затем посчитаете количество детей на узлах с более новым временем. Если вы сохраняете количество дочерних узлов в актуальном состоянии, эту сумму можно сделать быстро.
кэш с выдвижным истечением сделает работу ....
Заполните ваши предметы, и кеш обрабатывает старение ....