"가장 가까운 키 찾기"작업을 지원하는 .NET 사전은 무엇입니까?

Question

일부 C++ 코드를 C#으로 변환 중이고 키가 k 이상인 항목을 찾기 위해 std :: map :: lower_bound (k)를 호출합니다. 그러나 .NET의 SortedDictionary를 사용하여 동일한 작업을 수행 할 수있는 방법은 없습니다. 나는 SortedList를 사용하여 해결 방법을 구현할 수 있다고 생각하지만, 불행하게도 SortedList는 너무 느립니다 (O (n) 키 삽입 및 삭제). 내가 무엇을 할 수 있을지?

참고 : 내 특정 시나리오를 활용하는 해결 방법을 발견했습니다 ... 특히, 내 키는 정수가 0보다 조금 작기 때문에 List <TValue>을 사용하여 리스트 인덱스를 키로서 제공하고, k보다 크거나 같은 키를 검색하는 것은 단지 몇 번의 루프 반복으로 행해질 수있다. 그러나 원래의 질문에 답하는 것이 여전히 좋을 것입니다.

dict.Keys.Where(i => i >= K).OrderBy(i => i).First(); 

또는 훨씬 더 빨리 :

Answer 1

어떤 데이터 형식에 대해서도이 기능을 제공하는 B + 트리와 관련된 세 가지 데이터 구조를 만들었습니다 : BList<T>, BDictionary<K,V> and BMultiMap<K,V>. 이러한 각각의 데이터 구조는 FindLowerBound() 및 FindUpperBound() 메서드를 제공하며 C++의 lower_bound 및 upper_bound과 같은 식으로 작동합니다.

Answer 2

의가 K에 가장 가까운을 찾을 수이

Dictionary<string, int> dict = ... 
\\and you have 
k \\- is the key to find or if it is not than at least greater 
\\ you write 

var entry = dict.Where(o => o.key >= k).First(); 

Answer 3

뭔가가 있다고 가정 해 보자

public int? GetNearestKey(dict, K) 
{ 
    int? lowerK = null; 
    foreach (int key in dict.Keys) 
    { 
     if (key == K) 
     { 
      lowerK = K; 
      break; 
     } 
     else if (key >= K && (!lowerK.HasValue || key < lowerK)) 
     { 
      lowerK = key; 
     } 
    } 
    return lowerK; 
} 

Answer 4

문제는 사전/해시 테이블이 입력 값을 기반으로 고유 한 메모리 위치에 도달하도록 설계되었으므로 다음과 같은 목적으로 설계된 데이터 구조가 필요합니다. 당신이 저장하는 각 값과 관련된 범위를 수용하고 동시에 각 간격을 정확하게 업데이트하십시오.

제가 생각하기에 skip lists (또는 균형 이진 나무)이 도움이 될 수 있습니다. 그들은 O (n)에서 룩업을 수행 할 수는 없지만 나무보다 로그 적으로 더 빠르게 수행 할 수 있습니다.

.NET BCL에 이미 이러한 클래스가 포함되어 있다고 말할 수 없기 때문에 이것이 적절하지 않습니다. 불행히도 직접 구현하거나 자신을 지원하는 타사 어셈블리를 찾아야합니다. 그래도 좋은 예가 The CodeProject here 인 것 같습니다.

Answer 5

기본 프레임 워크에 이진 검색 트리 컬렉션 구현이 없으므로 하나를 작성하거나 구현을 찾아야합니다. 아시는 바와 같이, SortedList는 검색 측면에서 가장 비슷하지만 삽입/삭제에 대한 기본 배열 구현으로 인해 속도가 느립니다.

Answer 6

복잡성에 대한 질문에서 실수가 있다고 생각합니다.

SortedList에는 inserting 새 항목의 O (log (n)) 상각 된 복잡성이 있습니다. 용량을 미리 아는 경우 최악의 경우 O (Log (n))로 수행 할 수 있습니다.

Answer 7

아래 코드를 시도해 볼 수 있습니다. 이진 검색을 사용하므로 목록/배열이 미리 정렬되어 있다고 가정합니다.

