Эффективная Сортированная Карта Int32/Uint32 / Разреженный Массив

Question

Я ищу специализированную (и быструю) отсортированную карту Int32/UInt32 (которая предпочтительно быстрее, чем System.Collections.Generic.SortedDictionary, где K - это либо Int32, либо UInt32).

Он будет использоваться в качестве разреженного массива, есть ли реализации для.NET?

Answer 1

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

public class DoubleDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private Dictionary<TKey, TValue> backingHash = new Dictionary<TKey, TValue>();
    private SortedDictionary<TKey, TValue> backingTree = new SortedDictionary<TKey, TValue>();

    // For all the modify methods, do it in both.
    // For all retrieval methods, pick one of the backing dictionaries, and just use that one.
    // For example, contains and get on the Hash, iteration on the Tree.
}