Эффективно найти ближайший ключ словаря

У меня есть куча пар дат и денежных значений в SortedDictionary<DateTime, decimal>, соответствующих остаткам по кредитам, рассчитанным в будущем по датам составления контрактов. Есть ли эффективный способ найти ключ даты, который ближе всего к заданному значению? (В частности, ближайший ключ меньше или равен цели). Дело в том, чтобы хранить только данные в точках, когда значение изменилось, но эффективно ответить на вопрос "какой был баланс на дату x?". для любой даты в диапазоне.

Был задан аналогичный вопрос (Какой словарь .NET поддерживает "поиск ближайшего ключа" ?), и ответ был "нет" в то время, когда по крайней мере, от людей, которые отреагировали, но это было почти 3 года назад.

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

Ответ 1

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

var keys = new List<DateTime>(dictionary.Keys);

а затем эффективно выполнить бинарный поиск на нем:

var index = keys.BinarySearch(key);

Как говорится в документации, если index положителен или равен нулю, ключ существует; если он отрицательный, то ~index - это индекс, где key будет найден, если он существует. Поэтому индекс существующего ключа "сразу меньше" ~index - 1. Убедитесь, что вы правильно обрабатываете край, где key меньше любого из существующих ключей и ~index - 1 == -1.

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

Update

Как правильно указывает digEmAll, вы также можете переключиться на SortedList<DateTime, decimal>, чтобы keys собирала IList<T> (который SortedDictionary.Keys не). Этот интерфейс обеспечивает достаточную функциональность для выполнения бинарного поиска на нем вручную, так что вы можете взять, например. этот код и сделать его методом расширения на IList<T>.

Вы также должны иметь в виду, что SortedList работает хуже, чем SortedDictionary во время построения, если элементы не вставлены в уже отсортированный порядок, хотя в этом конкретном случае весьма вероятно, что даты вставляются в хронологические (отсортированные), который был бы идеальным.

Ответ 2

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

Я использовал TreeDictionary<K, V> из C5 Collections (GitHub/NuGet), который представляет собой реализацию красно-черного дерева.

Он имеет методы Predecessor/TryPredecessor и WeakPredessor/TryWeakPredecessor (а также аналогичные методы для преемников), чтобы легко находить ближайшие элементы в ключе.

Более полезным в вашем случае, я думаю, является метод RangeFrom/RangeTo/RangeFromTo, который позволяет вам получить диапазон пар ключ-значение между клавишами.

Обратите внимание, что все эти методы также могут быть применены к коллекции TreeDictionary<K, V>.Keys, которые позволяют работать только с ключами.

Это очень аккуратная реализация, и что-то подобное заслуживает того, чтобы быть в BCL.

Ответ 3

Невозможно эффективно найти ближайший ключ с помощью SortedList, SortedDictionary или любого другого "встроенного" типа .NET, если вам нужно чередовать запросы со вставками (если ваши данные не будут предварительно отсортированы, или коллекция всегда мала).

Как я уже упоминал по другому вопросу, на который вы ссылались, я создал три структуры данных, связанные с деревьями B +, которые обеспечивают функциональность поиска ближайшего ключа для любого типа сортируемых данных: BList<T>, BDictionary<K,V> и BMultiMap<K,V>. Каждая из этих структур данных предоставляет методы FindLowerBound() и FindUpperBound(), которые работают как С++ lower_bound и upper_bound.

Ответ 4

    public static DateTime RoundDown(DateTime dateTime)
    {
        long remainingTicks = dateTime.Ticks % PeriodLength.Ticks;
        return dateTime - new TimeSpan(remainingTicks);
    }