Получить самый большой ключ в словаре

У меня есть словарь с ключами, которые являются ints. Я хотел бы получить самый большой ключ. Я не отслеживаю ключи, поэтому они могут быть последовательными (например, 1,2,3,4,5,6), но могут пропустить (1,3,4,5), хотя я сомневаюсь, что это имеет значение.

Я просто использую двоичный поиск или есть метод? Насколько я вижу, вы вряд ли можете бить бинарный поиск такой простой задачи - возможно, вы можете вдвое уменьшить ее.

Ответы

Ответ 1

Если у вас есть LINQ, вы должны иметь возможность:

myDictionary.Keys.Max();

Ответ 2

Бинарный поиск будет самым быстрым, но не будет работать против нормального словаря, поскольку ключи не сохраняются в каком-либо конкретном порядке. Ответ @Minitech, используя Linq Max(), является самым легким, если вы используете обычный словарь.

Если это операция, вам придется делать много раз, вы можете подумать о переходе к SortedDictionary<TKey, TValue>, который сортирует записи на основе ключа.

var dict = new SortedDictionary<int, int> {{3, 0}, {12, 0}, {32, 0}, 
                                           {2, 0}, {16, 0}, {20, 0}};
Console.WriteLine(dict.Keys.Last()); //prints 32

EDIT: это может быть медленнее обычного словаря. Полагаю, было бы хорошо упомянуть об этом. Это потому, что записи в словаре хранятся по-другому (красное/черное дерево против хэш-таблиц/хэш-таблица)

Там есть точка, в которой SortedDictionary становится быстрее обычного Dictionary. Однако, вероятно, это будет около 1 миллиона предметов, однако это просто предположение. Оказывается, это примерно в 10 раз быстрее на этом множестве предметов (но мы все равно говорим о 100-м секунде, так ли это имеет значение?). Это примерно равное по версии x64 для 100000 элементов. Учитывая дополнительные накладные расходы на добавление предметов в словарь, это, вероятно, не стоит. Кроме того, я немного "обманул", переопределив сравнитель, чтобы сортировать в обратном порядке, поэтому я фактически делаю dict.Keys.First() вместо последнего, чтобы получить самый большой элемент.

A SortedDictionary действительно предназначен для того, чтобы вам было необходимо перебирать все пары ключевых значений по порядку. Я думаю, что ответ @SimonMourier, вероятно, лучший. Я гарантирую вам это быстрее, с минимальными накладными расходами.

Ответ 3

Если производительность действительно является проблемой, я бы создал новый класс поверх существующего, реализуя стандартные интерфейсы, например:

    public class RememberMaxDictionary<K, V> : IDictionary<K, V> where K: IComparable<K>
    {
        private Dictionary<K, V> _inner;

        public RememberMaxDictionary()
        {
            _inner = new Dictionary<K, V>();
        }

        public K MaxKey { get; private set; }

        public void Add(K key, V value)
        {
            _inner.Add(key, value);

            if (key.CompareTo(MaxKey) > 0) // test null if needed
            {
                MaxKey = key;
            }
        }

    ... TODO implement the rest...