LINQ To Objects GroupBy method

Question

LINQ To Objects GroupBy 方法如何工作？它是否查看每个密钥的整个集合？有没有办法告诉 GroupBy 方法集合已排序？

Answer 1

如果做得合理，GroupBy将在单个仅向前传递中工作。基本实现（不是他们的）将类似于：

var data = new Dictionary<TKey, List<TValue>>(comparer);
foreach(var item in source) {
    var key = keySelector(item);
    List<TValue> list;
    if(!data.TryGetValue(key, out list))
    {
        data.Add(key, list = new List<TValue>());
    }
    list.Add(itemSelector(item));
}

这基本上是按键分组，为每个唯一键创建一个列表，其中包含值。

您可以做一些事情，例如与上次看到的键进行比较（以帮助排序数据），但是......您需要分析以了解它是否值得。

Answer 2

让我们看看重载

IEnumerable<IGrouping<TKey, TSource>> Enumerable.GroupBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector
);

因为它是最容易理解的。实际上，代码将执行以下操作：

枚举通过source

对于源中的每个element，将元素映射到key = keySelector(element)

查看key是否在按TKey键的字典中 如果不是，请将值为 a List<TSource>和第一项的key添加element 否则，获取与密钥关联的List<TSource>并将element添加到列表中

现在您有一个字典映射TKey -> TSource，并且可以轻松生成IGrouping<TKey, TElement>序列。

所以像

var dictionary = new Dictionary<TKey, List<TSource>> dictionary;
foreach(var element in source) {
    key = keySelector(element);
    List<TSource> list;
    if(!dictionary.TryGetValue(key, out list)) {
        list = new List<TSource>();
        dictionary.Add(key, list);
    }
    list.Add(element);
}

从这里您可以轻松生成一系列IGrouping<TKey, TSource>。

我不明白你为什么认为排序的清单很重要。

Answer 3

它是否查看每个密钥的整个集合？

不。 GroupBy 的实现是 O（n），而不是 O（n^2）