c# – Data structure for fast selection of a range of values

Question:

There is an array of objects representing a key and a value. adding and searching through an array of objects is performed.

How to quickly search for objects by a range of keys (for example, if the key is a date, then search by a range of dates, respectively)?

What is the best data structure to use?

Answer:

From suitable data structures – any balanced tree – for example, Red / Black or AVL .

Of the ready-made structures in C#, SortedSet<T> is probably the closest – it has a range search, but there is no native support for storing key-value pairs.

SortedDictionary<K, V> , on the other hand, supports storing pairs, but does not support range searching.

So the easiest way is to use SortedSet , declaring your own container for pairs, which will override comparison and equality:

class KeyValueHolder<TKey, TValue> : IComparable<KeyValueHolder<TKey, TValue>>
    where TKey : IComparable<TKey>
{
    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<TKey, TValue> other)
    {
        return this.Key.CompareTo(other.Key);
    }

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

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

and use it like:

var set = new SortedSet<KeyValueHolder<DateTime, int>>();

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

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

Wrap it in your own container class and add syntactic sugar to taste.

Instead KeyValueHolder , you can use the standard KeyValuePair<K, V> by passing your own IComparer<KeyValuePair<K, V>> to the set constructor for comparison by key.

Inside the SortedSet is Red-Black Tree . Inserting a new element in O(log n), searching for a single element or range is also O(log n). Range search – for linear time.

Of the potential problems – there is dubious code in the range search method that makes it work in linear time on the number of elements found – so if large ranges are regularly found, it is better to write your own implementation.

Solutions based on SortedDictionary<K, V> will also have O(log n)/O(log n) complexity.

If new data is added only at the end, then you can try the option with SortedList<TKey, TValue> . The O(N) complexity of adding when writing in random order makes its use questionable. But if the data is added to the end, then the complexity drops to O(log n).

Searching for a range comes down to searching for two indices. If the boundary values ​​are definitely in the list, then after two calls .IndexOfKey . If not, then binary search. Both options are O(log n).

Using the found indexes, you can get values ​​from .Values – this is IList<TValue> . Retrieval by index in .Values – O(1). The .Values call itself is also O(1).

Post Views: 19
Scroll to Top