Best way to get an ordered list of groups by value from an unordered list

Question

I would like to know if there is a more efficient way to get an ordered list of groups by value from an initially unordered list than to use GroupBy(), followed by OrderBy(), for example:

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

For more details, I have a large List<T>one that I would like to sort, however there are many duplicate values, so I want to return the results as IEnumerable<IEnumerable<T>>, but GroupBy()returns the IEnumerablegroups. If I use OrderBy(), I just get IEnumerable<T>, without having an easy way to find out if the value has changed from one element to another. I could group the list, then sort the groups, but the list is large, so this ends up being slow. Since it OrderBy()returns OrderedEnumerable, which can then be sorted by a secondary field using ThenBy(), it must internally distinguish adjacent elements with the same or different values.

Is it possible to use the fact that I OrderedEnumerable<T>have to internally group my results by value (to facilitate ThenBy()), or else, what is the most efficient way to use LINQ to get an ordered list of groups?

Answer 1

• You can use ToLookup , which returns IEnumerable<IGrouping<TKey, TElement>and then OrderByfor the values ​​of each key upon request, This will be O (n) to create a search and O (h) to arrange the elements under each group (values ​​for the key), assuming that h is the number of elements under the group

• O (n) IDictionary<TKey, IOrderedEnumerable<T>>. , O (h) . . IOrderedEnumerable. SortedList<TKey, TValue> IOrderedEnumerable

[]:

, . , OrderBy .

, , , - , BCL, .

:

, // O (longN) . . node , , .

node :

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

, .

[ 2]: 100 ., , . , , . , , ToLookup .

Answer 2

, ,

items.GroupBy(i => i.KeyProperty).OrderBy(g => g.Key);

GroupBy - O(n). OrderBy O(k log k), k - .

OrderBy... , -, O(n log n) , , , .

-, IOrderedEnumerable , . , , ThenBy; , ThenBy, , .

, , " ", , SortedDictionary<TKey, IList<TItem>>, , O , LINQ . LINQ

Answer 3

I think I will repeat through the list for(;;)when you fill Dictionary<T, int>, where is the value - the number of repeating elements will be faster.