Zdobądź największy klucz w słowniku

Question

Mam słownik z kluczami, które są ints. Chciałbym zdobyć największy klucz. Nie śledzę kluczy, więc mogą być kolejne (np. 1,2,3,4,5,6), ale mogę pominąć (1,3,4,5), choć wątpię, by to miało jakikolwiek wpływ.

Czy po prostu używam wyszukiwania binarnego lub czy istnieje metoda? O ile widzę, trudno jest pokonać wyszukiwanie binarne dla tak prostego zadania - być może można go zmniejszyć o połowę.

Answer 1

Jeśli masz LINQ dostępne, powinieneś być w stanie to zrobić:

Answer 2

poszukiwania binarnego byłby najszybszy, ale nie będzie działać przeciwko zwykłym słowniku, ponieważ klucze nie są przechowywane w żadnym konkretna kolejność. Odpowiedź @ Minitech, używając Linq Max(), jest najłatwiejsza, jeśli używasz zwykłego słownika.

Jeśli jest to operacja, którą musisz wykonać wiele razy, możesz rozważyć przejście na numer SortedDictionary<TKey, TValue>, który sortuje wpisy na podstawie klucza.

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 

Edycja: ta może być niższa od normalnej słownika. Przypuszczam, że dobrze byłoby o tym wspomnieć. To dlatego, że wpisy w słowniku są przechowywane w inny sposób (a Red/Black drzewo vs łyżki stołowe/hash hash)

Nie jest punkt że SortedDictionary staje się szybciej niż normalny Dictionary. Jednak prawdopodobnie wyniesie to około 1 miliona pozycji, ale to tylko przypuszczenie. Okazuje się, że jest to około 10 razy szybsze przy tak wielu elementach (ale i tak mówimy o setnych częściach sekundy, więc czy to naprawdę jest , naprawdę, czy jest to?). Jest prawie równy w wydaniu x64 dla 100 000 elementów. Biorąc pod uwagę, że dodatkowe dodatki do słownika są dodatkowe, prawdopodobnie nie warto. Ponadto, trochę "oszukałem", przesłoniłem porównywarkę, aby sortować w odwrotnej kolejności, więc robię to w miejsce dict.Keys.First() zamiast ostatniego, aby uzyskać największy przedmiot.

SortedDictionary jest naprawdę przeznaczony do iteracji wszystkich par Key Value w kolejności. Myślę, że odpowiedź @ SimonMourier jest prawdopodobnie najlepsza. Gwarantuję ci, że to najszybszy, przy minimalnym obciążeniu.

Answer 3

Jeśli wydajność jest naprawdę problem, chciałbym stworzyć nową klasę na szczycie istniejącej, wdrażanie standardowych interfejsów, takich jak to:

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