Есть ли функция Lower Bound на SortedList <K, V>?

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

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

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

Я сделал несколько тестов на этом.

Операторы Linq не оптимизируются ни компилятором, ни машиной времени исполнения, поэтому они проходят через все элементы коллекции и медленны O (n). На основании ответа Мехрдада Афшари, вот двоичный поиск, который работает в O (log n) в коллекции Keys:

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;
}

Ответы

Ответ 1

Двоичный поиск коллекции SortedList.Keys.

Здесь мы идем. Это O (log 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);
}

Ответ 2

Не известно об одном, но это простой оператор LINQ:

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

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

Edit

Версия DaveW:

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 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;
}