# Finding which items have at least one common value with other items

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.

• 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. – Vogel612 Sep 25 at 20:41

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).

• 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) – tigrou Sep 25 at 11:12
• 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). – Gert Arnold Sep 25 at 11:41
• 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. – Gert Arnold Sep 25 at 11:58
• Please check my test code here. Your solution is considerably slower. I am not sure why it differs from results you got. – tigrou Sep 25 at 12:47
• 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. – Gert Arnold Sep 25 at 13:01

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)
});

• 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. – Pieter Witvoet Sep 25 at 11:49
• @PieterWitvoet is O(n) even possible? – Innat3 Sep 25 at 16:15
• 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)$. – Pieter Witvoet Sep 25 at 22:05