22

検索しようとしているコレクションが注文されたときに、バイナリ検索を使用するようにLINQに何らかの方法で「指示」できますか。順序付けされたデータが入力されたを使用しており、 Enumerable.First（<Predicate>）ObservableCollection<T>を使用しようとしています。私の述語では、コレクションがソートされたフィールドの値でフィルタリングしています。

4

5 に答える 5

33

私の知る限り、組み込みメソッドでは不可能です。ただし、次のような記述を可能にする拡張メソッドを作成するのは比較的簡単です。

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ませんが、一致するアイテムがない場合はそうなります。

于 2009-11-19T20:42:40.967 に答える
8

受け入れられた答えはとても良いです。

ただし、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;
    }
}
于 2014-04-15T18:55:36.413 に答える
2

さて、あなたはあなた自身の拡張メソッドを上書きすることができますObservableCollection<T>-しかしそれはあなたの拡張メソッドが利用可能であるところならどこでも ObservableCollection<T>それがソートされているかどうかを知らなくても使用されます。

また、述語で何を見つけたいかを示す必要があります。これは、式ツリーを使用した方が適切です...しかし、それを解析するのは面倒です。基本的に、の署名はFirst二分探索にはあまり適していません。

既存の署名をオーバーロードしようとせずに、新しい署名を作成することをお勧めします。

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

（今は実装しませんが、必要に応じて後で実装できます。）

関数を提供することにより、アイテム自体ではなく、コレクションがソートされているプロパティで検索できます。

于 2009-11-19T20:42:56.270 に答える
1

LINQで使用されるすべての（少なくともほとんどの）拡張メソッドは、IQueryable<T>orIEnumerable<T>またはIOrderedEnumerable<T>orに実装されていることに注意してIOrderedQueryable<T>ください。

これらのインターフェイスはいずれもランダムアクセスをサポートしていないため、バイナリ検索に使用することはできません。LINQのようなものの利点の1つは、データベースからデータセット全体を返す必要なしに、大きなデータセットを操作できることです。明らかに、まだすべてのデータがない場合は、何かをバイナリ検索することはできません。

IList<T>しかし、他の人が言っているように、ランダムアクセスをサポートする他のコレクションタイプに対してこの拡張メソッドを記述できない理由はまったくありません。

于 2009-11-19T21:39:01.273 に答える
1

Enumerable.First(predicate)列挙のみをサポートするで動作IEnumarable<T>するため、内部のアイテムにランダムにアクセスすることはできません。

また、述語には、最終的にtrueまたはfalseになる任意のコードが含まれているため、テストされたアイテムが低すぎるか高すぎるかを示すことはできません。この情報は、二分探索を行うために必要になります。

Enumerable.First(predicate)列挙をウォークスルーするときに、各アイテムを順番にテストすることしかできません。

于 2009-11-19T20:42:08.753 に答える