Фильтрация подмножества (потенциально) 1.000.000+ единиц

Question

У меня есть большой dataset с возможно более чем миллионом записей. Все элементы имеют назначенную метку времени, и элементы добавляются к набору во время выполнения (обычно, но не всегда, с более новой меткой времени). Мне нужно показать подмножество этих данных с заданным временным диапазоном. Этот временной диапазон обычно довольно мал по сравнению с общим набором данных, то есть из 1.000.000+ элементов, не превышающих около 1000, в данном заданном интервале времени. Этот временной диапазон перемещается с постоянным темпом, например. каждую секунду временной диапазон перемещается на одну секунду. Кроме того, пользователь может отрегулировать временной диапазон в любое время («переместить» через набор данных) или установить дополнительные фильтры (например, фильтр по тексту).

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

Edit: Используется язык C# 4.

Обновление: Я теперь с помощью интервального дерева, реализация может быть найдена здесь: https://github.com/mbuchetics/RangeTree

Он также поставляется с асинхронной версии, которая перестраивает дерево, используя Параллельная библиотека задач (TPL).

Answer 1

Включите новые элементы в отсортированный список. Это позволит вам легко выбрать диапазон. Вы также можете использовать linq, если вы знакомы с ним.

Answer 2

Используйте SortedList, отсортированный по дате загрузки по таймеру.

Все, что вам нужно - это реализовать двоичный поиск по сортированным клавишам внутри отсортированного списка, чтобы найти границу вашего выбора, что довольно просто.

Answer 3

У нас была схожая проблема в нашей разработке - пришлось собрать несколько миллионов элементов, отсортированных по какому-то ключу, а затем экспортировать по нему одну страницу по требованию. Я вижу, что ваша проблема как-то схожа.

Для этой цели мы адаптировали red-black tree структуру, следующими способами:

• мы добавили итератор к нему, так что мы могли бы получить «следующий» пункт в о (1)
• мы добавили найти итератор из «индекса», и сумел сделать это в O (журнал N)

RB Tree имеет O (журнал п) сложность вставки, так что я думаю, что ваши вставки будут соответствовать там красиво.

на итераторе было реализовано путем добавления и поддержания связанного списка всех листовых узлов - наша оригинальная принятая RB Tree реализация не включала это.

RB Tree также классный, потому что он позволяет вам точно настроить размер узла в соответствии с вашими потребностями. Экспериментируя, вы сможете определить правильные цифры, которые просто соответствуют вашей проблеме.