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

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

.net c# sortedlist
person agsamek    schedule 27.02.2009    source источник

Ответы (6)


arrow_upward
26
arrow_downward

Бинарный поиск в коллекции 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);
}
person mmx    schedule 27.02.2009
comment
Разве коллекция не создается каждый раз, когда мы читаем свойство Keys? - person agsamek; 27.02.2009
comment
agsamek: Нет, он не регенерирован. Он вернет экземпляр внутреннего класса KeyList, который обеспечивает прямой доступ к элементам исходной коллекции. В процессе ничего не копируется. - person mmx; 27.02.2009
comment
Отсутствие копии для ключей и значений является основным отличием от SortedDictionary. - person Julien Roncaglia; 27.02.2009
comment
Небольшое замечание, но я считаю, что это неправильно обрабатывает крайний случай, когда все значения в списке меньше ключа. Этот пример возвращает n, но он должен возвращать -1 (или выдавать исключение). - person terphi; 11.05.2012
comment
@terphi Ты прав. В этом случае он вернет 0, что может быть или не быть желаемым результатом в зависимости от контекста. В любом случае это можно исправить оператором if. - person mmx; 11.05.2012
comment
@ralu Вы не можете сделать это без линейного поиска в словаре. - person mmx; 01.12.2012
comment
Чтобы избежать переполнения: var m = low + (hi - low)/2 - person Erwin Mayer; 06.02.2013
comment
Когда список пуст, этот метод выдает исключение... он должен возвращать 0, не так ли? - person digEmAll; 18.12.2015
comment
Этот репозиторий содержит реализацию lower_bound() и upper_bound() для классов C# Array, List и SortedList: github.com /mohanadHamed/MNDSearchUtil - person Mohanad S. Hamed; 11.06.2017
comment
Разве это не O(log(2)N)? - person AgentFire; 18.12.2018
comment
@AgentFire O (log (n, base1)) == O (log (n, base2)) для всех допустимых оснований. доказательство: log(n, base1) = log(n, base2) * log(base1, base2) и log(base1, base2) является константой, что делает его асимптотически неактуальным. Таким образом, вы можете опустить базу, когда говорите об O (log (..)) чего-либо. - person mmx; 18.12.2018
comment
Но если предположить, что сложность вызова list[m] сама по себе является логарифмической, то сложность всей функции оценивается как O(log(n)²), не так ли? - person superbr4in; 17.01.2019
comment
Что ж, стоит упомянуть, что существует разница между просто List‹T› и SortedList‹T› с точки зрения временной сложности. Хотя вы используете IList‹T› для функции BinarySearch, временная сложность будет другой для SortedList‹T›, поскольку доступ к элементу со случайным индексом составляет O (log n). Таким образом, итоговая сложность этого метода составляет O(log² n). - person Boris Parfenenkov; 14.08.2020

arrow_upward
5
arrow_downward

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

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

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

person Dave W    schedule 27.02.2009

arrow_upward
3
arrow_downward

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

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

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

Изменить

Версия DaveW:

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

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

person Garry Shutler    schedule 27.02.2009

arrow_upward
0
arrow_downward

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

person Migol    schedule 27.02.2009

arrow_upward
0
arrow_downward

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

Этот пример реализован как расширение SortedList и возвращает значение наименьшего элемента, большее или равное предоставленному ключу. Он возвращает значение по умолчанию (TValue), если все ключи меньше предоставленного ключа или если был предоставлен пустой список.

public static TValue LowerBound<TKey, TValue>(this SortedList<TKey, TValue> list, TKey key) {
  if (list.Count == 0)
    return default;

  var comparer = list.Comparer;
  if (comparer.Compare(list.Keys[list.Keys.Count - 1], key) < 0)
    return default; // if all elements are smaller, then no lower bound

  int first = 0, last = list.Count - 1;
  while (first < last) {
    var middle = first + (last - first) / 2;
    if (comparer.Compare(list.Keys[middle], key) >= 0)
      last = middle;
    else
      first = middle + 1;
  }
  return list[list.Keys[last]];
}

Пример использования:

SortedList<string, Object> myList = new SortedList<string, Object>();
...
var value = myList.LowerBound<string, Object>("theKey");
person Ferdinand Stapenhorst    schedule 16.03.2021

arrow_upward
-2
arrow_downward

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