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

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

22 голосов
/ 29 ноября 2011

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

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

Ответы [ 3 ]

38 голосов
/ 29 ноября 2011

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

myDictionary.Keys.Max();
8 голосов
/ 29 ноября 2011

Бинарный поиск будет самым быстрым, но не будет работать с обычным словарем, поскольку ключи хранятся не в каком-либо определенном порядке.Ответ @ 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

РЕДАКТИРОВАТЬ: может быть медленнее , чем обычный словарь.Я полагаю, было бы хорошо упомянуть об этом.Это связано с тем, что записи в словаре хранятся по-разному (красное / черное дерево по сравнению с хеш-таблицами / хэш-таблицами)нормальный Dictionary.Тем не менее, это, вероятно, будет около 1 миллиона предметов, однако это только предположение.Оказывается, это примерно в 10 раз быстрее при таком количестве предметов (но мы все равно говорим о сотых долях секунды, так ли это действительно имеет значение?).Это примерно равно выпуску x64 для 100000 наименований.Учитывая дополнительные затраты на добавление элементов в словарь, это, вероятно, того не стоит.Кроме того, я немного «обманул», переопределив компаратор, чтобы он сортировал в обратном порядке, поэтому я на самом деле делаю dict.Keys.First() вместо последнего, чтобы получить самый большой элемент.если вам нужно перебрать все пары Key Value по порядку.Я думаю, что ответ @ SimonMourier, вероятно, лучший.Я гарантирую вам, что это самый быстрый, с минимальными накладными расходами.

2 голосов
/ 29 ноября 2011

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

    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...
...