SortedDictionary에서 처음 사용되지 않는 키를 빠르게 찾으려면 어떻게해야합니까?

Question

내가 SortedDictionary<int, object> 인 경우 현재 사용되지 않는 가장 낮은 키를 찾는 가장 빠른 방법은 무엇입니까? 분명히 우리는 0->int.MaxValue에서 카운터 i를 반복 할 수 있고 !Keys.Contains(i)이면 탈출 할 수 있습니다. 그러나 운이 좋고 첫 번째 예비 키가 키 시퀀스에서 일찍 일어나지 않으면 매우 느릴 수 있습니다. 어쩌면 다른 .NET 클래스도 이미이 작업을 수행합니까?

Answer 1

그렇다면 올바르게 이해하면 키는 0에서 int.MaxValue 사이 일 수 있습니다. 이 경우, 키의 순서에서 첫 번째 "구멍"을 찾아야합니다.

이

효율적으로 작업을 수행해야합니다 내가 전제 조건이 유효한지 확인하기 위해 검사의 몇 가지를 추가

public static int GetFirstUnusedKey<TValue>(SortedDictionary<int, TValue> dict) 
{ 
    if (dict.Comparer != Comparer<int>.Default) 
     throw new NotSupportedException("Unsupported comparer"); 

    using (var enumerator = dict.GetEnumerator()) 
    { 
     if (!enumerator.MoveNext()) 
      return 0; 

     var nextKeyInSequence = enumerator.Current.Key + 1; 

     if (nextKeyInSequence < 1) 
      throw new InvalidOperationException("The dictionary contains keys less than 0"); 

     if (nextKeyInSequence != 1) 
      return 0; 

     while (enumerator.MoveNext()) 
     { 
      var key = enumerator.Current.Key; 
      if (key > nextKeyInSequence) 
       return nextKeyInSequence; 

      ++nextKeyInSequence; 
     } 

     return nextKeyInSequence; 
    } 
} 

.

Answer 2

나는이 방법에 대한 성능 트로피의 모든 종류의 주장 아니지만, 나는 그것이 당신의 목표를 성취하기 위해 어떻게든지 간다 생각 :이 경우

var sd = new SortedDictionary<int, object>(); 

sd.Add(1, 1); 
sd.Add(2, 1); 
sd.Add(4, 1); 
sd.Add(5, 1); 

var e = Enumerable.Range(1, 5).Except(sd.Keys).First(); 

전자 = 3, 의도 한대로. 그래도 더 나은 해결책이있을 것으로 기대합니다.

Answer 3

대신 (그들은 분류되어 있습니다) 가장 낮은에서 시작 사용 키를 반복 0

에서 사용되지 않는 키의 시작을 검색하지 마십시오.

첫 번째 값이 0보다 크면 0이 가장 낮게 사용되지 않습니다.

두 개의 키 사이에 간격이 있으면 더 낮은 +1이 검색 한 것입니다.

Answer 4

왜 키를 이진 검색하지 않습니까?

ElementAt() 메서드를 사용하여 인덱스에서 키 값을 식별 할 수 있습니다. 키 값이 인덱스보다 큰 경우 왼쪽 하위 사전을 검색하거나 오른쪽을 선택하고 인덱스에서 인덱스의 값과 인덱스의 첫 번째 차이를 관찰 할 인덱스를 찾을 때까지 계속 이동하십시오.