c# - LINQ to Objects 并通过索引改进性能？

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 to 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 中。