Linq Distinct across multiple tables?

Question

The below linq resuired is too jedi for my brain, is what im trying to do even possible?

var aa = new string[] { "1", "2" };
var bb = new string[] { "1", "2", "3" };
var cc = new string[] { "2" };

//*cannot directly reference the above anymore*//
var dd = new string[][] { aa, bb, cc };
//result = dd.**magical linq to only get item(s) present in each table** i.e. result = {"2"}

I actually laughed when I read `magical linq`. – Kredns Jan 10 '11 at 09:54 — Kredns, Jan 10 '11 at 09:54

spender · Answer 1 · 2011-01-10T09:54:46.130

3

There may be a niftier way, but you can build a query in a loop:

var aa = new string[] { "1", "2" };
var bb = new string[] { "1", "2", "3" };
var cc = new string[] { "2" };

var dd=new string[][] { aa, bb, cc };

IEnumerable<string> q=dd.First();

for(var i=1;i<dd.Length;++i)
{
    q=q.Intersect(dd[i]);
}

edited Jan 10 '11 at 09:54

answered Jan 10 '11 at 09:49

spender

117,338
33
229
351

@Richard: The whole point of LINQ isn't to avoid loops; it's to make code more expressive and readable. It's often the case that a plain loop is more readable than its LINQ equivalent. – LukeH Jan 10 '11 at 10:18
Yes and no, agree readability is important, but in a lot of cases the Linq will operate differently through the way the underlying Linq provider works, and by executing a loop you remove that functionality. Most visible example is with a SQL provider, where expressions are translated into SQL and ran on the database - if you run a loop, you bypass that stage, often with performance cost. – RichardW1001 Jan 10 '11 at 10:25
The query isn't enumerated/evaluted until anywhere in this code. Your assertions about loops are not really valid unless the query is evaluated in the loop. Building a query in a loop (as opposed to making queries in-loop) is perfectly valid and won't affect the outcome, regardless of provider. It seems you are struggling with the deferred nature of LINQ. – spender Jan 10 '11 at 11:36

LukeH · Accepted Answer · 2011-01-10T10:33:19.053

3

var result = dd.Aggregate<IEnumerable<string>>((a, x) => a.Intersect(x));

If you want slightly better theoretical performance, at the expense of some readability, then you can do the following instead. It avoids the need to construct a new set for each intersection operation, using an explicit HashSet<T> to the pass the result to the next iteration rather than a plain IEnumerable<T>.

var result = dd.Aggregate((HashSet<string>)null,
                          (a, x) => {
                                        if (a == null)
                                            a = new HashSet<string>(x);
                                        else
                                            a.IntersectWith(x);
                                        return a;
                                    });

edited Jan 10 '11 at 10:33

answered Jan 10 '11 at 09:59

LukeH

263,068
57
365
409

Why is this more effective than join for example... for me it seems like a join should be used. See my late answer... but it is a nice solution with `Aggregate` :). – Tomas Jansson Jan 10 '11 at 10:59
-1, pushing all the result processing into CLR objects rather than letting the Linq provider work efficiently; does this even give the right answer ({"2"}), I suspect not? – RichardW1001 Jan 10 '11 at 11:19
@Richard: If this is LINQ-to-Objects -- and the example in the question certainly is, the data source being a `string[][]` array -- then *I am* using the LINQ provider efficiently. And why don't you actually test to see whether it gives the right answer and base your downvote on facts rather than your suspicions? – LukeH Jan 10 '11 at 11:26
@Tomas: I think a join would have a worst-case complexity of O(n*m) whereas an intersection should be O(n+m). In this case though I suspect there won't really be much difference, although `Intersect` is more readable, imo. (Correct me if I'm wrong on this, these type of calculations aren't really my forté!) – LukeH Jan 10 '11 at 11:27
Fair dos, the example in the question is Linq to Objects. The question however mentions tables, so the implication is that there will be a database interaction in the real-world application, at which point this will cease to be the most effective solution. Removed downvote, although I don't think this is actually the best solution because you are artificially introducing an assumption of using a specific Linq provider, at the expense of behaviour when a different provider is used. – RichardW1001 Jan 10 '11 at 11:42

score 3 · Answer 3 · answered Jan 10 '11 at 10:00

You could use the set operators - Union, Intersect etc.

(edit - misread question!)

I believe Intersect gives you what you're after straight out of the box:

var dd = aa.Intersect(bb).Intersect(cc);

Note that that will work because aa bb and cc are already all IEnumerables of the same type. If your IEnumerables are of different types (like from different Linq tables) you'll have to project the property you want:

var dd = aa.Select(a => a.PropertyA).Intersect(bb.Select(b => b.PropertyB).Intersect(cc.Select(c => c.PropertyC);

The result there will be an IQueryable, so you could chain on ToArray(), ToList() etc on the end to give the result you want.

score 3 · Answer 4 · edited May 23 '17 at 12:19

Caution, if you are using LINQ to SQL and you cast any part of a composite query to IEnumerable<>, that part cannot be combined with the rest of the query to form a single SQL query. This would happen using SQL as the datasource in the example by spender where the query is implicitly cast to IEnumerable<> when it is assigned to 'q'. Use IQueryable instead. Although each IEnumerable is deferred, three SQL queries will be sent to the server, and the intersection will be performed in-memory.

See Returning IEnumerable<T> vs. IQueryable<T> or search "IEnumerable vs IQueryable" to get references.

Tomas Jansson · Answer 5 · 2011-01-10T11:16:17.830

Why not use a simple join?

class Program
{
    static void Main(string[] args)
    {
        var aa = new string[] { "1", "2", "4" };
        var bb = new string[] { "1", "2", "3", "4" };
        var cc = new string[] { "2", "4" };

        //*cannot directly reference the above anymore*//
        var dd = new string[][] { aa, bb, cc };

        var result = dd.Aggregate((x, y) => x.Join(y, z => z, z => z, (z, v) => z).ToArray());
        foreach (var item in result)
        {
            Console.WriteLine(item);
        }
        Console.ReadLine();
    }
}

Linq Distinct across multiple tables?

5 Answers5