Структура данных для быстрой выборки диапазона значений

#c_sharp #алгоритм

Есть массив объектов, представляющих собой ключ и значение. производится добавление
и поиск по массиву объектов.

Как осуществить быстрый поиск объектов по диапазону ключей (например если ключ -
дата, то поиск по диапазону дат соответственно)?

Какую структуру данных лучше использовать?
    

Ответы

Ответ 1

Из подходящих структур данных - любое сбалансированное дерево - например, Red/Black
или AVL.

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

SortedDictionary наоборот, поддерживает хранение пар, но не поддерживает поиск
по диапазону. 

Так что проще всего будет использовать SortedSet, объявив свой контейнер для пар,
который будет переопределять сравнение и equality:

class KeyValueHolder : IComparable>
    where TKey : IComparable
{
    public KeyValueHolder(TKey key, TValue value = default(TValue))
    {
        this.Key = key;
        this.Value = value;
    }

    public TKey Key { get; private set; }
    public TValue Value { get; private set; }

    public int CompareTo(KeyValueHolder other)
    {
        return this.Key.CompareTo(other.Key);
    }

    public override bool Equals(object obj)
    {
        var other = obj as KeyValueHolder;
        return other != null && other.Key.Equals(this.Key);
    }

    public override int GetHashCode()
    {
        return this.Key.GetHashCode();
    }
}


и использовать его как:

var set = new SortedSet>();

for (int i = -5; i < 5; i++)
{
    set.Add(new KeyValueHolder(DateTime.Now.AddDays(i), i));
}

// найдет пары от -2 до 2
set.GetViewBetween(
    new KeyValueHolder(DateTime.Now.AddDays(-2.5)),
    new KeyValueHolder(DateTime.Now.AddDays(2.5))
    ).ToList().ForEach((kv) => Console.WriteLine(kv.Value));


Обернуть это в свой класс-контейнер и добавить синтаксический сахар по вкусу.

Вместо KeyValueHolder можно использовать стандартный KeyValuePair передав set-у
в конструктор свой IComparer> для сравнения по ключу.

Внутри у SortedSet - Red-Black Tree. Вставка нового элемента за O(log n), поиск одного
элемента или диапазона - тоже за O(log n). Перебор диапазона - за линейное время.

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

У решений на основе SortedDictionary сложность будет тоже O(log n)/O(log n).


Если новые данные добавляются только в конец - то можно попробовать вариант с SortedList.Сложность добавления при записи в случайном порядке O(N) делает его применение
сомнительным. Но если данные добавляются в конец, то сложность падает до O(log n). 

Поиск диапазона сводится к поиску двух индексов. Если граничные значения точно есть
в списке - то через два вызова .IndexOfKey. Если нет - то бинарным поиском. Оба варианта
- O(log n).

По найденным индексам можно достать значения из .Values - это IList. Обращение
по индесу в .Values - O(1). Сам по себе вызов .Values - тоже O(1).


Ответ 2

Думаю, вам нужен упорядоченный словарь.

Это map в C++ или SortedDictionary в .NET.

Например, в std::map элементы в данном диапазоне лежат в последовательном куске,
который начинается с итератора map.lower_bound(kmin) и заканчивается итератором map.upper_bound(kmax).
Нахождение обоих итераторов логарифмическое.

Для SortedDictionary у вас нету функций наподобие Lower/UpperBound, но их легко
заимплементировать самому при помощи бинарного поиска по SortedDictionary.Keys
(который выдаёт отсортированный список ключей).



Как оказалось, SortedDictionary.Keys не имплементирует IList, и значит,
в нём нельзя использовать двоичный поиск. Это явный недостаток BCL. В таком случае
воспользуйтесь SortedSet с кастомным компаратором.