Может ли LINQ использовать двоичный поиск при заказе коллекции?

Ответ 1

Насколько я знаю, это невозможно при использовании встроенных методов. Однако было бы относительно легко написать метод расширения, который позволит вам написать что-то вроде этого:

var item = myCollection.BinarySearch(i => i.Id, 42);

(предполагая, конечно, что ваша коллекция реализует IList, нет способа выполнить двоичный поиск, если вы не можете получить доступ к элементам случайно)

Здесь пример реализации:

public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
        where TKey : IComparable<TKey>
{
    if (list.Count == 0)
        throw new InvalidOperationException("Item not found");

    int min = 0;
    int max = list.Count;
    while (min < max)
    {
        int mid = min + ((max - min) / 2);
        T midItem = list[mid];
        TKey midKey = keySelector(midItem);
        int comp = midKey.CompareTo(key);
        if (comp < 0)
        {
            min = mid + 1;
        }
        else if (comp > 0)
        {
            max = mid - 1;
        }
        else
        {
            return midItem;
        }
    }
    if (min == max &&
        min < list.Count &&
        keySelector(list[min]).CompareTo(key) == 0)
    {
        return list[min];
    }
    throw new InvalidOperationException("Item not found");
}

(не проверено... может потребоваться несколько настроек) Теперь проверено и исправлено;)

Тот факт, что он выбрасывает InvalidOperationException, может показаться странным, но то, что Enumerable.First делает, когда нет соответствующего элемента.

Ответ 2

Ну, вы можете написать свой собственный метод расширения поверх ObservableCollection<T> - но тогда это будет использоваться для любого ObservableCollection<T>, где доступен ваш метод расширения, не зная, отсортирован он или нет.

Вам также нужно указать в предикате, что вы хотели найти, - что лучше сделать с помощью дерева выражений... но это было бы болью для синтаксического анализа. В принципе, подпись First не подходит для двоичного поиска.

Я предлагаю вам не пытаться перегружать существующие подписи, но писать новый, например.

public static TElement BinarySearch<TElement, TKey>
    (this IList<TElement> collection, Func<TElement, TItem> keySelector,
     TKey key)

(я не собираюсь реализовывать его прямо сейчас, но я могу сделать это позже, если вы захотите.)

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

Ответ 3

Принятый ответ очень хорош.

Однако мне нужно, чтобы BinarySearch возвращал индекс первого элемента, который больше, как это делает List<T>.BinarySearch().

Поэтому я просмотрел его реализацию, используя ILSpy, затем я изменил его, чтобы иметь параметр селектора. Я надеюсь, что это будет так же полезно для кого-то, как для меня:

public static class ListExtensions
{
    public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
    {
        var lo = 0;
        var hi = (int)tf.Count - 1;
        var comp = Comparer<U>.Default;

        while (lo <= hi)
        {
            var median = lo + (hi - lo >> 1);
            var num = comp.Compare(selector(tf[median]), target);
            if (num == 0)
                return median;
            if (num < 0)
                lo = median + 1;
            else
                hi = median - 1;
        }

        return ~lo;
    }
}

Ответ 4

Enumerable.First(predicate) работает с IEnumarable<T>, который поддерживает только перечисление, поэтому он не имеет произвольного доступа к элементам внутри.

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

Enumerable.First(predicate) может только проверять каждый элемент по порядку, когда он просматривает перечисление.

Ответ 5

Имейте в виду, что все (по крайней мере, большинство) методов расширения, используемых LINQ, реализованы на IQueryable<T> или IEnumerable<T> или IOrderedEnumerable<T> или IOrderedQueryable<T>.

Ни один из этих интерфейсов не поддерживает произвольный доступ, поэтому ни один из них не может использоваться для двоичного поиска. Одним из преимуществ чего-то типа LINQ является то, что вы можете работать с большими наборами данных, не возвращая весь набор данных из базы данных. Очевидно, вы не можете бинарно искать что-то, если у вас еще нет всех данных.

Но, как говорили другие, нет никакой причины, вы не можете написать этот метод расширения для IList<T> или других типов коллекций, поддерживающих произвольный доступ.