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