Как быстро отфильтровать объекты, которые удовлетворяют условию диапазона дат

Question

У меня большая коллекция предметов

public class Restriction
{
    // which days this restriction applies to
    public DateTime From { get; set; }
    public DateTime To { get; set; }

    // valid applicable restriction range
    public int Minimum { get; set; }
    public int Maximum { get; set; }
}

Я мог бы тогда иметь

IList<Restricton> restrictions;

и затем поиск ограничений, которые применяются в определенный день

restrictions.Where(r => day >= r.From && day <= r.To);

Выпуск

Полагаю, использование IList<T> - не лучший вариант, потому что я буду много раз искать эти ограничения, и каждый раз, когда я буду вызывать метод LINQ .Where, вся коллекция будет перечисляться и фильтроваться.

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

Вопрос

Что может быть лучше ( быстрее ) для перечисления моих ограничений, чтобы мой алгоритм не перечислял их каждый раз, когда я хотел бы отфильтровать несколько?

Я думал о IDictionary<K,V>, но все равно нужно будет отсканировать их все, потому что мои ограничения установлены не на день, а на дневной диапазон.

Что бы вы предложили?

Answer 1

Рассмотрите возможность упорядочения списка по From - тогда вы можете быстро выполнить бинарный поиск, чтобы найти подмножество ограничений, которые могут применяться в терминах From.

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

Возможно, существует гораздо лучшая альтернатива, но это хорошаяначать, и у меня не хватает умственной энергии, чтобы выработать что-то лучше прямо сейчас: (

Answer 2

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

Первый список должен быть отсортирован по свойству From, а хэш - во второй список, отсортированный по свойству To. Это было бы похоже на то, что делает база данных.

Сортированные списки в .Net

.Net имеет класс для создания как ключевого, так и позиционного доступа с именем SortedList , который вы можете использовать для достижения желаемого.

Вы можете использовать конструктор, который принимает IComparer, который вы можете использовать, чтобы указать, как SortedList должен сравнивать ваш класс Restriction. Вам нужно будет написать два IComparers, один из которых сравнивает свойство From, а другой сравнивает свойство To.

Answer 3

Распространенным решением проблемы такого рода является реализация разбиения; это реализовано в средах баз данных для сокращения пространства поиска. Единственное предостережение в том, что ваша коллекция не может быть отфильтрована по другим критериям, или вам нужно будет создать индекс.

Пример реализации может использовать набор списков, которые содержат определенные диапазоны дат (по месяцам, годам и т. Д.). Выполняя вставки, вы определяете правильный список и помещаете свой элемент в этот список. Выполняя поиск, вы можете легко определить правильный список или набор списков, а затем только выполнить сканирование в этих списках.

Тем не менее, вы должны учитывать это - с какими элементами вы будете иметь дело? Сканирование всего списка становится серьезной проблемой только тогда, когда количество элементов очень велико. Оптимизация этой проблемы была бы преждевременной, если вы не имеете дело с непомерными объемами данных.

Answer 4

Если у вас много запросов и не так много вставок, вы можете сделать следующее: Создать два отсортированных списка ваших объектов, один отсортированный по fromDate, другой по toDate.Затем вы можете выполнить быстрый поиск по sortedLists, чтобы найти для каждого списка набор допустимых результатов (в первом списке вы запрашиваете записи с fromDate <= searchDate, а во втором списке запрашиваете toDate >= searchDate).Затем объедините наборы результатов, чтобы получить результаты.