LINQ可以使用二进制搜索集合时是有序? [英] Can LINQ use binary search when the collection is ordered?
问题描述
我可以以某种方式指示LINQ使用二进制搜索时我试图搜索的集合是有序的。我使用的是的ObservableCollection< T>
,填充了有序的数据,我试图用<一个href=\"http://msdn.microsoft.com/en-us/library/bb535050.aspx\">Enumerable.First(<$p$pdicate>).在我的predicate,我被我收藏的排序中字段的值过滤。
Can I somehow "instruct" LINQ to use binary search when the collection that I'm trying to search is ordered. I'm using an ObservableCollection<T>
, populated with ordered data, and I'm trying to use Enumerable.First(<Predicate>). In my predicate, I'm filtering by the value of the field my collection's sorted by.
推荐答案
据我所知,这是不可能的内置方法。然而,它会相对容易编写扩展方法,允许你写类似的东西:
As far as I know, it's not possible with the built-in methods. However it would be relatively easy to write an extension method that would allow you to write something like that :
var item = myCollection.BinarySearch(i => i.Id, 42);
(假设,当然,前提是你收集实现IList的,没有任何办法来执行二进制搜索,如果你不能访问该项目随机)
(assuming, of course, that you collection implements IList ; there's no way to perform a binary search if you can't access the items randomly)
下面是一个示例实现:
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
确实没有当匹配的项目。
The fact that it throws an InvalidOperationException
may seem strange, but that's what Enumerable.First
does when there's no matching item.
这篇关于LINQ可以使用二进制搜索集合时是有序?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!