public static class ListExtensions 
{ 
    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer) 
    { 
     return GetAtMostIndex(list, value, comparer, 0, list.Count); 
    } 

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer) 
    { 
     return GetAtLeastIndex(list, value, comparer, 0, list.Count); 
    } 

    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count) 
    { 
     if (count == 0) 
     { 
      return -1; 
     } 

     int startIndex = index; 
     int endIndex = index + count - 1; 
     int middleIndex = 0; 
     int compareResult = -1; 

     while (startIndex < endIndex) 
     { 
      middleIndex = (startIndex + endIndex) >> 1; ///2 
      compareResult = comparer.Invoke(list[middleIndex], value); 

      if (compareResult > 0) 
      { 
       endIndex = middleIndex - 1; 
      } 
      else if (compareResult < 0) 
      { 
       startIndex = middleIndex + 1; 
      } 
      else 
      { 
       return middleIndex; 
      } 
     } 

     if (startIndex == endIndex) 
     { 
      compareResult = comparer.Invoke(list[startIndex], value); 

      if (compareResult <= 0) 
      { 
       return startIndex; 
      } 
      else 
      { 
       int returnIndex = startIndex - 1; 

       if (returnIndex < index) 
       { 
        return -1; 
       } 
       else 
       { 
        return returnIndex; 
       } 
      } 
     } 
     else 
     { 
      //todo: test 
      return startIndex - 1; 
     } 
    } 

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count) 
    { 
     if (count == 0) 
     { 
      return -1; 
     } 

     int startIndex = index; 
     int endIndex = index + count - 1; 
     int middleIndex = 0; 
     int compareResult = -1; 

     while (startIndex < endIndex) 
     { 
      middleIndex = (startIndex + endIndex) >> 1; ///2 
      compareResult = comparer.Invoke(list[middleIndex], value); 

      if (compareResult > 0) 
      { 
       endIndex = middleIndex - 1; 
      } 
      else if (compareResult < 0) 
      { 
       startIndex = middleIndex + 1; 
      } 
      else 
      { 
       return middleIndex; 
      } 
     } 

     if (startIndex == endIndex) 
     { 
      compareResult = comparer.Invoke(list[startIndex], value); 

      if (compareResult >= 0) 
      { 
       return startIndex; 
      } 
      else 
      { 
       int returnIndex = startIndex + 1; 

       if (returnIndex >= index + count) 
       { 
        return -1; 
       } 
       else 
       { 
        return returnIndex; 
       } 
      } 
     } 
     else 
     { 
      return endIndex + 1; 
     } 
    } 
} 

Answer 8

그것은 작품의 몇 개월이 걸렸지 만 마침내 난 ... 컴팩트 패트리샤 트리는, A는 "다음으로 큰 찾을 제공하는 정렬 된 사전을 호출이 문제에 대한 최소한 부분적인 해결책을 제공 할 수 있습니다 키 "작동.

http://www.codeproject.com/KB/recipes/cptrie.aspx

그것은 단지 특정 키 종류부터 용액 부분, 즉 byte[], string을지지되고있어 모든 프리미티브 정수형 (Int8..UInt64).또한 문자열 정렬은 대소 문자를 구분합니다.

Answer 9

당신은 다음과 같은 확장 방법과 SortedSet<T>이 작업을 수행 할 수 있습니다

public static class SortedSetExtensions 
{ 
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first) 
    { 
     if(set.Count == 0) 
     { 
      first = default(T); 
      return false; 
     } 

     var minimum = set.Min; 

     if(set.Comparer.Compare(minimum, value) > 0) 
     { 
      first = default(T); 
      return false; 
     } 

     first = set.GetViewBetween(minimum, value).Max; 
     return true; 
    } 

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first) 
    { 
     if (set.Count == 0) 
     { 
      first = default(T); 
      return false; 
     } 

     var maximum = set.Max; 

     if (set.Comparer.Compare(maximum, value) < 0) 
     { 
      first = default(T); 
      return false; 
     } 

     first = set.GetViewBetween(value, maximum).Min; 
     return true; 
    } 
}