SortedList 에 하한 함수가 있습니까?
-
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;
}