LINQ可以在收集被排序时使用二进制搜索吗? [英] Can LINQ use binary search when the collection is ordered?
问题描述
我可以以某种方式指示LINQ使用二进制搜索时,我试图搜索的集合是有序的。我使用 ObservableCollection< T>
,填充有序数据,我试图使用 Enumerable.First(< 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;没有办法执行二叉搜索if您不能随机访问这些项目)
(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屋!