사전에서 가장 큰 키 얻기

Question

int가있는 키가있는 사전이 있습니다. 가장 큰 열쇠를 얻고 싶습니다. 키를 추적하지 않아 연속적 (예 : 1,2,3,4,5,6) 일 수는 있지만 건너 뛸 수 있습니다 (1,3,4,5).

방금 ​​이진 검색을 사용합니까, 아니면 방법이 있습니까? 내가 아는 한 간단한 작업을 위해 이진 검색을 수행 할 수는 없습니다. 아마도이 작업을 절반으로 줄일 수 있습니다.

Answer 1

사용 가능한 LINQ가있는 경우, 당신은 할 수 있어야한다 :

myDictionary.Keys.Max(); 

Answer 2

이진 검색이 가장 빠른 것입니다하지만 키가 어떤에 저장되지 않기 때문에, 보통 사전에 작동하지 않을 것입니다 특정 순서. Linq Max()을 사용하여 @ Minitech의 대답은, 당신이 정상적인 사전을 사용하는 경우 가장 쉽습니다.

이 작업을 여러 번 수행해야하는 경우 키를 기반으로 항목을 정렬하는 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 

편집 :이 은 일반 사전보다 더 속도가 느려질 수 있습니다. 나는 그것을 언급하는 것이 좋았을 것입니다. 사전의 항목이 다른 방식으로 저장되기 때문에 그건 (레드/블랙 트리 해시 버킷/해시 테이블 대)

는는 SortedDictionary이 정상 Dictionary보다 더 빨리하게하는 지점이있다. 그러나 이것은 아마도 약 1 백만 품목으로 나올 것입니다. 그러나 그것은 단지 추측입니다. 그것은 많은 아이템에서 약 10 배 더 빠릅니다. (어쨌든 우리는 약 100 분의 1 초를 말하는 것입니다. 그렇다면 은 실제로일까요?). 100000 개 항목에 대해 x64에서 거의 동일합니다. 사전에 항목을 추가 할 때 추가로 발생하는 오버 헤드가 있음을 감안하면 그럴 가치가 없을 것입니다. 또한 비교자를 재정의하여 조금 "속이기"때문에 반대 순서로 정렬되므로 실제로 가장 큰 항목을 얻는 데 마지막으로 dict.Keys.First()을 수행하고 있습니다.

SortedDictionary는 모든 키 값 쌍을 순서대로 반복해야하는 경우에 유용합니다. 나는 @ SimonMourier의 대답이 아마도 최고라고 생각한다. 최소한의 오버 헤드로 가장 빠릅니다. 성능이 문제가 정말 경우

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