Есть ли функция с нижней границей в SortedList<K ,V="">?

Question

Существует ли функция с нижней границей на SortedList<K ,V>?Функция должна возвращать первый элемент, равный или больший указанному ключу.Есть ли какой-то другой класс, который поддерживает это?

Ребята, пожалуйста, прочтите вопрос еще раз. Мне не нужна функция, которая возвращает ключ, если он присутствует.Меня интересует сценарий, когда нет точного совпадения ключей.

Меня интересует время O (log n).Это означает, что у меня нет проблем с циклом foreach, а скорее хотелось бы иметь эффективный способ сделать это.

Я провел несколько тестов по этому поводу.

Инструкции Linq не оптимизированы ни компилятором, ни машиной выполнения, поэтому они проходят через все элементы коллекции и работают медленно O (n).Основываясь на ответе Мехрдада Афшари, вот бинарный поиск, который работает в 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;
}

Answer 1

Бинарный поиск в 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);
}

Answer 2

Я бы выбрал LINQ (предполагая, что вы используете C # 3), но используя перегрузку FirstOrDefault, которая принимает предикат:

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

(многие другие перечислимые методы также могут принимать предикаты, что является хорошим сокращением)

Answer 3

Не знаю ни одного, но это простое утверждение LINQ:

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

first будет либо первым объектом, который проходит сравнение, либо default(T) (что обычно null).

Редактировать

Версия Дейвью:

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

выполняет ту же работу, но потенциально может быть быстрее, однако вам придется это протестировать.

Answer 4

Или вы можете написать собственный метод расширения, чтобы сделать это.Обратите внимание, что НЕ гарантируется, что все эти функции будут выполняться последовательно.

Answer 5

Надеюсь, это должно быть быстрее, в зависимости от реализации 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;
}