4
\$\begingroup\$

I have the following collection :

var items = new[] 
{
    new { Name = "A", Values = new [] { 20, 4, 5, 9, 3, 22 } },
    new { Name = "B", Values = new [] { 10, 7, 9, 8, 42 } },
    new { Name = "C", Values = new [] { 11, 103, 0 } },
    new { Name = "D", Values = new [] { 7, 35, 42 } }
};

I would like to find which items have at least one common integer value with the others items. For example, "A" has 9 in common with "B", so "A" and "B" are related each other.

At the end, this should be the result :

A => [B]
B => [A, D]
C => []
D => [B]

I wrote this code :

var tuples = items 
    .SelectMany(x => x.Values, (x, y) => new { x.Name, Value = y })
    .ToList();  

var result = tuples.Join(tuples, 
           x => x.Value, 
           x => x.Value, 
           (x, y) => new { NameA = x.Name, NameB = y.Name })        
    .Distinct()
    .GroupBy(x => x.NameA, x => x.NameB, 
        (a, b) => new { Name = a, Overlaps = b.Where(x => x != a)) });

It works (and return expected results). I was wondering if there would be a more efficient (faster and with a lower memory footprint) way do to it. I wanted to use GroupJoin() but since I need to filter out duplicate values (using Distinct) I used Join() instead.

\$\endgroup\$
  • 1
    \$\begingroup\$ Regarding the on-topicness of the question and the rollbacks around it. As per meta policy answers to off-topic questions are not considered for the purposes of evaluating rollback criteria. As such fixing the code to make the question on topic is always acceptable. \$\endgroup\$ – Vogel612 Sep 25 at 20:41
5
\$\begingroup\$

For set-based operations like this it's better to use HashSet<T>.

The HashSet<T> class provides high-performance set operations.

The items can easily be converted to ones containing HashSets. Then, the Overlaps method does the comparison:

var hashed = items
    .Select(i => new { Name = i.Name, Values = i.Values.ToHashSet() })
    .ToList();
var overlaps = hashed.Select(h1 => new
{
    h1.Name,
    Overlaps = hashed
        .Where(h2 => h2.Name != h1.Name && h2.Values.Overlaps(h1.Values))
        .Select(h => h.Name)
});

Result:

A => B 
B => A,D 
C   
D => B 

Of course, if possible, it would be better to create items with HashSets at the outset.

EDIT

Triggered by your comment I did some benchmarking. I blew up your array a 1000 times, keeping unique names and then just measured both methods, using Linqpad:

var items = Enumerable.Range(1,1000).SelectMany(e =>  new[]
{
    new { Name = "A" + e, Values = new [] { 20, 4, 5, 9, 3, 22 } },
    new { Name = "B" + e, Values = new [] { 10, 7, 9, 8, 42 } },
    new { Name = "C" + e, Values = new [] { 11, 103, 0 } },
    new { Name = "D" + e, Values = new [] { 7, 35, 42 } }
});

var sw = Stopwatch.StartNew();
var hashed = items.Select(i => new { Name = i.Name, Values = i.Values.ToHashSet() }).ToList();

sw.Elapsed.Dump();

var overlaps = hashed.Select(h1 => new
{
    h1.Name,
    Overlaps = hashed
        .Where(h2 => h2.Name != h1.Name && h2.Values.Overlaps(h1.Values))
        .Select(h => h.Name).ToList()
}).ToList();
sw.Stop();
sw.Elapsed.Dump();

sw.Restart();
var tuples = items
    .SelectMany(x => x.Values, (x, y) => new { x.Name, Value = y })
    .ToList();

sw.Elapsed.Dump();
var result = tuples.Join(tuples,
           x => x.Value,
           x => x.Value,
           (x, y) => new { NameA = x.Name, NameB = y.Name })
    .Where(x => x.NameA != x.NameB)
    .Distinct()
    .GroupBy(x => x.NameA, x => x.NameB)
    .ToList();
sw.Stop();
sw.Elapsed.Dump();

The results:

00:00:00.0035664
00:00:02.0326684
00:00:00.0029370
00:00:06.3872002

As you see, the preparatory actions for both methods are done in 'no time', but the hashset-based method is considerably faster. Interestingly, if I blow up the arry 2000 times, the hashset-based method takes 7.7s and your method throws an OutOfMemoryException on my box.

Side note: if I don't make the names unique both methods are comparable. (On which I based my previous comment).

\$\endgroup\$
  • \$\begingroup\$ I tried your solution and it is much slower than original one. Overlaps() is not the issue. Bottleneck is the two inner loops on hashed. It is basically O(n^2) \$\endgroup\$ – tigrou Sep 25 at 11:12
  • \$\begingroup\$ OK, I didn't really have data to benchmark this, but then, I didn't expect this because the hashset comparison itself is really fast. It may turn out that your SelectMany version is the most efficient/scalable way to do it because Join's time complexity is O(n). \$\endgroup\$ – Gert Arnold Sep 25 at 11:41
  • \$\begingroup\$ If I blow up your items array 2000 times I get comparable results as for execution time (adding ToList to the inner Select to force execution). Did you notice that I added ToList() later to the creation of hashed? Anyway, comparable results is nothing like "faster", so if I can't think of any improvement I'll leave this answer here for reference, but of course it's not acceptable. \$\endgroup\$ – Gert Arnold Sep 25 at 11:58
  • \$\begingroup\$ Please check my test code here. Your solution is considerably slower. I am not sure why it differs from results you got. \$\endgroup\$ – tigrou Sep 25 at 12:47
  • 1
    \$\begingroup\$ It seems that the chance of overlaps is decisive here. When there are no overlaps, HashSet.Overlaps has to exhaust both sets to come to a conclusion, while Join benefits from fewer overlaps. However, when the number of items in the arrays increases (take max 40) then the hashset-based method gets the better one. So it seems to depends much on content and it's yours to decide which method suits you best. I think one advantage of my method is that it's less complex (more self-explanatory) and it seems to have a better memory consumption. \$\endgroup\$ – Gert Arnold Sep 25 at 13:01
2
\$\begingroup\$

I would make use of Intersect(), which, when combined with Any(), compares two lists of values and returns true if any matching values exist. I tested it and it runs significantly faster.

Separating and storing all the name-value pair combinations in memory seems overly costly and unnecessary.

var result = items.Select(x => new 
{ 
    x.Name, 
    Related = items.Where(y => 
                              y.Name != x.Name 
                              && 
                              y.Values.Intersect(x.Values).Any()
                         )
                         .Select(y => y.Name) 
});
\$\endgroup\$
  • 1
    \$\begingroup\$ This is \$O(n^2)\$, so it'll perform significantly worse for larger numbers of items. You'll only notice when you actually start enumerating the results (and their Related properties) though, due to the 'lazy' nature of Select. \$\endgroup\$ – Pieter Witvoet Sep 25 at 11:49
  • \$\begingroup\$ @PieterWitvoet is O(n) even possible? \$\endgroup\$ – Innat3 Sep 25 at 16:15
  • \$\begingroup\$ I think tigrou's solution is \$O(n)\$, with \$n\$ being the total number of values. Join, Distinct and GroupBy will use some sort of hash-based lookup internally, so they should all be \$O(n)\$. \$\endgroup\$ – Pieter Witvoet Sep 25 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.