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

Question

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

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

Редактировать: Используемый язык - C # 4.

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

Это также приходитс асинхронной версией, которая перестраивает дерево с помощью библиотеки параллельных задач (TPL).

Answer 1

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

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

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

Дерево RB имеет сложность вставки O (log n), поэтому я предполагаю, что ваши вставки будут хорошо вписываться туда.

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

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

Answer 2

Использовать SortedList отсортировано по отметке времени.

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

Answer 3

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