SortedList 에 하한 함수가 있습니까?

StackOverflow https://stackoverflow.com/questions/594518

  •  09-09-2019
  •  | 
  •  

문제

a에 하한 함수가 있습니까? SortedList<K ,V>? 함수는 지정된 키와 같은 첫 번째 요소를 반환해야합니다. 이것을 지원하는 다른 수업이 있습니까?

여러분 - 질문을 다시 한 번 읽으십시오. 키가 존재하는 경우 키를 반환하는 함수가 필요하지 않습니다. 정확한 키 일치가 없을 때 시나리오에 관심이 있습니다.

나는 O (log n) 시간에 관심이 있습니다. 그것은 Foreach Loop에 문제가 없지만이를 수행하는 효율적인 방법을 원한다는 것을 의미합니다.

나는 이것에 대해 약간의 테스트를했다.

LINQ 문은 컴파일러 나 런타임 머신에 의해 최적화되지 않으므로 모든 수집 요소를 걸어 가고 느린 O (N)입니다. Mehrdad Afshari 답변을 기반으로 Keys Collection에서 O (log n)에서 작동하는 이진 검색이 있습니다.

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
            this IList<T> sortedCollection, T key
        ) where T : IComparable<T> {
    int begin = 0;
    int end = sortedCollection.Count;
    while (end > begin) {
        int index = (begin + end) / 2;
        T el = sortedCollection[index];
        if (el.CompareTo(key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}
도움이 되었습니까?

해결책

이진 검색 SortedList.Keys 수집.

여기 우리는 간다. 이것은 O입니다 (로그 N):

private static int BinarySearch<T>(IList<T> list, T value)
{
    if (list == null)
        throw new ArgumentNullException("list");
    var comp = Comparer<T>.Default;
    int lo = 0, hi = list.Count - 1;
    while (lo < hi) {
            int m = (hi + lo) / 2;  // this might overflow; be careful.
            if (comp.Compare(list[m], value) < 0) lo = m + 1;
            else hi = m - 1;
    }
    if (comp.Compare(list[lo], value) < 0) lo++;
    return lo;
}

public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
                          (this SortedList<T,U> sortedList, T key)
{
    return BinarySearch(sortedList.Keys, key);
}

다른 팁

나는 LINQ와 함께 가고 (C#3을 사용하고 있다고 가정), 그러나 술어를 취하는 FirstOrdeFault의 과부하를 사용합니다.

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

(다른 열거 가능한 많은 방법은 또한 좋은 지름길 인 Predicates를 취할 수 있습니다)

하나는 알지 못하지만 간단한 LINQ 문입니다.

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();

first 비교를 통과하는 첫 번째 대상이거나 default(T) (일반적으로 null).

편집하다

Davew의 버전 :

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

같은 작업을 수행하지만 잠재적으로 더 빠를 수 있습니다. 그래도 테스트해야합니다.

또는이를 위해 자체 확장 방법을 작성할 수 있습니다. 이러한 모든 기능이 시퀀스에 들어가는 것을 보장하지는 않습니다.

SortedList의 구현에 따라 더 빠르기를 바랍니다.

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
        this SortedList<K, V> sortedCollection, K key
    ) where V : new()
{
    if (sortedCollection.ContainsKey(key))
    {
        return sortedCollection.IndexOfKey(key);
    }
    sortedCollection[key] = new V();
    int retval = sortedCollection.IndexOfKey(key);
    sortedCollection.Remove(key);
    return retval;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top