LINQ to Objects和具有索引的改进性能? [英] LINQ to Objects and improved perf with an Index?

问题描述

我正在使用LINQ to Objects，想知道是否有可能通过利用我拥有的索引来提高查询性能.最好用一个例子来解释.想象一个简单的类型...

I am using LINQ to Objects and wonder if it is possible to improve the performance of my queries by making use of an index that I have. This is best explained with an example. Imagine a simple type...

public class Person
{
    public int Age;
    public string FirstName;
    public string LastName;
}

还有一个我会针对它的简单查询...

And a simple query I would make against it...

List<Person> people = new List<Person>();

// 'people' populated with 50,000 instances...

var x = from t in people
        where t.Age > 18 && t.Age < 21
        select t;

如果我正确理解LINQ to Objects，则Where扩展方法的实现将枚举people集合中的所有50,000个实例，以便找到实际匹配的100个实例.碰巧的是，我已经有了按年龄分类的人员集合索引.这样...

If I understand LINQ to Objects correctly then the implementation of the Where extension method will enumerate all 50,000 instances in the people collection in order to find the 100 that actually match. As it happens I already have an index of the people collection that is sorted by Age. Like this...

SortedList<int, Person> ageSorted = new SortedList<int, Person>();

很显然，如果我能获得使用SortedList的位置是有意义的，那么它不再需要枚举所有50,000个实例，而是找到100个匹配条目的范围，从而节省了时间.

Clearly it would make sense if I could get the Where to use the SortedList so that it no longer has to enumerate all 50,000 instances, instead finding the range of 100 matching entries and so saving time.

是否可以将LINQ扩展到对象以实现我的情况?已经可以，但是我错过了这项技术吗?

Is it possible to extend LINQ to Objects to enable my situation? Is it already possible but I am missing the technique?

推荐答案

我相信已经有一个项目可以完全做到这一点- i4o .我不能说我自己使用过它，但这听起来像是您想要的那种东西……您可能需要稍微修改一下现有代码，但这当然值得一看.

There's already a project which I believe does exactly that - i4o. I can't say I've used it myself, but it sounds like the kind of thing you want... you may need to juggle your existing code a bit, but it's certainly worth looking at.

如果没有帮助，则您至少可以在SortedList<TKey, TValue>上编写自己的扩展方法.您可能无法轻松使用实际的where子句，但可以使用自己的方法使用最小值和最大值.您可能还 希望将其应用于IList<T>，在其中您断言已经对值进行了适当的排序(根据某些比较器).

If that doesn't help, you could at least write your own extension methods on SortedList<TKey, TValue>. You probably wouldn't be able to easily use your actual where clause, but you could use your own methods taking a minimum and a maximum value. You might also want to make them apply to IList<T> where you assert that you've already sorted the values appropriately (according to some comparer).

例如(完全未经测试):

For example (completely untested):

public static IEnumerable<T> Between<T, TKey>(this IList<T> source,
                                              Func<T, TKey> projection,
                                              TKey minKeyInclusive,
                                              TKey maxKeyExclusive,
                                              IComparer<TKey> comparer)
{
    comparer = comparer ?? Comparer<TKey>.Default;

    // TODO: Find the index of the lower bound via a binary search :)
    // (It's too late for me to jot it down tonight :)
    int index = ...; // Find minimum index

    while (index < source.Count &&
           comparer.Compare(projection(source[index]), maxKeyExclusive) < 0)
    {
        yield return source[index];
        index++;
    }
}

(如果您只有List<T>而不是IList<T>，则可以使用 List<T>.BinarySearch ，尽管您需要构建自定义的IComparer<T>.)

(If you only have List<T> instead of IList<T>, you could use List<T>.BinarySearch, although you'd need to build a custom IComparer<T>.)

此外，请查看.NET中的 SortedSet<T> 4.

Also, have a look at SortedSet<T> in .NET 4.

这篇关于LINQ to Objects和具有索引的改进性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！