Есть ли функция нижней границы в SortedList <K, V>? - PullRequest
Новая
       30

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

22 голосов
/ 27 февраля 2009

Есть ли функция нижней границы на 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;
}

Ответы [ 5 ]

20 голосов
/ 27 февраля 2009

Двоичный поиск в коллекции 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);
}
4 голосов
/ 27 февраля 2009

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

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

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

3 голосов
/ 27 февраля 2009

Не знаю, но это простой оператор LINQ: 

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

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

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

Версия DaveW: 

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

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

0 голосов
/ 17 мая 2013

Надеюсь, это будет быстрее, в зависимости от реализации 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;
}
0 голосов
/ 27 февраля 2009

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

...