Create List by Unique Key with Linq

Question

I have a class of type Dependency:

class Dependency
{
    public int Source;
    public int Target:
}

Given a list of List<Dependency> I would have the following list (each line is a Source/Target pair):

1, 2
1, 5
2, 1
3, 4
3, 6

Is it possible to merge them with Linq so that the following is produced List<Tuple<int,List<int>>:

1, [2,5]
2, [1]
3, [4,6]

Given a larger list of a couple of thousand items, would using Linq be the fastest way to perform the above merge?

So are `Source` and `Target` separate lists, or is it a class with properties `Source` and `Target`? — dotnetom, Sep 28 '14 at 10:35
Group by `Source` and the rest should be easy. Can't speak about speed, though. — Frédéric Hamidi, Sep 28 '14 at 10:39

score 4 · Accepted Answer · answered Sep 28 '14 at 10:42

You can use LINQ group by operator like this:

var items = new List<Dependency>();
// add your items to list

var result = (from i in items
             group i by i.Source
             into gr
             select new Tuple<int, List<int>>(gr.Key, gr.Select(a => a.Target).ToList())).ToList();

The above query should be quite fast, although it is hard to compare with other ways of achieving the same thing. I suggest testing that in practice - write alternative implementation and compare the performance.

If you would likr the methods equivalent: `items.GroupBy(x=>x.Source,(k,x)=>new Tuple>(k,x.Select(g=>g.Target).ToList())).ToList();` — Giannis Paraskevopoulos, Sep 28 '14 at 10:57

score 3 · Answer 2 · edited May 23 '17 at 10:26

_{Note: This other answer recommends C#'s group into syntax. My answer shows something similar, namely the .ToLookup(…) operator. If you're asking what the difference between these two is, see e.g. the following question: ILookup<TKey, TVal> vs. IGrouping<TKey, TVal>.}

The following solution won't yield a List<Tuple<int, List<int>>>, and I cannot say whether it is the fastest solution, but it's quite probably the most succinct:

ILookup<int,int> multiMap = dependencies.ToLookup(d => d.Source, d => d.Target);

The .ToLookup(…) operator groups your dependencies by their Source property (as specified by the first lambda), and instead of putting complete Dependency objects into the output, it only selects their Target values (as specified by the second, optional lambda).

What you get is an ILookup<TKey,TElement>, which is essentially like a Dictionary<TKey,TValue>, except that there can be several elements (values) per key.

Here's an example how you can iterate over all the values in such a data structure (a so-called multimap):

foreach (IGrouping<int,int> grouping in multiMap)  // enumerate over all groups
foreach (int target in grouping)  // enumerate over all values in one specific group
{
    int source = grouping.Key;  // get the key value of the group
    …
}

Create List by Unique Key with Linq

2 Answers2