Структура данных старения в C #

Question

Мне нужна структура данных, которая позволит запрашивать сколько элементов за последние X минуты . Элемент может быть простым идентификатором или более сложной структурой данных, предпочтительно временная метка элемента будет находиться в элементе, а не храниться снаружи (в виде хеш-кода или подобного, не хотелось бы иметь проблемы с несколькими одинаковыми элементами метка времени).

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

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

Answer 1

Для этого можно использовать простой связанный список.

В основном вы добавляете новые элементы в конец и удаляете слишком старые элементы с самого начала, это дешевая структура данных.

пример-код:

list.push_end(new_data)
while list.head.age >= age_limit:
    list.pop_head()

Если список будет достаточно занят, чтобы оправдать отрубание больших кусков за раз, тогда я согласен с dmo , используйте древовидную структуру или что-то подобное, что позволяет обрезку на более высоком уровне. 1010 *

Answer 2

кэш с скользящим сроком годности сделает работу ....

заполняет ваши предметы, а кэш обрабатывает старение ....

http://www.sharedcache.com/cms/

Answer 3

Я думаю, что важным фактором будет частота запросов вместо добавления / удаления. Если вы будете часто делать запросы (особенно если у вас большая коллекция), B-дерево может быть подходящим вариантом:

http://en.wikipedia.org/wiki/B-tree

У вас может быть какой-то поток, который периодически проходит и очищает это дерево или делает его частью поиска (опять же, в зависимости от использования). По сути, вы выполните поиск по дереву, чтобы найти точку «х минут назад», а затем посчитаете количество детей на узлах с более новым временем. Если вы сохраняете количество дочерних узлов в актуальном состоянии, эту сумму можно быстро сделать.