c# - 从无序列表中按值获取有序组列表的最佳方法

Question

我想知道是否有比使用 GroupBy() 更有效的方法从最初无序列表中按值获取有序组列表其次是 OrderBy() ，像这样:

List<int> list = new List<int>();
IEnumerable<IEnumerable<int>> orderedGroups = list.GroupBy(x => x).OrderBy(x => x.Key);

有关更多详细信息，我有一个很大的 List<T>我想对其进行排序，但是有很多重复值，所以我想将结果返回为 IEnumerable<IEnumerable<T>> , 多于 GroupBy()返回 IEnumerable组。如果我使用 OrderBy() , 我刚得到 IEnumerable<T> ，没有简单的方法可以知道值是否已从一项更改为另一项。我可以对列表进行分组，然后对组进行排序，但是列表很大，所以最终速度很慢。自 OrderBy()返回 OrderedEnumerable然后可以使用 ThenBy() 在辅助字段上对其进行排序, 它必须在内部区分具有相同或不同值的相邻项。

有什么办法可以利用 OrderedEnumerable<T> 的事实吗？必须在内部按值对其结果进行分组(以便于 ThenBy() )，否则使用 LINQ 获取有序组列表的最有效方法是什么？

Answer 1

• 您可以使用 ToLookup ，它返回一个 IEnumerable<IGrouping<TKey, TElement>然后做 OrderBy按需获取每个键的值。这将是 O(n) 创建查找和 O(h) 对每个组下的元素(键的值)进行排序，假设 h 是组下的元素数

• 您可以使用 IDictionary<TKey, IOrderedEnumerable<T>> 将性能提高到分摊 O(n) .但是如果你想按多个属性排序，它将再次按组的 O(h) 排序。参见 this answer有关 IOrderedEnumerable 的更多信息。您也可以使用 SortedList<TKey, TValue>而不是 IOrderedEnumerable

[更新]:

这里是 another answer你可以看看。但同样，它涉及在结果之上执行 OrderBy。

此外，您可以提出自己的数据结构，因为我在 BCL 上没有看到任何数据结构满足此要求。

一种可能的实现方式:

你可以有一个二叉搜索树，它平均在 O(longN) 中进行搜索/删除/插入。进行有序遍历将为您提供排序的键。树上的每个节点都将有一个有序集合，例如，用于值。

节点大致是这样的:

public class MyNode
{
    prop string key;
    prop SortedCollection myCollection;
}

您可以遍历一次初始集合并创建这种特殊的数据结构，可以查询它以快速获得结果。

[更新 2]: 如果你有可能低于 100k 的键，那么我觉得实现你自己的数据结构是一种矫枉过正。通常，订单返回的速度非常快，所花的时间也很短。除非您有大量数据并且多次排序，否则 ToLookup 应该工作得很好。