Получить последний элемент в SortedDictionary

Question

Я вижу этот вопрос.

Как я могу получить последний элемент в SortedDictionary в.Net 3.5.

Answer 1

Вы можете использовать LINQ:

var lastItem = sortedDict.Values.Last();

Вы также можете получить последний ключ:

var lastkey = sortedDict.Keys.Last();

Вы даже можете получить последнюю пару ключ-значение:

var lastKeyValuePair = sortedDict.Last();

Это даст вам KeyValuePair<TKey, TValue> с Key а также Value свойства.

Обратите внимание, что это вызовет исключение, если словарь пуст; если ты не хочешь этого, позвони LastOrDefault,

Answer 2

Last метод extension даст вам результат, но для этого вам придется перечислить всю коллекцию. Это такой позор SortedDictionary<K, V> не выставляет Min а также Max Члены особенно учитывая внутренне это поддерживается SortedSet<KeyValuePair<K, V>> у которого есть Min а также Max свойства.

Если O(n) нежелателен, у вас есть несколько вариантов:

1. Переключиться на SortedList<K, V>, Опять же, по какой-то причине BCL не упаковывает это по умолчанию. Вы можете использовать индексаторы, чтобы получить максимальное (или минимальное) значение за время O(1). Расширение с помощью методов расширения будет хорошо.

   //Ensure you dont call Min Linq extension method.
   public KeyValuePair<K, V> Min<K, V>(this SortedList<K, V> dict)
   {
       return new KeyValuePair<K, V>(dict.Keys[0], dict.Values[0]); //is O(1)
   }
   
   //Ensure you dont call Max Linq extension method.
   public KeyValuePair<K, V> Max<K, V>(this SortedList<K, V> dict)
   {
       var index = dict.Count - 1; //O(1) again
       return new KeyValuePair<K, V>(dict.Keys[index], dict.Values[index]);
   }
   

   SortedList<K, V> приходит с другими штрафами. Так что вы можете захотеть увидеть: в чем разница между SortedList и SortedDictionary?

2. Написать свой SortedDictionary<K, V> учебный класс. Это очень тривиально. Есть SortedSet<KeyValuePair<K, V>> в качестве внутреннего контейнера и основывать сравнение на Key часть. Что-то вроде:

   public class SortedDictionary<K, V> : IDictionary<K, V>
   {
       SortedSet<KeyValuePair<K, V>> set; //initialize with appropriate comparer
   
       public KeyValuePair<K, V> Min { get { return set.Min; } } //O(log n)
       public KeyValuePair<K, V> Max { get { return set.Max; } } //O(log n)
   }
   

   Это O(log n). Не задокументировано, но я проверил код.

3. Используйте легкомысленное отражение, чтобы получить доступ к вспомогательному набору, который является частным членом SortedDictionary<K, V> класс и вызвать Min а также Max свойства. Можно использовать выражения для компиляции делегата и его кэширования для повышения производительности. Это очень плохой выбор. Не могу поверить, что я предложил это.

4. Положитесь на другие реализации, например. За TreeDictionary<K, V> от С5. У них есть FindMin а также FindMax оба из которых O (log n)

Answer 3

Ты можешь использовать SortedDictionary.Values.Last();

или если вы хотите ключ и значение

SortedDictionary.Last();

Answer 4

Список отсортированных списков...

list[ Keys[Keys.Count - 1] ];  // returns the last entry in list

Answer 5

Как уже указали люди, последнее расширение будет перечислять всю коллекцию, его влияние на производительность может быть смертельным. Просто чтобы удалить 10000 последних элементов из SortedDict, потребовалось намного больше времени, чем аналогичная операция для SortedSet.

1. Удаление SortedSet Истекшее мс: 8

2. Удаление SortedDict Истекшее мс: 3697

   // В приведенном ниже коде ss - это SortedSet, а sd - SortedDictionary, и оба содержат одинаковые 10000 элементов.

    sw.Start();
    while (ss.Count != 0)
    {
        ss.Remove(ss.Max);
    }
   
    sw.Stop();
    Console.WriteLine("SortedSet Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);
   
    sw.Reset();
   
    sw.Start();
    while (sd.Count != 0)
    {
        sd.Remove(sd.Keys.Last());
    }
   
    sw.Stop();
    Console.WriteLine("Dict Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);