Как эффективно искать сортировку с неравенством?

Question

Хорошо, говорят, у меня есть строго типизированный SortedSet типа int. Я хочу найти наибольшее число в наборе, которое меньше x.

Возможно, это неправильная структура данных для этого, но мое интуитивное мышление состоит в том, что у меня есть отсортированная коллекция. Конечно, имеет смысл, что я должен выполнять этот тип поиска через платформу .NET?

Answer 1

Поскольку SortedSet не обеспечивает прямой доступ по индексу, вы должны полагаться на перечисление (линейный поиск - O (п)). Возможно, лучшим способом является использование SortedSet.GetViewBetween и Last, но это не похоже на то, что вы можете получить последний элемент без перечисления всех элементов в поле зрения.

Коллекция с прямым доступом по индексу (т.е. List) позволит вам сделать бинарный поиск с O (Lg п) производительность - так что если вам нужно искать много копирования в список мог с ToList дать лучшую производительность при использовании List.BinarySearch (которые дают вам позицию следующего элемента тому, который вы ищете).

// starting sample for BinarySearch approach 
// not handling case where item not in the list (x = 1). 
// List have to be sorted which is the case starting from sorted set: sortedSet.ToList() 
var list = new List<int>{ 1,3, 5, 7, 8,9}; 
var index = list.BinarySearch(8); 
Console.WriteLine(index < 0 ? list[~index - 1] : list[index-1]); 

Answer 2

Если я что-то отсутствует, используйте метод LastOrDefault расширения Linq в:

var lastBefore = set.LastOrDefault(num => num < x); // x is your search number 
if (lastBefore < set.ElementAt(0)) 
{ 
    // Nothing in the set is smaller 
} 
else 
{ 
    // lastBefore is the last number smaller then search number 
}