LINQ to Objects和改进的带有索引的perf？

Question

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

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

一个简单的查询我会反对它...

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个实例.碰巧我已经有一个按年龄排序的人员集合的索引.像这样...

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

很明显,如果我可以获得在哪里使用SortedList以便它不再需要枚举所有50,000个实例,而是找到100个匹配条目的范围,从而节省时间.

是否可以将LINQ扩展到Objects来实现我的情况？它已经可以但我错过了这项技术吗？

Answer 1

已经有一个我相信的项目就是 - i4o.我不能说我自己使用它,但听起来像你想要的东西......你可能需要稍微调整你现有的代码,但它当然值得一看.

如果这没有帮助,您至少可以编写自己的扩展方法SortedList<TKey, TValue>.您可能无法轻松使用实际的where子句,但您可以使用自己的方法获取最小值和最大值.你可能也想使它们应用到IList<T>,你断言你已经正确排序的值(根据一些比较器).

例如(完全未经测试):

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>.)

另外,请看SortedSet<T>.NET 4.

Answer 2

你写的查询将枚举整个列表是对的,显然LINQ不能假设你的数据.

如果你有一个SortedList,你可以使用SkipWhile/TakeWhile linq方法来利用它:

 var x = x.SkipWhile(kv => kv.Key <= 18).TakeWhile(kv => kv.Key < 21)

编辑

@ Davy8当然是最糟糕的情况,这仍然具有相同的性能.查看其他答案,以便更快地找到第一个值.

如果您需要针对不同的年龄范围多次执行此操作,那么您可以通过按年龄分组来加快速度:

var byAge = people.GroupBy(p => p.Age);

var x = from grp in byAge 
        where grp.Key > 18 && grp.Key < 21
        from person in grp
        select person;