LINQ To Objects GroupBy 方法

Question

LINQ To Objects的GroupBy方法是如何工作的？它是否会为每个键遍历整个集合？有没有办法告诉GroupBy方法集合已经排序？

- SiberianGuy

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));
}

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

你可以做一些比较最后看到的键的事情（以帮助排序数据），但是……你需要进行性能分析才能知道是否值得。

- Marc Gravell

---

如果我理解正确的话，您的意思是在创建枚举器时会对整个序列进行完整遍历，并且枚举器无法感知源序列之后的任何更改？ - relatively_random

Answer 2

让我们来看看重载（overload）

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

作为最简单易懂的方法，实际上代码将执行以下操作：

枚举源（source）

对于源中的每个元素（element），将元素映射到“key = keySelector（element）”

查看以TKey为键的字典中是否存在“key” 如果不存在，则添加一个键值为List和第一个项为element的key 否则，获取与key相关联的List并将element添加到列表中

现在你有一个将TKey映射到TSource的字典，并且可以轻松地生成IGrouping序列。

因此，类似以下内容：

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

我不明白您为什么认为列表的排序很重要。

- jason

---

如果列表已经排序，我们可以在不处理整个列表的情况下生成 IGrouping。 - SiberianGuy

如果列表按键排序，并且您知道它，您可以构建一个IGrouping对象，然后在键值更改时yield return它，然后开始一个新的IGrouping。@Idsa-制作一个GroupBySorted扩展方法并对其进行分析以查看它是否比常规的GroupBy有任何实际好处不会太难。 - Joel Mueller

Answer 3

它会为每个键遍历整个集合吗？ 不会。GroupBy的实现是O(n)，而不是O(n^2)。

- Amy B